endless-sky Allow the creation of bays that can carry ships of multiple types

Feature

This PR addresses the bug/feature described in issue #9896.

Summary

This PR adds a new root node bay that behaves as follows:

bay <name>: A named bay type. When a ship definition includes a bay point, that bay will be able to store ships from the matching bay root node. If no bay root node matches the name of the ship's bay, then it is assumed that the name of the ship's bay matches a singular category of ship that can be carried. This is done for backwards compatibility.
- This root node takes single token strings as children, similar to the category root node. The children strings are the categories of ship that bays of this type can store. The category must also be present in the category "bay type" root node.
- A named bay is added to whenever it is redefined (such as by a plugin), instead of overwriting it.

This PR only adds the mechanics for bay root nodes. No bay root nodes are added by this PR.

Usage examples

# The categories of ship that can be carried in bays.
category "bay type" 
	"Drone" 
	"Fighter"
	"Bomber"

# Fighter bays carry both fighters and drones.
bay "Fighter"
	"Drone"
	"Fighter"

# Drone bays carry only drones.
bay "Drone"
	"Drone"

ship "Cooler Carrier"
	# This "Fighter" bay refers to the "Fighter" bay node instead of the "Fighter" category,
	# meaning that it can carry both fighters and drones.
	bay "Fighter" x y
	# This "Bomber" bay has no matching "Bomber" bay root node. Therefore, we assume
	# that this bay may only hold the "Bomber" ship category.
	bay "Bomber" x y

Testing Done

Launched the game with no bay root nodes defined.
- Bought a Carrier (6 drone bays, 4 fighter bays), 6 drones, and 4 fighters. Received no flight check warnings for my ships and was able to deploy and recall my fighters.
- Purchased 10 drones and 0 fighters. Received flight check warnings for 4 of the drones. Upon launching, 4 of the drones weren't docked. After deploying and recalling, there were still 4 stray drones.
- Purchased 0 drones and 10 fighters. Received flight check warnings for 6 of the fighters. Upon launching, 6 of the fighters weren't docked. After deploying and recalling, there were still 6 stray fighters.
Launched the game with the "Fighter" and "Drone" bay root nodes from the usage examples.
- Using the same Carrier, purchased 4 fighters and 6 drones, IN THAT ORDER. Received no flight check warnings.
  - [x] ~~When I took off, all my ships were docked. Deploying worked fine. Upon recalling, only the drones would redock. Sometimes a fighter would redock, but as soon as a drone would dock, the fighters wouldn't dock anymore. Seems like the fighter bays were being filled first, so as soon as the drones would dock, the fighters would be unable to do so.~~ Fixed by https://github.com/endless-sky/endless-sky/pull/9906/commits/f7f755857e8d0771168cd8f83d7053dce03db1d3
  - [x] ~~Flipped the order that I purchased the ships so that it was 6 drones then 4 fighters. On take-off, the ships appear to be filling the bays in their order in your ships list, meaning the drones filled the Carrier first and therefore stole the fighter bays from the fighters.~~ Fixed by https://github.com/endless-sky/endless-sky/pull/9906/commits/f7f755857e8d0771168cd8f83d7053dce03db1d3
- Purchased 1 additional fighter for a total of 5 fighters and 6 drones. Received a flight check warning for it, as I had 5 fighters but only space for 4.
- Purchased 1 additional drone for a total of 4 fighters and 7 drones. Received a flight check warning for one of my fighters, as I have space for up to 10 drones total and purchasing the drone kicked a fighter out of its bay.
  - NOTICE: When I took off, there was a stray drone that wasn't docked even though it was a fighter that had the flight check warning. I don't know how much importance we want to put on making it so that the flight checks for extra carried ships exactly match which ships aren't carried when you take off, though.
- Purchased 10 drones. Received no flight check warnings for any of them. Every drone was able to deploy and recall.
- Purchased 10 fighters. Received flight check warnings for 6 of them. Only 4 were able to deploy and redock at a time.

Mar 10 '24 19:03 Amazinite

