How is a train's path calculated?

[SilverB1rd]

I was watching the Xterminator, colonelwill, and mojo stream and they were having issues introduced by the train pathing. If I recall correctly Rseding91 was talking in the chat about the algorithm used to do train pathing, saying it was mainly bound up in the visited nodes handling, using some variant of A* for the base algorithm.

I setup a basic reference track to help my understanding of what the game has to work with.


Enabling some of the debug information shed some light on how the game chunks the track sections


Are optimizations like caching routes, or simplifying the node graph for continuous sections, done behind the scenes?

Are there specific things that would help you out, like code examples or sample algorithms? Are there specific constraints that need to be satisfied?

[Tami]

Path detection is dependant of the path and the blocks:

For example a train blocking a route lowers this route, so trains will move another way if possible.
Some works for circtui blocked routes. if you blocke a while segment because you want to move on the rails to build stuff, the train will move another route if possible, if not train just waits.

If you use more circuit blocked signals in a row, for example 3 signals blocked by same circuit, then the route the alternate max distance can be further increased. For example if you have a short distance of 20 units (rails), but you block the route with 6 circuit signals, the train will even use a path with a distance of 1000+ units.

You even can loop a train in an endless loop until the train runs out of fuel by continius changing the circuit signals.

[SilverB1rd]

https://www.factorio.com/blog/post/fff-68

This fff post contains some information on weights used to calculate alternative routes. It sounds like trains will calculate the route when they leave the station, but also they can recalculate while in route. What can cause a train to recalculate mid route?

Maybe one optimization would be to save the routes at the stations.

From any station a to any station b for which a schedule exists station A caches the shortest route, when a train is leaving the station it checks the station's cache for the shortest route to station b.

The train could then verify if the route is still desirable, each node in the route is under a congestion threshold. This could reduce the number of path recalculations because it would cache routes by station instead of by train, two stations serving ten trains would have only need two cached routes. The check to determine if the route is still desirable would be the number of nodes between each station, or o(n), regardless of the size of the graph.

This could would have to deal with some complexity for routes that have multiple destinations to choose from.

[Yoyobuae]

https://www.factorio.com/blog/post/fff-68

This fff post contains some information on weights used to calculate alternative routes. It sounds like trains will calculate the route when they leave the station, but also they can recalculate while in route. What can cause a train to recalculate mid route?

When the train "sees" a red signal blocking the chosen route. A train only "sees" as far as it's braking point. So a slow moving train is effectively nearsighted, while a fast moving train looks way ahead.

Note that the train "seeing" a red signal doesn't mean the train can't still choose the same path again. If the path thru the red signal happens to be the "best" path the train will choose to wait at the red signal. A path to a train stop with no red signals in the way is "better" to a path with some red signals (to an extend).

Also when a train is stopped at a red rail signal and the signal turns green.

I made this little demonstration using the above principles:
https://youtu.be/AhlsS4uNwh0

At each split the train either decides to go right into the "outpost" or continue forward. The train stop pairs along the main line are needed to ensure trains have a clear path to a target station if the outpost happens to be closed (because a train is already there). The trains have only two stops in their schedule, so a pair of train stops reset their schedule back to what it was.

[SilverB1rd]

Note that the train "seeing" a red signal doesn't mean the train can't still choose the same path again. If the path thru the red signal happens to be the "best" path the train will choose to wait at the red signal. A path to a train stop with no red signals in the way is "better" to a path with some red signals (to an extend).

Also when a train is stopped at a red rail signal and the signal turns green.

Every Red signal causes a repath? Would it be a full or partial repath? Does it look for the shortest path around the blockage or does it repath all the way to the destination?

[Yoyobuae]

Note that the train "seeing" a red signal doesn't mean the train can't still choose the same path again. If the path thru the red signal happens to be the "best" path the train will choose to wait at the red signal. A path to a train stop with no red signals in the way is "better" to a path with some red signals (to an extend).

Also when a train is stopped at a red rail signal and the signal turns green.

Every Red signal causes a repath? Would it be a full or partial repath? Does it look for the shortest path around the blockage or does it repath all the way to the destination?

Yes, but only red signals that would force the train to stop and it only happens when the train would need to start braking to stop at that red signal. It's a full repath all the way to the destination train stop(s).

If the potential target train stop is far a way then the entire path to the stop has an effect on the path selection. That's why in the video above I placed train stops inline with the main rail line, to have more control over the train pathing (shorter distances, fewer signals, can guarantee a free path before letting train move into the split, etc).