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

We are aware of them, but they have low priority. We have more important things to do. They go here in order not to take space in the main bug thread list.
User avatar
boskid
Factorio Staff
Factorio Staff
Posts: 2821
Joined: Thu Dec 14, 2017 6:56 pm
Contact:

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

Post by boskid »

train-suboptimal-path-finding-setup.zip
(276.67 KiB) Downloaded 158 times
setup-1.png
setup-1.png (310.08 KiB) Viewed 6750 times
setup-2.png
setup-2.png (15.33 KiB) Viewed 6750 times
Issue:
path-with-curved-track.png
path-with-curved-track.png (18.28 KiB) Viewed 6750 times
Expected:
path-without-curved-track.png
path-without-curved-track.png (15 KiB) Viewed 6750 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.

User avatar
Jon8RFC
Filter Inserter
Filter Inserter
Posts: 554
Joined: Tue May 10, 2016 3:39 pm
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by 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
Attachments
jon8rfc_train_test.zip
(1.66 MiB) Downloaded 183 times
Last edited by Jon8RFC on Thu Aug 29, 2019 11:28 am, edited 1 time in total.
Image

User avatar
boskid
Factorio Staff
Factorio Staff
Posts: 2821
Joined: Thu Dec 14, 2017 6:56 pm
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by 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
74994-opposite-case.gif (324.5 KiB) Viewed 6568 times
74994-opposite-case.zip
(223.85 KiB) Downloaded 162 times

User avatar
Jon8RFC
Filter Inserter
Filter Inserter
Posts: 554
Joined: Tue May 10, 2016 3:39 pm
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by 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.
Image

mrvn
Smart Inserter
Smart Inserter
Posts: 5791
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by mrvn »

Jon8RFC wrote:
Thu Aug 29, 2019 11:36 am
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?

User avatar
Jon8RFC
Filter Inserter
Filter Inserter
Posts: 554
Joined: Tue May 10, 2016 3:39 pm
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by 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?
Image

User avatar
Jon8RFC
Filter Inserter
Filter Inserter
Posts: 554
Joined: Tue May 10, 2016 3:39 pm
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by 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
Attachments
74994-position.zip
(207.94 KiB) Downloaded 150 times
Image

User avatar
boskid
Factorio Staff
Factorio Staff
Posts: 2821
Joined: Thu Dec 14, 2017 6:56 pm
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by boskid »

Jon8RFC wrote:
Thu Aug 29, 2019 12:14 pm
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.

User avatar
boskid
Factorio Staff
Factorio Staff
Posts: 2821
Joined: Thu Dec 14, 2017 6:56 pm
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by boskid »

74994-build-order-matters.zip
(391.26 KiB) Downloaded 165 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"

User avatar
Jon8RFC
Filter Inserter
Filter Inserter
Posts: 554
Joined: Tue May 10, 2016 3:39 pm
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by 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.
Image

User avatar
boskid
Factorio Staff
Factorio Staff
Posts: 2821
Joined: Thu Dec 14, 2017 6:56 pm
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by boskid »

Jon8RFC wrote:
Thu Aug 29, 2019 1:12 pm
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.
Last edited by boskid on Thu Aug 29, 2019 2:06 pm, edited 1 time in total.

mrvn
Smart Inserter
Smart Inserter
Posts: 5791
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by mrvn »

Jon8RFC wrote:
Thu Aug 29, 2019 11:48 am
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.

User avatar
BlueTemplar
Smart Inserter
Smart Inserter
Posts: 2834
Joined: Fri Jun 08, 2018 2:16 pm
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by 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
Screenshot from 2019-08-26 14-25-33.png (3.82 MiB) Viewed 6474 times
(Note that they are on a loop, so can come in/out from either side.)
BobDiggity (mod-scenario-pack)

mrvn
Smart Inserter
Smart Inserter
Posts: 5791
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by mrvn »

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

User avatar
Jon8RFC
Filter Inserter
Filter Inserter
Posts: 554
Joined: Tue May 10, 2016 3:39 pm
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by Jon8RFC »

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

User avatar
boskid
Factorio Staff
Factorio Staff
Posts: 2821
Joined: Thu Dec 14, 2017 6:56 pm
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by boskid »

mrvn wrote:
Thu Aug 29, 2019 2:02 pm
Jon8RFC wrote:
Thu Aug 29, 2019 11:48 am
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
74994p453575-answer.gif (6.65 MiB) Viewed 6471 times
And this is what happens if i rebuild some rails so that lower path is preferred on same cost:
74994p453575-answer-2.gif
74994p453575-answer-2.gif (3.49 MiB) Viewed 6467 times
74994p453575-answer-3.gif
74994p453575-answer-3.gif (3.43 MiB) Viewed 6467 times
Last edited by boskid on Thu Aug 29, 2019 2:19 pm, edited 1 time in total.

mrvn
Smart Inserter
Smart Inserter
Posts: 5791
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by mrvn »

boskid wrote:
Thu Aug 29, 2019 2:11 pm
mrvn wrote:
Thu Aug 29, 2019 2:02 pm
Jon8RFC wrote:
Thu Aug 29, 2019 11:48 am
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.

User avatar
boskid
Factorio Staff
Factorio Staff
Posts: 2821
Joined: Thu Dec 14, 2017 6:56 pm
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by boskid »

mrvn wrote:
Thu Aug 29, 2019 2:17 pm
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:
boskid wrote:
Thu Aug 29, 2019 1:04 pm
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"

User avatar
boskid
Factorio Staff
Factorio Staff
Posts: 2821
Joined: Thu Dec 14, 2017 6:56 pm
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by boskid »

Jon8RFC wrote:
Thu Aug 29, 2019 2:10 pm
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
Long Handed Inserter
Long Handed Inserter
Posts: 54
Joined: Thu Aug 15, 2019 4:16 pm
Contact:

Re: [0.17.66] Suboptimal train pathfinding with two curved tracks intersection

Post by 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.
Last edited by quale on Fri Aug 30, 2019 8:36 pm, edited 1 time in total.

Post Reply

Return to “Minor issues”