Opening as a draft to show that this is being worked on. Noting that the snag I caught during testing is a rather large one.

Using the same Carrier, purchased 6 drones and 4 fighters. Received no flight check warnings.

When I took off, all my ships were docked. Deploying worked fine. Upon recalling, only the drones would redock. Sometimes a fighter would redock, but as soon as a drone would dock, the fighters wouldn't dock anymore. Seems like the fighter bays were being filled first, so as soon as the drones would dock, the fighters would be unable to do so.

This is likely happening because the bays are filled in the same order they are defined. On the Carrier, the fighter bays are defined first, and so the drones fill the fighter bays first. The order that the bays are defined in should not matter, though.

I imagine we could make it so that a carrier more intelligently fills its bays by shuffling carried ships to the most restrictive bays first (e.g. if there is a ship of type X docking and the ship has a bay that holds both X and Y and another bay that holds only X, put the ship in the bay that holds only X first), but then we run into issues of having multiple carriers in the same fleet.

Say you have two Carriers. That makes 12 drones and 8 fighters. A Carrier can hold up to 10 drones, or 6 drones and 4 fighters. What happens if you recall and 10 of your drones go to one Carrier and 2 go to the other? Well the second carrier would still have space for 4 fighters, but now you have 4 fighters flying around with nowhere to dock.

Right now when recalling, fighters and drones basically just go to the first ship they can find that can hold them. If we want to be able to have bays that can hold multiple ship categories, we need to basically reserve every bay the moment that the recall occurs in an order that ensures that every carried ship can dock.

Either that, or we completely do away with the fighter/drone distinction for the sake of simplicity. I don't think that's the way we should go if we don't need to, though.

Mar 10 '24 19:03 Amazinite

Right now when recalling, fighters and drones basically just go to the first ship they can find that can hold them. If we want to be able to have bays that can hold multiple ship categories, we need to basically reserve every bay the moment that the recall occurs in an order that ensures that every carried ship can dock.

Is it not possible to make use of the ships' parent attribute for this, making them board their parent if possible? Or would that break every other use case? (I recall a PR from a couple months/years ago that had something like this, not sure what happened to that.)

On a separate note, how does this handle plugins adding ship categories to existing bay types?

Mar 10 '24 19:03 tibetiroka

An alternative solution would be to have ships take off from a docked state to rearrange themselves, if only a portion of them were docked before. (This would have issues with disabled ships not being able to take off, and would be a bit of a UX nightmare, but might help as a stopgap measure.)

Mar 10 '24 19:03 tibetiroka

On a separate note, how does this handle plugins adding ship categories to existing bay types?

A named bay is added to whenever it is redefined (such as by a plugin), instead of overwriting it.

Mar 10 '24 19:03 Amazinite

An alternative solution would be to have ships take off from a docked state to rearrange themselves, if only a portion of them were docked before. (This would have issues with disabled ships not being able to take off, and would be a bit of a UX nightmare, but might help as a stopgap measure.)

We'd need to be able to intelligently reorder carried ships in the first place to even be able to do that, so might as well just dock them in an intelligent order to begin with.

Mar 10 '24 19:03 Amazinite

Is it not possible to make use of the ships' parent attribute for this, making them board their parent if possible? Or would that break every other use case?

That, plus intelligent docking order, would likely solve most of the problem. The only extra case to account for would be intelligently parenting new ships that you capture.

(I recall a PR from a couple months/years ago that had something like this, not sure what happened to that.)

Are you thinking of this one? #6130

Mar 10 '24 19:03 Amazinite

That, plus intelligent docking order, would likely solve most of the problem. The only extra case to account for would be intelligently parenting new ships that you capture.

It's a bit more than that, since you can lose and gain both carriers and fighters, so it might be necessary to re-dock some ships to be able to fit everything in, even if the order was correct previously. (This is amplified if not all ships were requested to dock initially, or there wasn't enough space the first time the order was given.)

Are you thinking of this one? #6130

Yeah that PR seems to have some useful functionality. Tieing bays and carried ships together would probably allow for caching a bunch of the necessary calculations, but isn't enough when ships are lost (or gained I guess).

