In other languages: Deutsch

Railway/Train path finding: Difference between revisions

From Official Factorio Wiki
Jump to navigation Jump to search
m (updated for 0.17.38 (tested in 0.17.55 at least). note that the recalculation is not instant, but takes around half a second (a train was observed decelerating from ~210km/h to ~160km/h before rerouting and accelerating again))
mNo edit summary
 
(27 intermediate revisions by 6 users not shown)
Line 2: Line 2:
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.
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 [[WIKIPEDIA:A*_search_algorithm|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 calculated using the following weighting rules:
== Path finding penalties ==
 
For calculation it uses a simple [[WIKIPEDIA:A*_search_algorithm|A*-algorithm]]<sup>[https://www.factorio.com/blog/post/fff-331]</sup>: 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).
* 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 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 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 -> 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 rail block contains a train that is stopped at a train stop -> 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 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 path includes a manually controlled stopped train -> Add a penalty of 2000.
* When the rail block contains a manually controlled stopped train with a passenger -> Add a penalty of 2000.
* When the path includes a manually controlled stopped train without a passenger -> Add a penalty of 7000.
* When the rail block contains 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 rail block contains an automatic train without a schedule -> Add a penalty of 7000.
* When the path includes a train currently arriving to a rail signal -> Add a penalty of 100.
* When the rail block contains a train currently arriving to a train stop -> 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 rail block contains a train currently arriving to a rail signal -> Add a penalty of 100.
* When the path includes a train that doesn't have a path -> Add a penalty of 1000.
* 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.


The route of a train is revalidated (and recalculated if it was invalid) in the following scenarios:
== Path Revalidation ==
* A locomotive that is part of the train is rotated. The train is forced to make a new path.
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.  
* [https://lua-api.factorio.com/latest/LuaTrain.html#LuaTrain.recalculate_path LuaTrain::recalculate_path()] is called on the train by script. The train can be forced to recalculate its path regardless of validity.
The following events cause path revalidation:
* 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.
* A rail is destroyed (all trains are revalidated).
* The train is pathing to a train stop that gets destroyed. The train is forced to make a new path.
* A rail is created and invalidates a signal (all trains are revalidated) .
* A rail which is part of the train's path gets destroyed.
* A signal (chain or regular) is created or destroyed  (all trains are revalidated).
** If the rail is the destination of the path, the train is forced to recalculate its path.
* A rail block changes and invalidates a signal (chain or regular) (all trains are revalidated).
* The train doesn't have a path and a rail gets created.
* [https://lua-api.factorio.com/latest/LuaTrain.html#LuaTrain.recalculate_path LuaTrain::recalculate_path()] is called on the train by a script.
* 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'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.
* [https://lua-api.factorio.com/latest/LuaTrain.html#LuaTrain.recalculate_path 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 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 set to go to a station using the "Go to stop" button in the train's GUI.
* 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.
* A waypoint (train stop without wait condition) is removed from the train's schedule.
* The train starts braking for a signal (chain or regular) it cant reserve. The train is forced to recalculate its path.
 
=== 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 wants to depart from a train stop.
* The train has waited at a chain signal for a multiple of 5 seconds.
* The train is pathing to a train stop that gets disabled.
** 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.
=== Destination full / No path trains ===
* If the train doesn't have a path, the path is recalculated every 128 ticks.
* A rail gets created.
* The train enters a new block and can't reserve the next needed signal (chain or regular). The train is forced to recalculate its path.
* A train stop that is part of the train's schedule gets enabled, renamed or created.  
* The train collides with something that is not a train (like a player). The train is forced to recalculate its path.
* The train limit of a train stop that is part of the train's schedule becomes not full.
* The train is pathing to a train stop that gets disabled. The train is forced to recalculate its path.
* The train stop that it currently cannot reach gets disabled or destroyed.
* The train doesn't have a path and a train stop that is in its schedule gets enabled.
 
=== Others ===
* The train collides with something that is not a train (like a player).


== History ==
== History ==
{{History|0.18.1|
* Train stop at train's starting segment exit is no longer counted into penalty. (Not mentioned above)}}


{{History|0.17.38|
{{History|0.17.38|
Line 68: Line 89:
== See also ==
== See also ==


* [https://gist.github.com/Rseding91/c0d4d08d6feaed618ed4a03f6c6a8fe6 Train pathfinding as of version 0.16 (Code)]
* [https://gist.github.com/Rseding91/c0d4d08d6feaed618ed4a03f6c6a8fe6 Train pathfinding code]
* [https://www.factorio.com/blog/post/fff-331 FFF #331]
* [https://www.factorio.com/blog/post/fff-68 FFF #68]
* [https://www.factorio.com/blog/post/fff-68 FFF #68]
* [[Railway]]
* [[Railway]]
{{C|Railway{{!}}#Railway/Train path finding}}

Latest revision as of 18:29, 17 May 2024

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

Retrieved from "https://wiki.factorio.com/index.php?title=Railway/Train_path_finding&oldid=198353"