Increase bot queue processing rate

[4xel]

Okay but that doesn't help when some players put down large blue belt blueprints on a server before you can even make blue belts.

Well there is a problem with those players then. A lot of public server gat blueprint privilege for that very reason.

Making a category for blue belts does not make sense, but Thue's suggestion of having a low priority list for items that have failed once would help your case.

[punchkid]

This isn't only a problem in speedruns or server games.
Even in my factory that is in the transition phase to a "mega"base the bot delay is very noticeable. Having a setting to change this would be very nice.


And getting a mod is not something you should have to do for a core mechanic in a game.
Also mods disable achievements which is a big bummer for people like me that like achievements.

[Ajedi32]

A suggestion which should not increase update time too much, but will make construction feel much faster: Have a separate internal queue for ghosts which have little hope of being built, i.e. failed construction at least once by having no materials or in network with no total construction bots. This means that the main queue can be set to always advance at max_successful_attempts_per_tick_per_construction_queue speed.

This. A few tweaks to the scheduling algorithm could improve responsiveness a _lot_ without any significant impact to performance. Increasing the processing rate is a needlessly crude solution.

[rain9441]

Well, the thing about tweaking the scheduling algorithm is that the solutions presented are talking about determining whether or not a certain item has a certain trait or piece of data about it (little hope of being built). As far as I know, this doesn't actually exist. If you want to treat items that have failed too many times differently than items that have only failed a few times, and by what reasoning the failure was, now you need to track that data. That requires code and effort. I'm not saying it is a lot or a little code, but it sounds to me that it will require a code change.

It may be the case that changing this number from 1 to 25 makes the entire problem go away without any measurable performance hit and does so in a way that is just as efficient as a complex algorithm for 99% of cases. It only requires a value change for a property on a force. The code which uses this variable already exists, and a default value was seemingly selected arbitrarily. The value that was selected was also the utmost conservative value in existence - one failure = stop processing. You cannot be *more conservative* with a setting unless you rework it to process the bot queue only once ever second instead of every tick.

The fact that the default value is the most conservative value you can possible choose makes me believe that the simplest and most effective solution is to pick a higher default value which impacts neither performance nor gameplay. From my standpoint, this suggestion seems well received and has the highest chance of being implemented if the effort level associated with it is minimal (maximum value, minimal scope).

[ssilk]

Last night I did a test in my 100% planning practice. I changed the bot queue failure rate from 1 to a higher number mid run (10 or 100 I forget, it was not unreasonably high). It had a significant effect on the rate at which my construction bots built things (very positive!) without any sort of performance hit. Prior to the change, most bots were sitting in roboports doing nothing. As soon as I made the change, 100s of bots across multiple roboports began working furiously.

We cannot know, how they have tested the bots, what other scenarios to test changes for that numbers we are missing. I’m sure they have made a lot of tests.

Yes, It is eventually so, that we are right: it is uselessly restricted.

But I doubt that.

Okay but that doesn't help when some players put down large blue belt blueprints on a server before you can even make blue belts.

Well there is a problem with those players then. A lot of public server gat blueprint privilege for that very reason.

Making a category for blue belts does not make sense, but Thue's suggestion of having a low priority list for items that have failed once would help your case.

Would that make sense:
Instead of placing a ghost entity (which will be placed by bots) a new “planning-entity” (no better name yet). Both have similar behavior, but the main difference is, that bots will ignore planning-entities. They will never be placed by bots?

And a tool, which enables me to change a ghost into a planning-entity and back.

[ptx0]

Instead of placing a ghost entity (which will be placed by bots) a new “planning-entity” (no better name yet). Both have similar behavior, but the main difference is, that bots will ignore planning-entities. They will never be placed by bots?

And a tool, which enables me to change a ghost into a planning-entity and back.

probably need to iterate every item that spawn an entity and have a hidden item that are instantly placed and a selection tool that can convert between the placeholder entity and the real one.

a mod exists like this for Satisfactory.

[4xel]

Instead of placing a ghost entity (which will be placed by bots) a new “planning-entity” (no better name yet).

I wished I had this feature several times. I got no clue about how to integrate it well in the GUI and I think it might be a challenge.

Now it wouldn't solve all the problem related to max_attempts_per_tick_per_queue.

[ssilk]

Yes and no.

