Railway/Train path finding: Difference between revisions
Jump to navigation
Jump to search
(→See also: yay for rseding) |
(updated to 0.16, added things from the code) |
||
| Line 4: | Line 4: | ||
For calculation it uses a simple A*-algorithm, with the following special weighting-rules (see [https://gist.github.com/Rseding91/c0d4d08d6feaed618ed4a03f6c6a8fe6 the posted path-finding code]): | For calculation it uses a simple A*-algorithm, with the following special weighting-rules (see [https://gist.github.com/Rseding91/c0d4d08d6feaed618ed4a03f6c6a8fe6 the posted path-finding code]): | ||
* Base cost for a block/segment is the length of the segment. | |||
* 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. | ||
* 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 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. 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 on a signal. This is to make pathing as dynamic as possible. | The route is recalculated if the train needs to stop. 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 on a signal. This is to make pathing as dynamic as possible. | ||
Revision as of 11:37, 30 December 2017
< 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, with the following special weighting-rules (see the posted path-finding code):
- Base cost for a block/segment is the length of the segment.
- 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. 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 on a signal. This is to make pathing as dynamic as possible.
History
- 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.