Mar 10 '24 19:03 tibetiroka

The way this is shaping up, that could be a whole PR of its own changing how fighters and drones reparent.

I'm tempted to say we tackle intelligent docking order here so that given a single carrier everything looks good when taking off and recalling, then any sort of permanent parenting and recalculating parents when fighters are gained or carriers are lost could be done next.

Nothing changes anyway until we add any bay root nodes, so it's not like merging just this would break anything.

Mar 10 '24 20:03 Amazinite

Just a dumb question, but why not just have 1 'bay type' that allows both drones and/or fighters to use it?

I assume that this might mess with plugin compatibility

Mar 10 '24 20:03 xX-Dillinger-Xx

We could very easily have that be the case for vanilla, even without this PR or any other engine updates, but then that leaves no customization options for plugins. Compatiblity would be fine.

What I'm doing here though is adding capabilities to the engine. How vanilla or any plugins make use of the engine's mechanics is a separate topic.

Mar 10 '24 20:03 Amazinite

Don't mind me I'm just trying learn, I hope I'm not becoming a pest. I understand your trying to accommodate customizations, I am just offering up a possible option if what your trying do becomes too complicated.

Just keeping it simple, whats happens if:

keep fighter bays < only accepts fighter
keep drone bays < only accepts drones
add new 'universal' bay < accepts anything in a predetermined list

Am I right in assuming all existing ship builds in vanilla and plugins would continue as is. ? Any edited or new ship builds should only contain 'universal' alone OR a mix of fighter and drone.

I afraid that adding even more calculations may have a negative impact to people with weak GPU, like me.

Mar 10 '24 20:03 xX-Dillinger-Xx

I afraid that adding even more calculations may have a negative impact to people with weak GPU, like me.

GPUs are for drawing the frames. Gameplay calculations, which this would be, are for the CPU.

Mar 10 '24 22:03 Amazinite

When a ship docks with a carrier, the carrier now docks the ship in the most restrictive bay first, where restrictiveness is measured by the number of categories the bay allows. If a drone is docking and a carrier has two bays, one that carries only drones and one that carries both drones and fighters, then the first of those two bays is considered the more restrictive and the drone is placed there. That way, drones don't hog fighter bays from fighters when they could've used a drone bay.

Mar 12 '24 08:03 Amazinite

as thee did request, h're is thy revieweth

May 11 '24 20:05 RisingLeaf

Looks like another docking order issue. The drones are being docked first before the fighters. The drones choose one of the carriers to dock with and then fill the drone bays first since those are the most restrictive, but then they start loading into the fighter bays before the fighters get a chance to instead of looking for drone bays on a separate carrier. By the time the fighters get a chance to dock, the drones have already filled all the bays on the first carrier.

We need to change it so that carried ships look at all available bays across the whole fleet instead of choosing a carrier at random to dock with then determining if that carrier has available bays.

Jul 13 '24 18:07 Amazinite

This is not a trivial fix. :|

Jul 13 '24 19:07 Amazinite

Could you not just prioritise bays with single use? Would have to look at the code to actually grasp it ig. I imagine this being even more complex for bays with triple use. It does sound a bit like the bin packing problem though.

Jul 13 '24 21:07 RisingLeaf

Could you not just prioritise bays with single use?

That's what I'm trying to do. Have some difficulty getting it working for some reason, though.

Jul 13 '24 21:07 Amazinite

The latest commit fixes the provided save files, but it isn't 100% of the way there. I left a few todo comments in areas that still need improved upon.

Jul 13 '24 22:07 Amazinite

Converting to a draft, as I'm pretty sure that we need proper bay reserving behavior (such as in #6130) so that we can maintain an efficient docking order. The issue I'm having now is that the fighters are efficiently docked on take off, but upon deploying and recalling I get a bunch of stray fighters since they're for some reason all trying to dock on the same carrier instead of spreading out across the multiple carriers in the fleet. Although maybe that's just something I messed up with my change to Ship::CanCarry or something in AI.

Jul 14 '24 02:07 Amazinite