In other languages: Deutsch

Railway/Train path finding: Difference between revisions

From Official Factorio Wiki
Jump to navigation Jump to search
No edit summary
(Updated info)
Line 1: Line 1:
{{Languages}}
{{Languages}}
{{sublinks}}
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 caluclated using the following weighting rules:
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:
* 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 block distance from the start, so the far away occupied paths don't matter much.
Line 9: Line 8:
* When the path includes a train stop that is not the destination -> Add a penalty of 2000.
* 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 -> 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 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 -> 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 manually controlled stopped train without a passenger -> Add a penalty of 7000.
Line 15: Line 14:
* When the path includes a train currently arriving to a rail signal -> 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 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 (possibly including the destination) is recalculated if the train needs to stop at a signal or if is current destination is disabled or destroyed. 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 when leaving a stop, and 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.
The route of a train is recalculated in the following scenarios:
* A locomotive that is part of the train is rotated. The train is forced to make a new path.
* [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 make a new path.
* 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 make a new 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 make a new path.
* The train doesn't have a path and a rail gets created.
* A rail gets created and invalidates a signal along the train's path. The train is forced to make a new path.
* A rail block changes and invalidates a signal along the train's path. The train is forced to make a new path.
* A rail signal 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 or arriving at a station.
* The train is preparing to stop at a red signal that changes to no longer be red. The train is forced to make a new path.
* The train encounters a red signal and the train is not inside a chain signal block. The train is forced to make a new 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 make a new path.
* The train wants to depart from a signal that was red. The train is forced to make a new path.
* If the train doesn't have a path, the path is recalculated every 128 ticks.
* The train enters a new non-chain-signal block and can't reserve the next needed signal. The train is forced to make a new path.
* The train collides with something that is not a train (like a player). The train is forced to make a new path.
* The train is pathing to a train stop that gets disabled. The train is forced to make a new path.
* The train doesn't have a path and a train stop that is in its schedule gets enabled.


== History ==
== History ==


{{History|0.16.0|
{{History|0.16.0|
* The specifc penalties can now be found in the utility constants, which allows mods to change them. (Undocumented)}}
* The specific penalties can now be found in the utility constants, which allows mods to change them. (Undocumented)}}


{{History|0.15.0|
{{History|0.15.0|
Line 39: Line 64:
* [https://gist.github.com/Rseding91/c0d4d08d6feaed618ed4a03f6c6a8fe6 Train pathfinding as of version 0.16 (Code)]
* [https://gist.github.com/Rseding91/c0d4d08d6feaed618ed4a03f6c6a8fe6 Train pathfinding as of version 0.16 (Code)]
* [https://www.factorio.com/blog/post/fff-68 FFF #68]
* [https://www.factorio.com/blog/post/fff-68 FFF #68]
* [https://forums.factorio.com/viewtopic.php?f=30&t=4834 bug ticket]
* [[Railway]]
* [https://forums.factorio.com/viewtopic.php?f=30&t=2237#p62195 Bug ticket explained]

Revision as of 21:27, 4 October 2018

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 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 recalculated 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 make a new path.
  • 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 make a new 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 make a new path.
  • The train doesn't have a path and a rail gets created.
  • A rail gets created and invalidates a signal along the train's path. The train is forced to make a new path.
  • A rail block changes and invalidates a signal along the train's path. The train is forced to make a new path.
  • A rail signal 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 or arriving at a station.
  • The train is preparing to stop at a red signal that changes to no longer be red. The train is forced to make a new path.
  • The train encounters a red signal and the train is not inside a chain signal block. The train is forced to make a new 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 make a new path.
  • The train wants to depart from a signal that was red. The train is forced to make a new path.
  • If the train doesn't have a path, the path is recalculated every 128 ticks.
  • The train enters a new non-chain-signal block and can't reserve the next needed signal. The train is forced to make a new path.
  • The train collides with something that is not a train (like a player). The train is forced to make a new path.
  • The train is pathing to a train stop that gets disabled. The train is forced to make a new path.
  • The train doesn't have a path and a train stop that is in its schedule gets enabled.

History

  • 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=164664"