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

[boskid]

train-suboptimal-path-finding-setup.zip

(276.67 KiB) Downloaded 191 times

setup-1.png (310.08 KiB) Viewed 7864 times

setup-2.png (15.33 KiB) Viewed 7864 times

Issue:

path-with-curved-track.png (18.28 KiB) Viewed 7864 times

Expected:

path-without-curved-track.png (15 KiB) Viewed 7864 times

Issue is with this small curved rail section that is not connected. Removing it gives proper, short path. Issue is independent of true train direction.

[Jon8RFC]

Interesting. I did a similar test, and it has to do with where the train is with respect to the track divergence:
https://youtu.be/vlaE-srbSiU

Once the train passes the track divergence (which happens to be in the case above), longer paths happen. It doesn't have to be a single track, even a shorter, full loop inside the main loop performs the same function of forcing the shortest route, so long as the train hasn't passed the divergence.

It seems like it's a matter of the track breaking up whatever it thinks are contiguous tracks, and where the train is with respect to it.

EDIT:
Quick follow-up, if it's helpful to show a different breaking up of the tracks situation location which can't be accessed by the train's path:
https://youtu.be/Jcz-HSyf5x8

[boskid]

Right, it is not intersection. It is purely this track. In your video it is not even dead-end. There is something fishy here.

Here is opposite case - shorter path when there is this additional curved rail segment. This can be explained as "pathfinding does not like rail merge points", but why in this case there is longer path when there is only this basic merge point from loop(2 rails) and to station (1 rail)?

74994-opposite-case.gif (324.5 KiB) Viewed 7682 times

74994-opposite-case.zip

(223.85 KiB) Downloaded 192 times

[Jon8RFC]

To add to that, the direction of the track divergence doesn't matter--whether or not the current possible paths can even use the extra track--just the fact of having a divergence is what makes things different.

[mrvn]

To add to that, the direction of the track divergence doesn't matter--whether or not the current possible paths can even use the extra track--just the fact of having a divergence is what makes things different.

Does the train direction matter? What if you place the back locomotive first so the train faces the other way?

[Jon8RFC]

They're double-headed, and I tested setting the "automatic" from either train, so I think the trains themselves aren't relevant. Their positions on the track, the length of the track and WHERE the divergences are, are relevant.

New info...

The length of the track with regard to the divergences can matter, because one divergence causes longer pathing, but another doesn't:
https://youtu.be/nxuo7AJDn2U

So, it's a strange path penalty thing, given this video?

EDIT:
I thought maybe it was a matter of canceling the divergences out (odd vs even number of divergences), but I couldn't quite make sense of it and accidentally happened upon the situation in this video. I wonder if various divergences throughout the track would create new "paths" (not real ones, but it creates a penalty?), and you could create a whole slew of calculations which are unnecessary, harming UPS. Could many unfinished or partially-removed be causing not only strange paths, but also unnecessary calculations?

[Jon8RFC]

And to add a little more confusion, train position matters even in a simple loop without divergences. The "shortest" path chosen seems incorrect, and it varies:
https://youtu.be/wQvdvj4zz0g

[boskid]

And to add a little more confusion, train position matters even in a simple loop without divergences.

Well, what you did (accidently removed some rails) fits my observation: rail building order matters. Sometimes when this setup does not give longer path, i just remove one rail segment for short path and rebuild it again (most often curved rail from merge point).

Also interesing observation here: rail signal does not affect what path is taken, however train stations prevent this issue from happening. Here is also additional quirk: if train leaves station, station it departs also counts for "station not on path" penalty and train will choose path that is not going through this station.

[boskid]

74994-build-order-matters.zip

(391.26 KiB) Downloaded 202 times

Same setup twice with equal "train station" penalty when going pass station or going in reverse. Train in upper setup chooses to go past station C (short path), while train i lower setup chooses longer path. Because of this i suspect that pathfinding is working fine, but is not counting distance penalty of first rail segment from which train starts from. All other artifacts may be just due to "rest of path is same, choose based on build order since cost for rest of path is same"

[Jon8RFC]

What about this situation?
https://youtu.be/nxuo7AJDn2U?t=26

Haha, I just realized that my clips all have the partypoker247 audio in the background I'm watching on my secondary monitor, sorry.

[boskid]

What about this situation?
https://youtu.be/nxuo7AJDn2U?t=26

Haha, I just realized that my clips all have the partypoker247 audio in the background I'm watching on my secondary monitor, sorry.

It still counts as "build order matters". I am not saying that train will choose path that was build first/last. By building some curved rails you may affect internal rail ID's or something that is used when sorting edges in path graph (sorting or other means are required for determinism - so there is no case that in one player's game, train would choose path A and other in others path B because they have same cost but player A built this setup and player B joined game after).

Since both setups have same cost when counting beyond line of stations C/not-on-path my first assumption is that path cost does not count cost of first segment, that is from train to next vertex on path graph. Proof for this: if you move not-on-path station 2 tiles to right, it is not possible to force train to choose lower path (since beyond station this path is 2 tiles longer), and if C station is 2 tiles to right (comparing to not-on-path station), it is not possible to force train to go past station C. I think only explanation for this is first rail section (on which train is standing) is not considered towards path cost.

-- edit:
With this explanation, lets test if it is correct (or at least, if there are any couterexamples):
https://youtu.be/vlaE-srbSiU - when video starts, there are 3 merge points (vertex). Upper, left, and lower. Right where train is standing, track(track=many rails in one line) is connect to upper and lower merge points. However lower merge point is closer to train station and this is why train chooses longer path (assuming cost of first track is not counted). When you remove lower merge point, this difference gets even larger: now track connects only to upper and middle merge point. Choosing longer path still is better since middle merge point is closer to station

