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.

Path finding penalties

For calculation it uses a simple A*-algorithm^[1]: 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 the number of blocks 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 -> Add a penalty of 2000.
• When the rail block contains a train that is stopped at a train stop -> Add a penalty of 500.
• When the rail block contains a train that is stopped at a train stop and the train doesn't have other valid stops in its schedule -> Add a penalty of 1000.
• When the rail block contains a manually controlled stopped train with a passenger -> Add a penalty of 2000.
• When the rail block contains a manually controlled stopped train without a passenger -> Add a penalty of 7000.
• When the rail block contains an automatic train without a schedule -> Add a penalty of 7000.
• When the rail block contains a train currently arriving to a train stop -> Add a penalty of 100.
• When the rail block contains a train currently arriving to a rail signal -> Add a penalty of 100.
• When the rail block contains 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 rail block contains a train that doesn't have a path -> Add a penalty of 1000.

Path Revalidation

A rail path will be revalidated if any event happens that could make this trains path invalid. If the path is found to be invalid then the game will repath the train. Path revalidation just confirms that the current path is still valid and does not confirm that it is still the best. The following events cause path revalidation:

• A rail is destroyed (all trains are revalidated).
• A rail is created and invalidates a signal (all trains are revalidated) .
• A signal (chain or regular) is created or destroyed (all trains are revalidated).
• A rail block changes and invalidates a signal (chain or regular) (all trains are revalidated).
• LuaTrain::recalculate_path() is called on the train by a script.
• The train's schedule is changed.
• 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 has waited at a chain signal for a multiple of 5 seconds.

Repath events

There are a number of events that can cause a train to repath listed below. When one of these conditions is met the game considers possible paths from the train's current location to any train stop matching the destination name in the train's schedule and will chose the path with the lowest score according to the penalties listed above.

User / script generated events

• A locomotive that is part of the train is rotated.
• LuaTrain::recalculate_path(true) is called on the train by a script.
• The train is switched to automatic control when it was previously manually controlled.
• The train is set to go to a station using the "Go to stop" button in the train's GUI.
• A waypoint (train stop without wait condition) is removed from the train's schedule.

Repaths that happen as part of normal train operation

• A train fails a revalidation.
• The train stop a train is heading to is renamed or destroyed.
• The train is preparing to stop at a signal (chain or regular) that changes so that the train can now continue.
• The train is braking for a signal (chain or regular) it cant reserve.
• The train enters a new rail block and can't reserve the next needed signal (chain or regular).
• The train has waited at a chain signal for a multiple of 5 seconds and there are multiple train stops with the same name as the destination.
• The train has waited at a chain signal for a multiple of 30 seconds and there is only a single train stop with the same name as the destination.
• The train wants to depart from a signal (chain or regular) that it stopped at.
• The train wants to depart from a train stop.
• The train is pathing to a train stop that gets disabled.

Destination full / No path trains

• A rail gets created.
• A train stop that is part of the train's schedule gets enabled, renamed or created.
• The train limit of a train stop that is part of the train's schedule becomes not full.
• The train stop that it currently cannot reach gets disabled or destroyed.

Others

• The train collides with something that is not a train (like a player).

History

• 0.18.1:
  • Train stop at train's starting segment exit is no longer counted into penalty. (Not mentioned above)

• 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 code
• FFF #331
• FFF #68
• Railway