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.

[DinnerBuffet]

+1 on some kind of change like this. I made a quick proof of concept mod to see if I could get this behavior and got surprisingly far. The mod is able to automatically combine a full rocket's worth of materials (Using the first-fit packing algorithm below) and launch them to the requesting platform. However, it's a bit janky and broken in many cases.

Caveats:

• You need to manually turn off "Automatic requests from space platforms". There is no way in mod to disable the default behavior otherwise.
• The platforms don't "know" that requested materials are being launched in the way that the default behavior knows, so in order to prevent a platform from leaving mid-request I had to make the mod pause the platform from moving and keep track of the request until it arrives, which the mod will detect and then unpause.
• Even though you're probably not supposed to, you can access the rocket silo's requester point in order to make logistic requests directly to the rocket silo and will even automatically launch the rocket as soon as it is full.
• Unfortunately, despite numerous attempts to get around it, the rocket will always launch with only one type of item when using the above method. If your logistic request was 100 low-density units and 150 processing units, all will be delivered to the rocket silo, but as soon as all items are delivered, the rocket will automatically launch with just the 150 processing units, leaving the 100 low-density units in the inventory. This completely breaks the mod and makes it useless.

I'm sure you could still make a mod that can do something like this by requesting it to a logistic's chest and inserting things into the rocket from there, but this gets a bit tricky because of the above caveats and I gave up. Hoping that Wube makes this a thing in 2.1 or at least makes it easier to mod the behavior!

[Koub]

[Koub] Moved to Ideas and Suggestions from Frequently Suggested / Link Collections.

[crimsonarmy]

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.

Rockets, once you get to the midgame, are relevantly cheap so a suboptimal algorithm being the default (and sending some things you don't need to) isn't really an issue (early game you are launching so few rockets that manually doing things isn't really an issue).

see 116498

[juliawtapp]

I feel like the main issue with loading rockets with an algorithm like the above-mentionned first-fit method is not that it can't be done, but that (as mentionned at least once in the thread linked by crimsonarmy) once you get to later game, you have dozens, hundreds, even thousands of rocket silos.

Going through a few silos multiple times to pack requests into them more tightly probably doesn't matter in terms of UPS cost but doing so for hundreds or thousands of silos in my mind means doing all those extra steps for every single rocket silo, which i would imagine would result in hitting a performance limit much sooner than with the current system.

And as mentionned by others, why not just make more rockets? Why does it matter if there are extra parts in your platform? They'll be there when you decide to expand it, or to repair any damage from incidents.

[angramania]

Going through a few silos multiple times to pack requests into them more tightly probably doesn't matter in terms of UPS cost but doing so for hundreds or thousands of silos in my mind means doing all those extra steps for every single rocket silo, which i would imagine would result in hitting a performance limit much sooner than with the current system.

Can be simply solved. Just add checkbox like "use smart packing" or "pack multiple items in one rocket" and use packing algorithm only for sillos with this setting on.

And as mentionned by others, why not just make more rockets? Why does it matter if there are extra parts in your platform? They'll be there when you decide to expand it, or to repair any damage from incidents.

Because 99.99% of players do not play till they have megabases with thousands of rocket silos, hundreds levels of productivity, etc?

[crimsonarmy]

And as mentionned by others, why not just make more rockets? Why does it matter if there are extra parts in your platform? They'll be there when you decide to expand it, or to repair any damage from incidents.

Because 99.99% of players do not play till they have megabases with thousands of rocket silos, hundreds levels of productivity, etc?

You don't need a megabase. I don't know about you but I tend to have an average of a rocket every few seconds before finishing the inner planets.

(not super important but I would wager that more than 0.01% of players make megabases)

[angramania]

You don't need a megabase. I don't know about you but I tend to have an average of a rocket every few seconds before finishing the inner planets.

One rocket is 1000 science packs. 2 rockets for Gleba, one per Vulcanus and Fulgora. So if someone have in average one rocket every 15 seconds it gives him 2000 ESPM. Okay, 99.9% do not need kilobase and rocket every few seconds.

[juliawtapp]

Going through a few silos multiple times to pack requests into them more tightly probably doesn't matter in terms of UPS cost but doing so for hundreds or thousands of silos in my mind means doing all those extra steps for every single rocket silo, which i would imagine would result in hitting a performance limit much sooner than with the current system.

Can be simply solved. Just add checkbox like "use smart packing" or "pack multiple items in one rocket" and use packing algorithm only for sillos with this setting on.

And as mentionned by others, why not just make more rockets? Why does it matter if there are extra parts in your platform? They'll be there when you decide to expand it, or to repair any damage from incidents.

Because 99.99% of players do not play till they have megabases with thousands of rocket silos, hundreds levels of productivity, etc?

I feel like a checkbox that completely changes how an entity is used by the logistics network doesn't fit with how other factorio buildings feel; but that's more of an opinion than an argument for or against.

I also have never megabased, nor have I ever gotten past maybe a few levels of rocket productivity. I just end up building more rocket silos because rockets are cheap and easy to supply with logi, and why wouldn't I want new ships / outgoing cargo to be delivered faster?

I also use them for more than just science packs, so I don't have to set up a mall on every single planet. I ship everything from belts to lamps to power poles to combinators and programmable speakers.

All I'm saying is the tools exist in the game right now to avoid running into the above problem, and I feel the intent is to "just build more" and they even made rockets cheaper and simpler to make specifically to encourage it.

[crimsonarmy]

You don't need a megabase. I don't know about you but I tend to have an average of a rocket every few seconds before finishing the inner planets.

One rocket is 1000 science packs. 2 rockets for Gleba, one per Vulcanus and Fulgora. So if someone have in average one rocket every 15 seconds it gives him 2000 ESPM. Okay, 99.9% do not need kilobase and rocket every few seconds.

Why are you assuming that rockets only transport science? I have far more rockets transporting planet specific crafts (green belts, biochambers, foundries, em plants...), generic supplies that would be annoying to make locally (blue circuits for Gleba, general base supplies so there is only one mall, etc.), and even more categories.