[kovarex] [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

[BlueTemplar]

(Never mind about my issue, looks like that trains will only recalculate their paths if at a CHAIN signal, but not at a "basic" rail signal...)

The route of a train is revalidated (and recalculated if it was invalid) in the following scenarios:

• [...]
• 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 recalculate its path.
• [...]

(Missed the difference between revalidating and recalculating...)
P.S.: Thanks about reminding me about train debug tools !

[boskid]

Same issue but with final rail segment, not initial rail segment. This only affects temporary stations since target is not real train station that would split rail segment into two smaller ones:

74994-dual-case.gif (565.16 KiB) Viewed 2764 times

74994-dual-case.zip

(281.91 KiB) Downloaded 111 times

-- edit:
btw, which rail segment is considered as starting one if train at station stands on multiple rail segments? Or are there two starting segments, one for each direction, rail segment under first rolling stock for particular direction? From couple of tests it is same segment in both directions, taken as rail segment under 1/2 of distance of first rolling stock of last moving direction. Is it right?

[quale]

btw, which rail segment is considered as starting one if train at station stands on multiple rail segments? Or are there two starting segments, one for each direction, rail segment under first rolling stock for particular direction? From couple of tests it is same segment in both directions, taken as rail segment under 1/2 of distance of first rolling stock of last moving direction. Is it right?

In my small setup, the train always paths from a certain rail-relative end regardless of orientation or previous automatic/manual direction. If it’s still moving, it does prefer to maintain that direction. By end, I mean the part of the train that’s also the threshold for entering a block. I can’t think of a sensible rule to guide the search for why this is. Right now I don’t want to brute-force configurations hoping something jumps out.

Interestingly, if I have a straight segment with identical stops at the very ends, the train manages to path to the closest one. It still has a sense of distance within its starting segment. That seems to apply only in the special case where a destination station is in the starting segment. It then always picks that one no matter how far away, breaking ties correctly when there are two in the segment.

Edit:

Same issue but with final rail segment, not initial rail segment. This only affects temporary stations since target is not real train station that would split rail segment into two smaller ones:

This affects regular train stops as well. As soon as the pathfinder has found the start of a destination segment, it just goes for it. It doesn’t care that the stop is at the other end of a potentially long segment, and another segment still waiting to be evaluated might have a closer stop.

I remembered the wiki referenced some source code. Sure enough, here’s the 2017 TrainPathFinder. It’s Dijkstra’s, not A* as commonly claimed. Its priority queue is a linked list. It considers both ends of the train properly, starting at what would be considered the front pathing in each direction. It measures the entire starting segment instead of none of it as I’d assumed, explaining why I was so confused about the preferred direction. Doh!

I’ve spotted some more awkwardness I might look into later. I’m done for now.

[slippycheeze]

boskid has the right idea. The train starts pathing at the end of the segment it’s in, not counting the distance it needs to travel first to reach that end. Segments are series of connected rail pieces, delineated by switches, signals and stops. Try it with all of them. Build order can have an effect when both ends are tied.

If they are considered identically far, I would assume that build order is simply an artifact of implementation of the pathfinder. That is: it probably does control that today, but I wouldn't assume it will never change the identical path selected. Optimizations of the pathfinding code would change that, and so long as they were deterministic, everything would still work fine.

I remembered the wiki referenced some source code. Sure enough, here’s the 2017 TrainPathFinder. It’s Dijkstra’s, not A* as commonly claimed. Its priority queue is a linked list. It considers both ends of the train properly, starting at what would be considered the front pathing in each direction. It measures the entire starting segment instead of none of it as I’d assumed, explaining why I was so confused about the preferred direction.

Are you sure about your assessment that it is Dijkstra? I'd call your attention to this code here. Certainly looks like it inserts candidates based on their relative cost, the main difference between the two algorithms...

[quale]

If they are considered identically far, I would assume that build order is simply an artifact of implementation of the pathfinder. That is: it probably does control that today, but I wouldn't assume it will never change the identical path selected. Optimizations of the pathfinding code would change that, and so long as they were deterministic, everything would still work fine.

Ties in the queue are explicitly broken using the segment ID. If multiple paths converge, the first to arrive remains if the cost isn’t strictly improved. If the cost is improved, blockDistanceFromStart isn’t updated. Er. So it’s a mix of build order and effects of earlier steps.

Are you sure about your assessment that it is Dijkstra? I'd call your attention to this code here. Certainly looks like it inserts candidates based on their relative cost, the main difference between the two algorithms...

That’s where it inserts into the priority queue. Dijkstra and A* both have one. The difference is that instead of using only the cost so far as priority, A* adds a heuristic to help direct the search toward the goal. There’s no heuristic here. You could be pedantic and claim Dijkstra is a special case of A*, at best.

Of course, this is code from 2017. Some of this may no longer be true.

[mrvn]

If it's terminating as soon as it hits the destination segment then that would explain all the above cases I think. But in a real game the effect should be minimal. Usually stations have signals right before and after the train so the error would be at most a train length.

[kovarex]

Minor issue.