A Detailed Look at a Bidirectional Three-way Train Intersection
Posted: Mon Mar 09, 2015 3:06 am
Update! The Intersection Checker has been ported to Javascript and is now available here: http://feepingcreature.github.io/trainsearch.html
Train intersections in Factorio are easy to get wrong. In this post, I'll give an example of a naive approach that fails, show why it fails, then demonstrate how to do it correctly.
Consider this humble example of the genus.
Looks good at first glance, right? It actually has a subtle timing issue that can cause a deadlock involving two trains. To illustrate what can happen, let's subdivide the image the same way that Factorio does.
In Factorio, the rail network is split, at signals, into numbered blocks. Let's sketch these in.
Note that any group of "rails that touch" forms a block. It doesn't matter whether those rails are merging or merely crossing - the entire connected center snarl is a single block. You can easily test this by looking at the "incoming/outgoing blocks" data on a rail signal.
So why is this setup broken?
Consider the following chain of events. A train enters the intersection from the top right (347), crossing to the bottom left (346). Since the bottom left is blocked by a previous train, it gets held up in 344. Meanwhile, another train is underneath, waiting to enter 346. By chance, it gets priority when the blocking train moves on. Our bottom train, now in 346 wants to leave upwards, via 348. But it can't - the first train is blocking it from entering 344. But the first train also cannot move on - the train from below is blocking 346!
We have a deadlock.
Visualized like this, it's relatively easy to see how this can be fixed - simply break the "side blocks" up at the outside curve.
In this version, our deadlock cannot happen - the train waiting in 349 to enter 344 will not block the train in 344 from continuing on to 350. As a happy side effect, trains that don't cross each other's path don't interfere with each other.
Can any other deadlocks happen in this version? Maybe with three trains, somehow? To analyze this, I've written a short program ( http://pastebin.com/meRvP9jY ) to exhaustively search all possible combinations of trains and paths through an intersection for deadlocks (a situation where no train can make forward progress).
Let's test it with our broken intersection first.
Output:
Exactly the problem we saw! The program seems to work.
Let's run it on our new intersection:
Output:
So I think you can use this layout with confidence.
Train intersections in Factorio are easy to get wrong. In this post, I'll give an example of a naive approach that fails, show why it fails, then demonstrate how to do it correctly.
Consider this humble example of the genus.
Looks good at first glance, right? It actually has a subtle timing issue that can cause a deadlock involving two trains. To illustrate what can happen, let's subdivide the image the same way that Factorio does.
In Factorio, the rail network is split, at signals, into numbered blocks. Let's sketch these in.
Note that any group of "rails that touch" forms a block. It doesn't matter whether those rails are merging or merely crossing - the entire connected center snarl is a single block. You can easily test this by looking at the "incoming/outgoing blocks" data on a rail signal.
So why is this setup broken?
Consider the following chain of events. A train enters the intersection from the top right (347), crossing to the bottom left (346). Since the bottom left is blocked by a previous train, it gets held up in 344. Meanwhile, another train is underneath, waiting to enter 346. By chance, it gets priority when the blocking train moves on. Our bottom train, now in 346 wants to leave upwards, via 348. But it can't - the first train is blocking it from entering 344. But the first train also cannot move on - the train from below is blocking 346!
We have a deadlock.
Visualized like this, it's relatively easy to see how this can be fixed - simply break the "side blocks" up at the outside curve.
In this version, our deadlock cannot happen - the train waiting in 349 to enter 344 will not block the train in 344 from continuing on to 350. As a happy side effect, trains that don't cross each other's path don't interfere with each other.
Can any other deadlocks happen in this version? Maybe with three trains, somehow? To analyze this, I've written a short program ( http://pastebin.com/meRvP9jY ) to exhaustively search all possible combinations of trains and paths through an intersection for deadlocks (a situation where no train can make forward progress).
Let's test it with our broken intersection first.
Code: Select all
// side paths
paths ~= [346];
paths ~= [347];
paths ~= [348];
// center paths
paths ~= [346, 344, 348];
paths ~= [348, 344, 347];
paths ~= [347, 344, 346];
Code: Select all
Variant 3: 2 simultaneous trains, from [346, 347].
There were trains, but none of them could move. Failure state.
The events leading up to this were:
Train 1 chooses path [346, 344, 348].
Train 1 enters block 346.
Train 2 chooses path [347, 344, 346].
Train 2 enters block 347.
Train 2 enters block 344.
Train 1 wants to enter block 344 but it's blocked by train 2.
Train 2 wants to enter block 346 but it's blocked by train 1.
Let's run it on our new intersection:
Code: Select all
// side paths
paths ~= [349, 350];
paths ~= [354, 353];
paths ~= [352, 351];
// center paths
paths ~= [349, 344, 353];
paths ~= [354, 344, 351];
paths ~= [352, 344, 350];
Code: Select all
[...]
Variant 7: 3 simultaneous trains, from [349, 354, 352]. 978073 successful orderings.
No possible deadlocks.
