TL;DR
Introduce one or both of the following:- a modest penalty for segments forcing repath by being unreservable
- a small constant penalty for each train / reserved segment on the path that is independent from the segment length
I believe they could improve train throughput in multipath situations by:
- reducing lane-sticking behaviour
- minimizing number of stops at intersections
- better avoidance of existing queues and slowly dissolving traffic bottlenecks
- better distribution of trains across alternative routes in large-scale networks
- eliminating repath loops when trains get stuck at blue signals
Why?
I was having fun with multipath crossings (in this case optimizing counter-directional double roundabouts) when I noticed trains staying at blue signals at the entry point.They had a free path in front of them, still chose to stop and wait for some occupied segments to get free, doubling the time spent at the crossing as well as leaving it at a slower speed. They also reserved the highly sought parts of the intersection for a longer time, since they lost their speed when stopping and could only enter the crossing at a much lower velocity.
From my understanding, the following happens here:
- initial pathfinding: two paths exist through the crossing, the slightly shorter path is chosen.
- when arriving to the crossing, the train cannot reserve the next segment, therefore it starts to brake and repaths.
- the slightly shorter path variant is chosen again, even if that segment is blocked and requires a full brake, while the other, insignificantly longer path through the intersection would allow for immediate entry.
I assume this is caused by the 'occupied by train' penalty being vanishingly small in short rail segments (like in intersections) by having an upper limit of 2x the segment length.
What?
I think implementing some of the following adjustments could help generally improving the pathfinding algorithm:Penalty for segments that would cause braking the train by being unreservable within braking distance:
Especially, add penalty if blue chain signals would stop the train.
This would be a minor change that provides significant advantages by tweaking only the direct surroundings of the train while it has no impact on the rest of the carefully developed pathfinding algorithm.
This penalty could be velocity-based, braking from higher speeds less preferable. The efficiency loss would be better reflected if stopping a 298 km/h train had a much higher penalty than stopping a just-started 100 km/h one.
This would force fast trains to seamlessly swap to the open, slightly longer paths, while slow/stopped trains would adhere to the mathematically shortest route.
Exemplary formulas could be similar to eg. (penalty = kmh_speed / 4) or (penalty = kmh_speed / 6) based on the speed at pathfinding time.
A small constant penalty for all trains (segments occupied by other trains) on the path:
Consider eg. crossless elevated crossing designs: to keep them simple or to save on footprint area, they are often made asymmetric. Traveling straight, right and straight again leads to the same place as right, then left and right again in the rectangular train grid, but the path lengths usually differ.
More generally, paths being only marginally shorter can attract disproportionate traffic in some network topologies.
As more trains use the same route, the likelihood of future reservation conflicts increases. Once a train starts braking, queues and slowly dissolving bottlenecks can form behind it.
While all trains can break at the same time, they continue their route only one after another; chain signals and other trains waiting on incoming lanes might add further delay at putting the high-traffic rail line in motion again.
I believe that having a carefully chosen, small generic constant pathfinding penalty for trains could help achieving a better train distribution in generic large-scale networks, serving as a uniform distribution heuristic. A route with many trains is statistically more likely to develop reservation conflicts before arrival, therefore a small bias toward less utilized alternatives may improve network-wide throughput.
This penalty could more or less decrease with distance from the current position (like penalty = 15 + 15 / block-distance) but should not depend on the length of the reserved segments.
Train throughput effects
These changes could promote a more natural and fluid saturation of available routes and paths.Keeping the trains in motion would reduce travel times, path conflicts and fuel consumption.
Following designs could benefit especially:
- multipath situations like:
- multi-lane (eg. 4-lane) grids
- multipath crossings
- asymmetric intersections
- crossless (elevated rail) intersections
- roundabout intersections
- etc.
Effects on existing designs
The train network is expected to automatically find the best route, and that could be improved even on existing savefiles.I expect compatibility issues on existing designs to be marginal, since they usually do not depend on exact pathfinding route length. If they do that, usually only to balance trains by providing multiple same-length route options.
When trains should be routed only in specific directions, circuit-closed signals are the de-facto standard solution.
The proposed exemplary penalty values would be small enough to never bother with these.
Performance effects
If the train stops at an intersection, multiple repaths happen:- The train enters a new rail block and can't reserve the next needed signal.
- The train is braking for a signal it can't reserve.
- (possibly) The train has waited at a chain signal for a multiple of 5 seconds [...].
- The train wants to depart from a signal that it stopped at.
Reduced travel times mean less traffic; the intersections are occupied for a shorter time if passing through at full speed instead of accelerating from zero velocity. This could further reduce the overall amount of reservation conflicts and so the number of repath events.
In traffic jams the number of repaths scales with the number of affected trains, as well as with the number of stops per train. Since the generic train penalty could serve as a heuristic to better avoid traffic bottlenecks that might arise in the future, it could help better preserving performance and efficiency in well-dimensioned large-scale rail networks.
While the computational complexity of individual repaths would slightly increase, the overall number of repath events could decrease. Therefore the performance impacts cannot be predicted easily, but these effects could balance out each other.
Possible cons & counterarguments
Imperfect bottleneck prevention heuristicsCurrently occupied segments provide only a rough indication about future congestions; a route that seems clear might get saturated before arrival, while the congested one becomes clear.
This approach does not attempt to precisely predict future traffic situations; it is aimed at improving path selection on average by only using lightweight heuristics.
Overcorrection: All trains getting routed away from a central intersection, causing higher traffic at adjacent intersections while no traffic in the central one.
This can also be seen as a positive load-balancing effect, since the traffic is distributed to multiple crossings around the bottleneck, ideally always located nearer to the destination. As the bottleneck dissolves, more and more trains will be routed back onto the shortest route over the central intersection by repath events being part of the normal train operation.
Infinite repath oscillation
In practice, this should not be an issue. While this behaviour is probably already possible in the current version of the game, I don't think applying the proposed changes would make this scenario more or less likely.
Some scenarios might sound reasonable on first impression, but the effects will either cancel each other out or won't get applied by the pathfinding logic. The planned penalties would be both small and localized (smaller than the existing dynamic penalties like eg. the occupied-by-braking-train one).
Using pathfinding-time velocity
For the calculation, the speed at pathfinding time should be used; this counts lost efficiency instead of lost opportunities.
While this calculation works perfectly for full-speed trains, in some cases it can underestimate the efficiency loss and so the penalty value for accelerating trains. It can still provide three different path options for stopped, accelerating and full-speed trains in an otherwise identical traffic situations while being computationally easier to determine.
Better route balancing does not necessarily improve throughput
Some designs might be intentionally designed around heavily utilized main routes.
This proposal is primarily aimed at multipath situations where multiple equivalent routes are intended to serve as alternatives.
Final thoughts
The new penalties should be kept intentionally small.Trains should ideally keep using the mathematically shortest route but choose the best path if multiple similar-length ones exist.
This proposal would mostly affect pathfinding on nearby rail segments and situations where the distant alternative paths run near each other (eg. in parallel), since the game engine uses directional heuristics as part of the A* implementation.
Some of the existing penalties would optionally need a bit of redesign (possibly lowering them) to better match the new overall system. This would be an optional step requiring a little bit of testing.
Any more ideas on this?