[0.10.3] Train Pathfinding

[Balthazar]

I've posted about this before, but this time i caught the son of a bitch in the act.



Here Train 2 was waiting for the track ahead to clear as train 1 approached the intersection, selecting the wrong track while both exits were blocked by train 1.

This happened after one of my trains ran out of fuel and clogged everything, i watched another 5 trains make the same mistake, derping off into the distance, wasting time, fuel, and delaying other trains, so it seems like a consistent error. The wrong path is a dead end that goes nowhere as well:



This is clearly not the right path for the train to choose as it can only possibly lead back to the intersection.

[sillyfly]

Yes, this is very frustrating. See also this post -
https://forums.factorio.com/forum/vie ... f=7&t=2237

I think the problem is that the pathfinding algorithm always prioritizes clear paths, even if they are longer. This sometimes leads to a situation which is nonsensical - going around a long loop, only to come back to the same (blocked) junction.

In the thread I mentioned above ssilk offered some pseudo-code to maybe solve this, but I don't know when the developers intend to incorporate something like this.
A best solution would probably be something of a Viterbi-like algorithm to find the optimal path, while giving red signals some weight less than infinity.

[Balthazar]

It's not quite the same though, if it was just picking the clear path i could understand it, but for me both tracks are occupied @_@

[ssilk]

Well, in this case it is easy, cause there is minimum one track, which the train runs over twice. In that case, the way MUST be wrong.

In other cases it is eventually a good idea to choose a longer way to avoid jamming. The problem is eventually, that the way around is more crowded.

Hm.

In my opinion this happens in real life every day: Trains are routed around. I see that nearly every time, when I travel by train. If you watch it from above, there is eventually a better solution, but if you sit in the train you don't see that. And it doesn't matter, the difference is just some minutes - what counts in the end is that you come to your target. I mean: the train routing must not be perfect, it just needs to be good enough, that obvious errors are avoided and that it utilizes the maximum, no!, a good throughput by itself.

And the second need to it is, that it makes the process of choosing the path as transparent as possible. Because I predict many bug reports, if it is not clear, how the train finds it's way in a not "best/shortest" way, as for "Viterbi-like algorithm".

There are many ideas, the most bring in some color-overlay in. I've also nothing against, if a train needs longer to start, cause of solving a complex pathfinding-problem, as long, as this is transparent (a waiting clock over the train for example).

[sillyfly]

I didn't mean anything too complicated. By Viterbi-like algorithm all I meant was an algorithm that checks - if an optional path leads to the exact same place as another, but through a longer route - the longer path is obviously wrong. It's a way of ruling out paths once you know of better ones.

In this model, all you need to do is say something like - a red signal equals X tiles (Say 100, just as an example), and then just search for the shortest path (maybe with a few optimizations for the maximum search radius, to keep it sane).
If I understand correctly, this is very similar to what you already suggested. Of course, those are only suggestions and the developers will decide what is best for them
But as I see it a lot of the problems now arise from the fact the a red light is considered the absolute worst, which is wrong in almost all cases.

[slpwnd]

Actually the current path finding logic is dead simple. It is a standard A* algorithm. The algorithm properly resolves situations with one way tracks but apart from that doesn't care if there is a red signal on the track. There is one exception to this. When the very next block from the starting position (which is this case!) is occupied by another train then algorithm will always prefer a different path (unless that path starts with an occupied first block as well). This special rule is to avoid situations when trains come to the rail signals from opposite directions when they could have avoided this.

However in this case, both of the paths start with an occupied block which is strange.

[Balthazar]

Well, that solves the why i guess

Is the setup unusual? I always use this type of rail network same as TTD, i have a lot of trains running around mostly for fun, and making individual paths for everything is a chore, especially when theres a lot of overlap. If the two trains are converging on the same path one goes first, then the other, or am i missing something? I don't see a problem with that.

If you're talking about a head-on collision that should never happen in a one-way setup.

[slpwnd]

If you're talking about a head-on collision that should never happen in a one-way setup.

OMG Good point. Maybe it can use the special rule only if the next block is not a one way block. That would solve quite a bit ...

EDIT: Could you maybe post the save so I can test it a bit ...

[Balthazar]

Sorry for the late reply, i'll get on it now, just need a minute to get the trains clumped up, will edit when done

EDIT: savelink https://www.mediafire.com/?1p8n2k81ahscisi
Just unpause the train directly below the player to get it running again

[ssilk]

See to bring this to front: https://forums.factorio.com/forum/vie ... f=6&t=7346

[kovarex]

Fixed for 0.11.11