https://youtu.be/Jcz-HSyf5x8 - same here. Since this dead-end-curved-rail is placed where it is, there are 2 merge points. Left (long track goes here from bottom) and right (curved rail enters here). Long track goes into both of them (from up into right merge, from down into left merge). Left merge point is closer to destination and so train chooses long path since it does not count for distance it must travel on initial track. "short path" is here longer by 2 tiles, since its cost starts on right merge point.

https://youtu.be/nxuo7AJDn2U - also fits this description. First two branches created merge points that are still closer to station. Third one however made merge point that is farther from destination than upper initial merge point.

Case from initial post: same as second video. Long path has 2 units lower cost since it connects to left merge point, where "short path" ends in right merge point (2 units higher cost)

74994-opposite-case.gif - also fits. When there is no branch, train sees two paths that are equal in cost and so chooses based on build order (and some internal details). When there is this additional branch, "long path" finally costs more since it ends in merge point for this branch and this merge point is farther (higher cost) from target.

-- edit:
With this explanation it is clear why train must be two-headed. If train can go only one direction, counting this extra cost (from train head to first vertex on train network graph) would increase cost of every path and so it would cancel out ("a<b" is same as "a+c < b+c" [if no overflows]). However if train can go in each direction (two locomotives in opposite directions), this initial cost may be different based on direction train chooses.

[mrvn]

They're double-headed, and I tested setting the "automatic" from either train, so I think the trains themselves aren't relevant. Their positions on the track, the length of the track and WHERE the divergences are, are relevant.

Every train has a front and a back. In a double-headed train one locomotive faces front and one back and the train can drive forward and backward. But it still has a front that's unchanging.

Now if the code runs A* for the forward direction first and backward second the direction the train is facing might very well matter.

PS: What about a train with all but one locomotive facing one direction? Will it weigh the paths in both direction according to the acceleration and resistance for each direction? A longer path might be quicker with more locomotives pulling.

[BlueTemplar]

The game might also just pick one of the locomotives, try to pathfind, and not even trying to pathfind from another one if it manages to find a path with the first ?

Might explain why I get trains stuck like this :

Screenshot from 2019-08-26 14-25-33.png (3.82 MiB) Viewed 7588 times

(Note that they are on a loop, so can come in/out from either side.)

[mrvn]

And it might prefer the direction the train moved in last instead of front.

[Jon8RFC]

How do I determine which locomotive is the front? Is it just the first one put down?

[boskid]

They're double-headed, and I tested setting the "automatic" from either train, so I think the trains themselves aren't relevant. Their positions on the track, the length of the track and WHERE the divergences are, are relevant.

Every train has a front and a back. In a double-headed train one locomotive faces front and one back and the train can drive forward and backward. But it still has a front that's unchanging.

Now if the code runs A* for the forward direction first and backward second the direction the train is facing might very well matter.

PS: What about a train with all but one locomotive facing one direction? Will it weigh the paths in both direction according to the acceleration and resistance for each direction? A longer path might be quicker with more locomotives pulling.

This should answer both of your questions: train behaves same in both directions and loco count is not considered for cost.

74994p453575-answer.gif (6.65 MiB) Viewed 7585 times

And this is what happens if i rebuild some rails so that lower path is preferred on same cost:

74994p453575-answer-2.gif (3.49 MiB) Viewed 7581 times

74994p453575-answer-3.gif (3.43 MiB) Viewed 7581 times

[mrvn]

They're double-headed, and I tested setting the "automatic" from either train, so I think the trains themselves aren't relevant. Their positions on the track, the length of the track and WHERE the divergences are, are relevant.

Every train has a front and a back. In a double-headed train one locomotive faces front and one back and the train can drive forward and backward. But it still has a front that's unchanging.

Now if the code runs A* for the forward direction first and backward second the direction the train is facing might very well matter.

PS: What about a train with all but one locomotive facing one direction? Will it weigh the paths in both direction according to the acceleration and resistance for each direction? A longer path might be quicker with more locomotives pulling.

This should answer both of your questions: train behaves same in both directions and loco count is not considered for cost.
74994p453575-answer.gif

What are the station names? I assume it's:

Code: Select all

       /--A--\
A-B---<       |
       \--A--/

Considering both directions the train should then always drive between the two left most stations (even with the locomotive unbalance I think). Instead it prefers the direction it traveled last.

[boskid]

What are the station names? I assume it's:

Code: Select all

       /--A--\
A-B---<       |
       \--A--/

Considering both directions the train should then always drive between the two left most stations (even with the locomotive unbalance I think). Instead it prefers the direction it traveled last.

Just download and tinker with this:

74994-build-order-matters.zip

Same setup twice with equal "train station" penalty when going pass station or going in reverse. Train in upper setup chooses to go past station C (short path), while train i lower setup chooses longer path. Because of this i suspect that pathfinding is working fine, but is not counting distance penalty of first rail segment from which train starts from. All other artifacts may be just due to "rest of path is same, choose based on build order since cost for rest of path is same"

[boskid]

How do I determine which locomotive is the front? Is it just the first one put down?

My way of doing this: enable "show-debug-info-in-tooltips". While train is moving, if you hover mouse over train, you will see "riding state" changing. By its values you will be able to check if train is going straight or in reverse. In this bug report, every test i did was not affected by train internal direction.

[quale]

boskid has the right idea. The train starts pathing at the end start of the segment it’s in, not counting the distance it needs to travel first to reach that end counting the entire segment no matter where it is in the segment. 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.