More intelligent Rocket auto-launch

[dgnuff]

TL;DR:

Improve on the current algorithm that currently only automatically launches a full load of a single entity type.

Why:

Building rockets is a painful process. More often than not, a rocket design doesn't require exactly a multiple of (e.g.) 100 belts. This means that components need to be loaded and launched manually.

What:

It was noted in this thread on Steam https://steamcommunity.com/app/427520/d ... 020781600/ that the "optimal" solution to this problem requires solving the Knapsack problem https://en.wikipedia.org/wiki/Knapsack_problem . So we don't try that. Rather than get a perfect load every time, this aims to get as close to optimal as is reasonably possible, while being able to do so in reasonable time. i.e. not the exponential time required by the Knapsack problem, or any other NP-complete problem for that matter.

Proposed load algorithm.

1. There are two special snowflakes: Foundations and Cargo bays. Always send Foundations first, and then send Cargo bays second. This does mean that there is a risk when sending the last Foundations that there will be empty space after as many Cargo bays as possible have been loaded, assuming they didn't all fit. However this space will never be greater than 90 kilos, just under 10% of Rocket capacity. Remember how I said this is only reasonably optimal, not perfect.
2. Once the last Cargo bays have been loaded, there may be empty space on the rocket. Fill it using the general algorithm that follows, which is also used to fill subsequent completely empty rockets.
3. The logistic network that is providing parts to the Silo is aware of the total count of each entity type in the provider chests. This is provable because when a rocket is auto-filling with normal cargo, hovering over a request in the ship shows the quantity available on the planet.
4. Create a sorted multimap, C++ provides the std::multimap STL container precisely for this purpose. For each entity type being requested, use the count of each item that will fit in the rocket (e.g. 100 for Belts, 10 for Asteroid Grabbers, 1000 for Science Packs, etc.) as the key in the multimap, and the entity itself as the value.
4a. An alternative data structure that might be a little faster is a sorted map, where key values are individual weight classes from above, and the value is a "fast container", e.g. std::unordered_set where each member of this second collection is the items of a given weight, e.g. 100 would hold all four colors of belts in use etc., 50 would hold all inserters etc., 10 would hold ship components: asteroid grabbers, crushers, etc. and so on.
5. Find the heaviest item (value with lowest key) that will still fit in the rocket. Load these until either there's no space left in the Rocket for more, or the request from the ship is satisfied. Repeat this step till you can't find anything left that will fit.
6. Launch the rocket. Repeat from step 5 until there's nothing being requested by the ship.

This isn't going to be perfect, it will sometime launch a rocket that's not completely full. That's understood. But at least it will be a vast improvement over the current system.

For the curious, this is close to the First-Fit Decreasing algorithm: https://en.wikipedia.org/wiki/First-fit ... in_packing . Note that the Performance section of that refers to the number of rockets (bins) used, rather than the time taken to fill them. In Factorio, I very strongly suspect the computation time is a far greater concern. This would, of course need to be tested to see (A) does it actually work, and (B) if so, what performance impact if any is there?

My reason for adding 4a is that the search time for both a std::map and std::multimap is O(n log2(n)). By reducing the count of entries in the map, search time on the map goes down. Search time on a std::unordered_set is constant, so overall there is a chance that 4a may work out faster than 4 if there are a large number of entity types involved.