It would solve the problem, that you have ghosts, that can’t be placed yet, because they are outside of roboport-range: they become only “real” ghosts, if they are reachable. Which reduces the load for the queue a lot for big blueprints.

More of such clever things are thinkable: remove ghosts, which are in a network, where the current item is not available yet. Remove ghosts, that are not even researched yet.

I mean Factorio already might do such things already (it puts ghosts into different queues), but with that it would make it more obvious.

[ptx0]

From my testing, I changed max_failed_attempts_per_tick_per_construction_queue to 200 and max_successful_attemps_per_tick_per_construction_queue to 200. Game update went from approximately 0.900ms to 1.00ms. I changed it from 200 back to 1, and it went back to 0.900ms. I then painted a large chunk of the map with ghosts, 10's of thousands of ghosts. The peak update was 1.600ms, but usually stayed around 1.300ms. When I filled in the entire visible map with ghosts, the update time was 3.600ms. This was hundreds of thousands of ghosts with a setting of 200 instead of the default (which is 1 and 3 for successes/failures respectively).

I realize that there are many things you can do in mods in Factorio, but the mere fact that you can do something in a mod does not disqualify it from being a valid suggestion in vanilla.

I think I have shown there is evidence to support that this could be increased safely and would be a positive change to vanilla factorio.

in my system, constructionmanager update time goes from .03ms to 1.38ms just by itself on your values of 200.

it's not a great result, i have a high end system (ryzen 3700x with 2666MHz memory, CL17) and not a very large base though I've got plenty of ghosts and upgrading going on that cannot be satisfied currently.

Screenshot_20210118_095946.png (1.24 MiB) Viewed 16357 times

surely you understand why it's so low?

[blahfasel2000]

What I don't get is why failed and successful attempts are handled differently i the first place? Is a failed attempt more costly than a successful one?

At least in theory, yes, failed attempts should on average be more costly than successful attempts. For a successful attempt the game on average has to scan through half the chests (provider, storage, buffer) in the logistics network for the material, while for failed attempts due to missing material it always has to scan all chests. A similar argument applies to finding an idle bot in the network.

I haven't made any actual measurements though, so I can't say if it really makes a difference in reality as well.

[rain9441]

Failed attempts are more costly because you have to try it again. Each construction bot job has inevitably 1 successful attempt and N failed attempts. When you have all the materials in the game and the bots can build anything at any time, the processing power required is minimal. When you place huge blueprints and expect the bots to fill in the blueprint over time, the number of failed attempts rises and scales with time spent as a job. Depending on the strategy for making an attempt, it could range from processing power per second being O(n) (check every job every so many ticks) to O(1) (check one job every tick). The usual proposed middle ground is O(logn) using a strategy of exponential backoff or priority queue. My proposal is to make it O(10), which is still O(c) and less than O(logn) when n > 100.

The reason that the game allows 3 successful attempts per tick is anyone's guess. My personal guess is that 3 successful attempts per tick gives a really great graphical effect when you place a blueprint down and 100s of bots swarm out of the roboports to work - but only 3 bots per tick instead of all of them in an instant.

[ickputzdirwech]

For a successful attempt the game on average has to scan through half the chests (provider, storage, buffer) in the logistics network for the material, while for failed attempts due to missing material it always has to scan all chests.

Makes sense. On the other hand a successful attempt triggers a very costly action: A robot flying and building the entity or tile.

Failed attempts are more costly because you have to try it again.

Again, it makes sense. It only means however that failed attempts are more expensive in the long run. I am more worried about per tick performance. But the idea to prioritise things that haven’t failed that often yet would at least improve responsiveness.

[rain9441]

Per tick performance right now is just checking one job for potential matches (bots available and item available). If you check 10 jobs for potential matches each tick, it'll probably be 10 times more.

My testing showed that performance is not entirely dependent on the number of failures. More jobs existing does reduce performance. Right now if you compare 10,000 blueprinted ghosts to 100,000 blueprinted ghosts for the same failures per tick value you'll notice a difference in the update speed for the game. I also noticed a few things about the algorithm that may clue you into performance. Ghosts that aren't in any roboport range seem to have almost no impact on performance. The closest construction bot is selected for a job, not an arbitrary one, to fulfill a job, so it must take into consideration where all of the bots are across the roboport networks (It may have to look at all bots because construction zones overlap and so a job may be able to be filled by two different networks). It may or may not look for the closest bot prior to looking for items in the logistics network, I cannot tell.

