Railway/Train path finding

Before a train moves to a target (in this case, a Train stop), it calculates the best route based on the railway network at that time.

For calculation it uses a simple Dijkstra's algorithm: The pathfinder first builds a list of non-disabled stops that match the name in the schedule, then searches outward from both ends of the train at once, if applicable, in segments. A segment is an uninterrupted plain sequence of rails, with no intersections, stops, or signals (all of which define segment borders). The cost (distance) is calculated using the following weighting rules:

• Base cost for a block/segment is the length of the segment (linear grid length along the center of the rail).
• When the rail block is occupied by a train -> Add a penalty of 2 * length of the block divided by block distance from the start, so the far away occupied paths don't matter much.
• When the rail block is guarded by a rail signal set to red by the circuit network -> Add a penalty of 1000.
• When the path includes a train stop that is not the destination -> Add a penalty of 2000.
• When the path includes a train stop with a train stopped in it -> Add a penalty of 500.
• When the path includes a train stop with a train stopped in it that doesn't have other valid stops in its schedule -> Add a penalty of 1000.
• When the path includes a manually controlled stopped train -> Add a penalty of 2000.
• When the path includes a manually controlled stopped train without a passenger -> Add a penalty of 7000.
• When the path includes a train currently arriving to a train stop -> Add a penalty of 100.
• When the path includes a train currently arriving to a rail signal -> Add a penalty of 100.
• When the path includes a train currently waiting at a rail signal -> Add a penalty of 100 + 0.1 for every tick the train has already waited.
• When the path includes a train that doesn't have a path -> Add a penalty of 1000.

The route of a train is revalidated (and recalculated if it was invalid) in the following scenarios:

• A locomotive that is part of the train is rotated. The train is forced to make a new path.
• LuaTrain::recalculate_path() is called on the train by script. The train can be forced to recalculate its path regardless of validity.
• The train does not have a path and a train stop that is part of train's schedule gets renamed or created. The train is forced to recalculate its path.
• The train is pathing to a train stop that gets destroyed. The train is forced to make a new path.
• A rail which is part of the train's path gets destroyed.
  • If the rail is the destination of the path, the train is forced to recalculate its path.
• The train doesn't have a path and a rail gets created.
• A rail gets created and invalidates a signal (chain or regular) along the train's path. The train is forced to recalculate its path.
• A rail block changes and invalidates a signal (chain or regular) along the train's path. The train is forced to recalculate its path.
• A signal (chain or regular) gets destroyed or created.
• The train is set to go to a station using the "Go to stop" button in the train's GUI.
• The train's schedule is changed.
• The train is switched to automatic control when it was previously manually controlled.
• The train's braking force gets changed and the train is currently driving normally, arriving at a signal (chain or regular) or arriving at a station.
• The train is preparing to stop at a signal (chain or regular) that changes so that the train can now continue. The train is forced to recalculate its path.
• The train is braking for a signal (chain or regular) it cant reserve and the train is not inside a chain signal block. The train is forced to recalculate its path.
• The train wants to depart from a train stop.
• The train has waited at a chain signal for a multiple of 5 seconds.
  • If the trains has waited for a multiple of 30 seconds or if multiple train stops with the name of the destination exist, the train is forced to recalculate its path.
• The train wants to depart from a signal (chain or regular) that it stopped at. The train is forced to recalculate its path.
• If the train doesn't have a path, the path is recalculated every 128 ticks.
• The train enters a new rail block and can't reserve the next needed signal (chain or regular). The train is forced to recalculate its path.
• The train collides with something that is not a train (like a player). The train is forced to recalculate its path.
• The train is pathing to a train stop that gets disabled. The train is forced to recalculate its path.
• The train doesn't have a path and a train stop that is in its schedule gets enabled.

History

• 0.17.38:
  • When a train performs path finding while in a chain signal sequence, the pathfinding will have a constraint to not go through reserved block before exiting the chain sequence. This solves a problem of train intersections being possible to be deadlocked even with proper chain signals usage in cases of using temporary stops or when path is changed because of station is being enabled/disabled by a circuit network. This also allowed us to to let train recalculate path spontaneously even in chain signal sequence, as it shouldn't break anything now.

• 0.16.42:
  • Added train path finding penalty for train with no path equal to 1000 tiles

• 0.16.0:
  • The specific penalties can now be found in the utility constants, which allows mods to change them. (Undocumented)

• 0.15.0:
  • Train station adds 2000 tiles penalty when path finding, so trains try to avoid stations not related to their path.

• 0.11.17:
  • Increased the pathing penalty for non-moving train in manual mode from 200 to 1000.

• 0.11.13:
  • Stopped, manually controlled train adds additional penalty (related to train path finding) of 200 tiles to the block it occupies.

• 0.11.11:
  • The pathfinding is based on penalties for blocked segments now. For trains waiting in station, the more remaining time in the station, the bigger penalty.

See also

• Train pathfinding as of version 0.16 (Code)
• FFF #68
• Railway