Train path finding should not block the game (if possible), run in separate thread

Ideas that are too old (too many things have changed since) and ones which won't be implemented for certain reasons or if there are obviously better suggestions.

Moderator: ickputzdirwech

Post Reply
User avatar
AdamK
Inserter
Inserter
Posts: 47
Joined: Thu Jul 25, 2019 9:11 am
Contact:

Train path finding should not block the game (if possible), run in separate thread

Post by AdamK »

TL;DR
Train path finding should not block the game, run in separate thread

What ?
Track building/removal and trains needs some love. I guess there is a train path finding cache, but building/removing track may slow game a lot. This could be optimized in the following ways:
1) track should have a property saying: there is a path going through here
- thanks to this, track removal cost (related to path finding) should be 0, if no paths go through this part of track
- if removed track had a paths going through it, bad luck you have to invalidate at least paths going through them
2) when new track is build, there is no need to invalidate all paths immediately. It can be delayed and run in separate nonblocking thread
- yes some train will have suboptimal paths for a moment
- yes, some trains will need to have path finding run immediately if they want to go on new route
- this should be fast enough for low amount of trains/track, and with high amount of trains/track it should be good enough
3) invalidating path cache could be delayed if there is track related blueprint being built in progress (with a timeout for sure) to not redo/restart everything
each time track is built
Why ?
I'm running a base with a lot of trains (3k+) and stops (500+) and it works flawlessly (mostly 60FPS/UPS) except when I'm modifying track when FPS/UPS can drop into single digits

User avatar
NotRexButCaesar
Smart Inserter
Smart Inserter
Posts: 1120
Joined: Sun Feb 16, 2020 12:47 am
Contact:

Re: Train path finding should not block the game (if possible), run in separate thread

Post by NotRexButCaesar »

I personally would be very happy to just not consider newly placed rails for already pathed trains. Similar to train limits, trains already on their way can use the path they have, and when they repath or path again consider the new track.

Your idea of only invalidating paths that actually use the removed rail is also very good.
—Crevez, chiens, si vous n'étes pas contents!

User avatar
ssilk
Global Moderator
Global Moderator
Posts: 12888
Joined: Tue Apr 16, 2013 10:35 pm
Contact:

Re: Train path finding should not block the game (if possible), run in separate thread

Post by ssilk »

This drop happens, when you have many trains waiting on red signals. Every train tries to search for a new path, if you change something in the network. I get this only, when I have a deadlock and suddenly 100 trains are waiting to continue.

You can try to post your base here viewtopic.php?f=5&t=17501

In any case you cannot suggest how the technical implementation should work. So I move this to not implemented.
Cool suggestion: Eatable MOUSE-pointers.
Have you used the Advanced Search today?
Need help, question? FAQ - Wiki - Forum help
I still like small signatures...

User avatar
boskid
Factorio Staff
Factorio Staff
Posts: 2227
Joined: Thu Dec 14, 2017 6:56 pm
Contact:

Re: Train path finding should not block the game (if possible), run in separate thread

Post by boskid »

AdamK wrote:
Wed Feb 24, 2021 6:33 am
Train path finding should not block the game, run in separate thread
I will quote myself here (fff-364):
boskid wrote:One could simply say "make it multithreaded" but there are a lot of technical challenges to solve before this is even possible in order to not cause any issues when running in multiplayer. Basically, to ensure it will still be deterministic.
Trains pathfinder cannot run "anytime in separate thread". If there would be a construction robot placing rail somewhere on the map, if main thread would be in the middle of creating that rail and the pathfinder would run in other thread, then it would be race with 3 possible outcomes: if pathfinder would run fully before, it would not account for that rail, if it would run in parallel with construction robot update it could crash because of transient state inconsistency and if it would run after it would account for that rail which would desync if other clients in MP would get their thread to finish early.

There is lua event `on_train_changed_state` which may fire because of the repath, and because it is a lua event which may touch everything, it cannot run in parallel with anything that depends on the game state (which is basically everything).
AdamK wrote:
Wed Feb 24, 2021 6:33 am
1) track should have a property saying: there is a path going through here
That piece already exists and it is used when a rails are destroyed, however there are still checks running for most of the trains because removing rail may cause other changes that affect trains, like it may cause rail blocks to split making some signals to be no longer invalid which may need some paths to be revalidated or recomputed.
AdamK wrote:
Wed Feb 24, 2021 6:33 am
2) when new track is build, there is no need to invalidate all paths immediately. It can be delayed and run in separate nonblocking thread
That is also already a thing, however it also has a limited scope: when a rail is created it does not cause all the NO_PATH trains to immediately repath but only schedules those trains to repath within 128 ticks from now (exact tick that train will repath is based on the trainID). In other cases, building a rail may merge 2 rail blocks which will invalidate some rail signals which again needs some revalidations for trains even with a path that does not touch that rail.
AdamK wrote:
Wed Feb 24, 2021 6:33 am
3) invalidating path cache could be delayed if there is track related blueprint being built in progress (with a timeout for sure) to not redo/restart everything
each time track is built
There is no such thing as path cache, penalties for different trains will be different (like closed signal will not be considered closed for a train that has a rail block reserved behind the signal), and repath events means that literally there were changes affecting penalties so the cache (if any) would be invalidated anyway. All the pathfinder requests are done on real entities, possibly touching all the rails in the whole rails network (when there is no path, every rail reachable rail has to be touched because it could be the one missing piece to the goal).

There are some micro tweaks, like when you have a rail block that has no trains on it, has no signals anywhere on it (and is not connected to any other blocks, but that is obvious as it has no signals), removing or creating rails in that rail block will not cause any checks and repaths.

In general this topic classifies to "outdated/not implemented"

User avatar
AdamK
Inserter
Inserter
Posts: 47
Joined: Thu Jul 25, 2019 9:11 am
Contact:

Re: Train path finding should not block the game (if possible), run in separate thread

Post by AdamK »

I did not want to overstep, I just theorized on what I've seen. I also did not take MP into account at all. Devs, thanks for your detailed explanation. Factorio is brilliant :D

Post Reply

Return to “Outdated/Not implemented”