If you want to know about the performance compared to other parts of the game, you can compare different values for the number of failures and just paint a bunch of items that you don't have all over the map.

[ptx0]

at 200 for both queues,

Screenshot_20210121_202240.png (104.31 KiB) Viewed 16155 times

it's pretty damn slow when i upgrade my whole base's concrete to refined.

[ssilk]

@rain: It makes no sense to grab some special case and say “in this case (my case) the bots doing it like so is much faster”. Just too simple.

The work that needs to be done with this suggestion is
- find out which cases exist
- and why this suggestion makes (most of) them faster

[Rseding91]

For anyone wanting to know the cost of increasing the processing rate: https://www.reddit.com/r/factorio/comme ... a/gbansq9/ you perform steps 1-5 for each successful attempt per-queue. You perform steps 1, 2, and 5 for each failed attempt per-queue.

[QuaBBy]

For each ghost that exists:

1. O(N) search to find a network with an overlapping construction area

-> Where N is all roboports on the ghosts force

2. O(N + log(M)) Find the closest existing available robot with the required item (if any)

-> Where N is the number of existing available robots with items of the required type

-> Where M is the number of available item types that all robots are currently carrying and want to get rid of those items

4. If no existing robot is found continue to step 5

5. O(N + log(M)) Find the nearest available source of the required item (relative to the ghost)

-> Where N is all logistic points providing the requested item

-> Where M is all item types in the logistic network

6. O(N) Find the roboport with construction robots nearest to the supply of items

-> Where N is the number of roboports

Sorry to bring this up once again, but I am genuinely hooked by this topic and just look for some answers from practical implementations. So far you guys optimized alot of stuff REALLY good. Just some questions or maybe silly mentions:

Why is the search of step 1, 5 and 6 in O(n)? Are you taking the worst case assumptions? Is it not worth optimizing in e.g. a spacial-access R-Tree? ( https://en.wikipedia.org/wiki/R-tree ). This should also help tremendously in step 5 and 6 with the nearest neighbor search from my experience. In average O(log N).

Furthermore, I think the bot queue has alot of consecutive entries of the same type ( e.g assemblers) which is not beneficial when we are missing this specific type. If the next ghost is the same type as the unsuccessful last ghost with the same roboport in step 1, i think we can skip the rest of the (expensive) steps. We won't find this type in our second attempt and can skip multiple entries rather cost efficient. It is not alot of additional memory, but speeds up bot queue tremendously if one consecutive type is skipped entirely. IMHO

Sorry if those are pretty forward remarks that you already thought of or are already implemented in a better way..

[badde_jimme]

Instead of having a queue of ghosts, it might be better to have a queue of (chunk, building_type) pairs, with each pair holding a list of ghosts that can be built of that type in a given chunk.

For instance, instead of 1024 concrete ghosts, have an entry for concrete in a specific chunk. If there are no roboports in that chunk, 1024 ghosts can be rejected in one tick. If concrete cannot be supplied to that chunk, 1024 ghosts can be rejected in one tick. If there are no construction robots available for that chunk, 1024 ghosts can be rejected in one tick.

And we can reject a chunk's worth of inserters in one tick, or belts, or assemblers etc.

[rain9441]

I didn't want to get into complex solutioning as Rseding and other developers at Wube have demonstrated extraordinary skillsets and success in this area. I still would like this suggesting to be the simple idea of increasing the basic number of attempts per tick. I know that strikes most developers as bad, but from a practical standpoint it very well could be the ideal solution as it does not introduce new complexity, nor does it increase management of custom data structures, nor have an additional memory footprint.

I do have one other idea which is to resort the queue every iteration of it by repositioning every job randomly within the list. This would increase bot productivity in many cases because of how placing a giant blueprint leaves the jobs in one section of the queue - creating a "dark age" so to speak. In my 100% speedruns I have been doing this manually by cutting out blueprints and pressing undo every few seconds. By doing that act, it distributes large chunks of ghosted entities throughout the queue reducing the maximum amount of time between processing of an entity for a given roboport.

[ptx0]

roboport networks on different forces should update in parallel.