A Detailed Look at a Bidirectional Three-way Train Intersection

Don't know how to use a machine? Looking for efficient setups? Stuck in a mission?
Post Reply
FeepingCreature
Burner Inserter
Burner Inserter
Posts: 19
Joined: Sat Dec 13, 2014 1:08 am
Contact:

A Detailed Look at a Bidirectional Three-way Train Intersection

Post by FeepingCreature » 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.

Image

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.

Image

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.

Image

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.
Last edited by FeepingCreature on Mon Jul 06, 2015 11:56 am, edited 1 time in total.

User avatar
StanFear
Fast Inserter
Fast Inserter
Posts: 236
Joined: Sun Dec 15, 2013 2:49 pm
Contact:

Re: A Detailed Look at a Bidirectional Three-way Train Intersection

Post by StanFear » Wed Mar 18, 2015 12:14 pm

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 ?

User avatar
ssilk
Global Moderator
Global Moderator
Posts: 10430
Joined: Tue Apr 16, 2013 10:35 pm
Contact:

Re: A Detailed Look at a Bidirectional Three-way Train Intersection

Post by ssilk » Wed Mar 18, 2015 5:21 pm

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. :)
Cool suggestion: Eatable MOUSE-pointers.
Have you used the Advanced Search today?
Need help, question? FAQ - Wiki - Forum help
I still like small signatures...

roy7
Filter Inserter
Filter Inserter
Posts: 334
Joined: Fri Dec 12, 2014 4:24 pm
Contact:

Re: A Detailed Look at a Bidirectional Three-way Train Intersection

Post by roy7 » Tue Jun 16, 2015 4:03 am

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

tjmonk15
Inserter
Inserter
Posts: 26
Joined: Fri Jun 20, 2014 9:23 pm
Contact:

Re: A Detailed Look at a Bidirectional Three-way Train Intersection

Post by tjmonk15 » Tue Jun 16, 2015 4:46 am

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

- Monk

roy7
Filter Inserter
Filter Inserter
Posts: 334
Joined: Fri Dec 12, 2014 4:24 pm
Contact:

Re: A Detailed Look at a Bidirectional Three-way Train Intersection

Post by roy7 » Tue Jun 16, 2015 10:58 pm

tjmonk15 wrote: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
Burner Inserter
Burner Inserter
Posts: 19
Joined: Sat Dec 13, 2014 1:08 am
Contact:

Re: A Detailed Look at a Bidirectional Three-way Train Intersection

Post by FeepingCreature » Tue Jun 16, 2015 11:49 pm

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
Fast Inserter
Fast Inserter
Posts: 236
Joined: Wed May 13, 2015 5:28 am
Contact:

Re: A Detailed Look at a Bidirectional Three-way Train Intersection

Post by PiggyWhiskey » Tue Jun 23, 2015 1:05 pm

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
Burner Inserter
Burner Inserter
Posts: 19
Joined: Sat Dec 13, 2014 1:08 am
Contact:

Re: A Detailed Look at a Bidirectional Three-way Train Intersection

Post by FeepingCreature » Mon Jul 06, 2015 11:55 am

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
Long Handed Inserter
Long Handed Inserter
Posts: 96
Joined: Thu May 07, 2015 6:29 am
Contact:

Re: A Detailed Look at a Bidirectional Three-way Train Intersection

Post by RoddyVR » Tue Jul 07, 2015 8:54 am

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
Filter Inserter
Filter Inserter
Posts: 927
Joined: Sat May 23, 2015 12:10 pm
Contact:

Re: A Detailed Look at a Bidirectional Three-way Train Intersection

Post by ratchetfreak » Tue Jul 07, 2015 9:31 am

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

FeepingCreature
Burner Inserter
Burner Inserter
Posts: 19
Joined: Sat Dec 13, 2014 1:08 am
Contact:

Re: A Detailed Look at a Bidirectional Three-way Train Intersection

Post by FeepingCreature » Tue Jul 07, 2015 12:18 pm

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

[edit] Added an example picture too.

Post Reply

Return to “Gameplay Help”

Who is online

Users browsing this forum: No registered users and 3 guests