Railway/Train path finding

< 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 A*-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 caluclated 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 doesnt 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.

The route is recalculated if the train needs to stop at a signal. There is an invisible front point internally called the train_stop_point which is used to determine if the train needs to stop. See Debug mode and turn show_train_stop_point on to see that point. The route also recalculated after a train has stopped at a chain signal (if the initial repath didn't find any exits), and every five seconds after that. This is to make pathing as dynamic as possible.

History

• 0.16.0:
  • The specifc 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
• bug ticket
• Bug ticket explained