A Detailed Look at a Bidirectional Three-way Train Intersection

[FeepingCreature]

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.

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];

Output:

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.

Exactly the problem we saw! The program seems to work.

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];

Output:

Code: Select all

[...]
Variant 7: 3 simultaneous trains, from [349, 354, 352]. 978073 successful orderings.
No possible deadlocks.

So I think you can use this layout with confidence.

[StanFear]

interesting, have you though about making it into a mod to use directly in game ? where we could select the intersection, and the mod would say "ok" or "there might be a problem"

would be preety great, and ... can your piece of code analyse a whole rail network ?

[ssilk]

For me such stuff belongs into a "blueprint-generator".

Create blueprint for
- Train
--- Rail-layouts
------ Intersections
--------- 2 path
------------ 3-way ................ <click>

A requester opens "Please click to the endpoints of 3 incoming and 3 outgoing rails!"
The rest is automatic. Cause you can repeat this every time it don't needs to be stored, it can be placed directly.

[roy7]

What language is your program written in? I was guessing Java but wanted to be sure.

[tjmonk15]

It was written in D (http://dlang.org/) and the Syntaxt label at the top of the paste says.

- Monk

[roy7]

It was written in D (http://dlang.org/) and the Syntaxt label at the top of the paste says.

- Monk

Thanks! I'd never have guessed that was what Syntax was referring to since I've not heard of D before.

[FeepingCreature]

It was actually written in Neat (https://github.com/FeepingCreature/fcc), my own language! The syntax is largely compatible with D, so that's why I usually use that highlighting option. Somebody who knows D can probably convert this program to D in a few minutes.

I don't think this is feasible to integrate into the game since, due to combinatorial explosion, it takes a minute to make its way through all options for a three-way intersection. With a four-way intersection, it'd be hopelessly overloaded. Might work better with a stochastic approach, not sure.

[PiggyWhiskey]

This is quite amazing.

I'm not fluent in D (or Neat) is there any chance for a Java/C#/VB version?
I started on a conversion to make a mini application, but the syntax is beyond me.

[FeepingCreature]

I ported the code to JavaScript! Also added a small optimization that made it a whole lot faster (to avoid checking the same train state twice).

http://feepingcreature.github.io/trainsearch.html

This is now the official version. I'll add it to the initial post.

[RoddyVR]

THANKS!

quickly showed me how i'd deadlock my planned junctions (i suspected that there were problems, but hoped i was smarter than everyone else who plays factorio).
My first response to it's deadlock situation was "but that would require like 20 car long trains!!! but then i realized that it could just be a string of short trains following eachother and would cause the same thing.

great program. One suggestion though, have the site show the instructions by default. those who have used the program already will know to ignore or collapse them... but new users wont have a "what do i do with these numbers" moment.

[ratchetfreak]

and maybe add a screen shot of an intersection with overlayed blocks as an example

[FeepingCreature]

I've improved the help text somewhat. Is it easier to use and understand like this?

[edit] Added an example picture too.