How does Factorio's train pathfinding avoid physically impossible train movements

[i_like_trains]

I'm always curious how things work behind the scences and I understand that you might not be allowed to discuss implementation details like this publicly.

04-11-2026, 02-10-27.png (557.08 KiB) Viewed 454 times

I took a screenshot from one of your blog posts about trains and labled what I consider vertexes (correct me if I placed my vertexes incorrectly).

Valid moves are:
A ->B, B -> A,
A -> C, C -> A

But invalid movements are going from C - > A - > B. If we look at the individual moves of C - > A - > B it's C - > A and A - > B which are both valid. So how does Factorio keep track of where the train came from?

[Loewchen]

So how does Factorio keep track of where the train came from?

It doesn't. Trains cannot drive backwards so if you do not provide a way to turn around they cannot path to what lies behind them.

[mmmPI]

I think the train path finder code is public : https://gist.github.com/Rseding91/c0d4d ... 3f6c6a8fe6

the "segments" are the "blocks" colored as a single color in game when holding a signal, there isn't a particular thing where you placed the "A" for the game , it wouldn't represent a place where 2 different colors are adjacent or separate, those are created by the presence of signals.

I may be wrong but i would say given where you placed the loco if it was a double headed train and you try to go to C, it would list the indidivual rails from where , add the next one, next one, until it reaches C.

From C, if you try to go to B, the pathfinder will list all rails from where it is, it wil reach where you placed the A, but here it will not add the rails that are not possible to access, so it will not try to go up, it will list all the rails going to the left, realize it's a dead end and there is no possible path to explore, so conclude B isn't reachable and show the "no-path" warning.

[i_like_trains]

First if all, to

It doesn't. Trains cannot drive backwards so if you do not provide a way to turn around they cannot path to what lies behind them.

Sure, but I'm curious how the calculation works as driving backwards is already some sort of state and graphs with state are difficult. Especially because
the graph would have no transitivity. So just because aRb and bRc doesn't mean aRc.

Line 314 suggests that there's a difference between segments and blocks. Seems like a segment is in a block, but there can be multiple segments in a block.
if (neighborSegment->getBlock() != currentSegment->getBlock())

[boskid]

segments vs blocks is not relevant for this discussion. Quick glossary is provided in https://factorio.com/blog/post/fff-331 section `Trains Pathfinder changes`.

This situation does not create problems because pathfinder nodes are directional.

In the original picture that lists A, B, C, there would be in fact 6 nodes [simplifying things quite a lot because train stops will cut segments creating more of them]: lets call them A_west, A_east, B_west, B_east, C_west, C_east. Possible transitions are following:
- A_east -> B_east
- A_east -> C_east
- B_west -> A_west
- C_west -> A_west

Here you can see that there are no ways to start in any of (B_east, B_west) and reach any of (C_east, C_west). In code those nodes are stored inside of seenForwards and seenBackwards (they are only created when explored and they only exist during pathfinding, they get removed when pathfinder is done).

[mmmPI]

Line 314 suggests that there's a difference between segments and blocks. Seems like a segment is in a block, but there can be multiple segments in a block.
if (neighborSegment->getBlock() != currentSegment->getBlock())

don't trust my wording on this, i linked the code because it's the correct answer, i only have "some" understanding of the principles, when i say "list all the rail" that may very well be what is actually a segment in the game, and thus a block would indeed be composed of several segment (rails).

To me when the path finding algo runs, i imagine the "logic" starts where the locomotive is and look forward as if the locomotives is about to drive in a maze and keep track of the distances of each branch, wether they turn left or right or go straight when given a choice.

If it has 2 loco it does twice the work , it starts 2 of those trees, from the point of view of each loco.

But when mapping such trees, the train isn't allowed to reverse direction, it consider driving "always forward".

The "segment" part i associate as rail adjacency rules, which one ares "neighbours" to each other in the sense of allowing a train to pass from one to another. I think it is at this level that a train isn't able to see a path in the rail that it isn't able to drive through because that would mean reversing direction or turning an impossible angle. ( because when "exploring" it embed train driving rules).

The sum of the segments, makes a block, with "entries" and "exits", which are "linked", not all entries lead to all exits , depending on which direction you enter the block.

I think it is something like A* the pathfinding algo, applied at the "block" level whereas the segment logic is done "before" as a necessary step to create the graph on which the A* (or equivalent) is run.

You probably can tell i'm no expert, i am also curious how things works, and sharing what i think i understand from bits gathered here and there over the years, i think it's not as complicated as graph with states, i think i understand intuitively why this : ""So just because aRb and bRc doesn't mean aRc. "" isn't the way the game logic handle pathinding because i implemented for fun a A* algo in javascript once, with the idea that it was similar to how factorio trains works, to understand better, and when i read the question you ask yourself, i feel it's too complicated but it may be because i'm missing the little details.


Edit : Thanks boskid for the clarifications

[i_like_trains]

This situation does not create problems because pathfinder nodes are directional.

If railroads are modeled directionally, how are terminal loops possible in Factorio? In the picture below, there's no way to move from B to C over Z without chaning direcitons. Are you 100 % sure is a directed graph?

04-11-2026, 22-53-02.png (19.69 KiB) Viewed 176 times

[boskid]

In the picture below

I do not understand which game concepts nodes on your graph represent so i wont answer anything about it. I can only tell you that trains pathfinder is finding a path within a directed graph regardless of rails being bidirectional because there are separate nodes for travel each direction (1 rail segment = 2 nodes*)

[i_like_trains]

- A_east -> B_east
- A_east -> C_east
- B_west -> A_west
- C_west -> A_west

Is this derived on the fly or are these relations stored and then constructed during pathfinding? Or is the relation always east -> east and west -> west are allowed?

[i_like_trains]

In the picture below

I do not understand which game concepts nodes on your graph represent so i wont answer anything about it. I can only tell you that trains pathfinder is finding a path within a directed graph regardless of rails being bidirectional because there are separate nodes for travel each direction (1 rail segment = 2 nodes*)

Well, it doesn't map to anything in Factorio. I tried to illustrate my point of confusion.
If it's directed and we go from A to B to Z to C it would all be the same direction, right?

A_east -> B_east -> Z_east -> C_east. But from a top down view the edge between Z and C looks like a west movement, no?

[boskid]

i am simplifying things here a lot because some details are not relevant. Each rail segment has 2 ends (front and back) and they know neighbor rail segments and if they are connected front-front, front-back, back-front or back-back. This is not relevant for the discussion. "east/west" was just a simplification to not get into unnecessary details.