http://pubby.games/factorio.html
Factorio's Belt Bug
Factorio is a factory-building game involving lots (and I mean, LOTS)
of conveyor belts. The code that implements these belts is marvel of
optimization, but unfortunately they can't handle every construct.
The Problematic Sushi Belt
The issue occurs when belts are arranged in a loop. At first, items
placed on the belt appear to work normally, circulating around like
the luggage return at an airport. But as soon as the belt reaches
full capacity, it stops.
[belt2]
So what's going on?
I don't have access to Factorio's source code, but I reckon I can
give a good explanation of why this happens. Imagine a simplified
version of Factorio in which belts are single-lane and can hold only
one item per tile:
[belt1]
To update, we'll repeatedly iterate over every item on the belt,
looking for items that have an empty tile in front of them. As we
find such items, we'll move them forwards on the belt and continue
our iteration.
Before: [belt2] After: [belt3]
If the tile in front of an item isn't empty, we can't move the item
there yet but it may be possible to move the item at a different
iteration. For example, item "A" below can't move until item "B" has
moved, and this may take several iterations.
[belt4]
There are different orders one can iterate - some more efficient than
others - but for the sake of correctness, all that matters is
eventually reaching a fixed point. The algorithm stops when no items
can be moved anymore.
Lastly, it's important that when an item moves, it won't move again
until the algorithm completes. Otherwise, items will teleport all
over the place at inconsistent speeds. We'll have to tag each item
that moves and exclude it from future iterations.
Before: [belt2] After: [belt5]
Here's the pseudocode:
do
set MADE_PROGRESS to false
for each item, I
if I has not already moved
let B be the belt under I
let B' be the belt B outputs to
if B' has no item
move I from B to B'
mark I as moved
set MADE_PROGRESS to true
while MADE_PROGRESS is true
And here's the algorithm running to completion, visualized:
[belt1]
The Factorio corner case
For an item to move under this algorithm, it must have a free space
to move onto. But when the items are packed tightly into a circle,
there is no free space and so the whole belt jams up.
[belt6]
Yikes!
Fixing things with optimism
The algorithm above tries to prove which items can move,
pessimistically assuming that any item it can't prove, won't move.
But what if we do the opposite? Consider an algorithm that
optimistically assumes all items move, then proves which items can't.
So how do we do this? Well, if an item is at the end of a belt, it's
safe to say that item can't move. Below, we'll mark such items with a
red "X" to show they can't move.
Before: [belt7] After: [belt8]
Likewise, if an item is blocked by another immobile item, it can't
move either. Once we mark a red "X", the item before it can be marked
as well.
Before: [belt8] After: [belt9]
This new algorithm also runs until it reaches a fixed point. Then,
all items without a red "X" can be moved forwards.
If you try this algorithm out on a circular belt, you'll notice it
completes without marking a single "X"! But this is correct: all
items in the belt will move around it, as none were proven to be
immobile.
[belt6]
Merges
Before giving the pseudocode, there's something that needs to be
addressed. What happens when two or three belt merge together, as in
the case below?
[belt10]
As defined, the second algorithm will move both items onto the merged
belt at once because it can't prove either to be immobile. A bug! The
correct behavior, as handled by the first algorithm, is to only move
one or the other; not both.
We can fix the second algorithm by defining a priority for each
merging belt. A lower priority belt tile will be deemed immobile if a
higher priority belt has an item on it. Below, belt "A" is the higher
priority one, and belt "B" is the lower priority one. "A" is
occupied, so "B" must be immobile.
Before: [belt11] After: [belt12]
For a game like Factorio, these priorities could be switched every
frame to evenly zipper the contents of both belts into one.
The final pseudocode
The code below follows three steps.
1. Handle merges
2. Mark immobile belts (the red "X")
3. Move all items on belts not marked immobile
for each belt intersection, S
set BLOCKED to false
for each input belt to S, B
if BLOCKED is true
mark B as immobile
if B has an item
set BLOCKED to true
do
set MADE_PROGRESS to false
for each item, I
let B be the belt under I
let B' be the belt B outputs to
if B' doesn't exist or if B' is immobile
mark B as immobile
set MADE_PROGRESS to true
while MADE_PROGRESS is true
for each item, I
let B be the belt under I
let B' be the belt B outputs to
if B is not immobile
move I from B to B'
Pros and Cons
From a correctness perspective, the second algorithm is superior, but
one must admit that it takes more code and is less obvious than the
first design. It also complicates the implementation of other
components like inserters, factories, and chests, though this may be
a non-issue for greenfield projects. I suspect Factorio is far too
developed to ever change their belt algorithm, but I'm hopeful newer
games will take the second approach at my own suggestion.
It's important to note that the second algorithm only produces a
usable result when the algorithm finishes. However, the first
algorithm can be run incrementally. Every iteration moves the game
state from one valid position to the next, which may be useful at
times.
An interesting connection to compiler research
I wrote this article about Factorio, but the technique is more
general than that. Flipping around the problem and reversing what
you're proving is a really useful skill!
Originally, I learned of this technique from a paper on compiler
research: "Combining Analyses, Combining Optimizations," by Cliff
Click. Ammusingly, the paper was also using the technique to deal
with loops, albeit of the programming variety. Of course, Cliff Click
isn't the first person to do this sort of thing. Mathematicians have
been enjoying it from quite a ways back.
FAQ
* Have you played factorio?
Yes, I've beat the game twice, and even attempted to make my own
clone game. This article was a result of that work.
* This is inefficient code! Factorio is far more optimized.
Yes, I'm aware, and did a deep-dive of Factorio before writing
this article. But adding optimizations in to my explanation would
totally muddy the clarity and turn this short article into a long
one.
* So you can't optimize it?
You can. The biggest optimization is to combine long straight
segments of belts into a single nodes, a la this Factorio blog
post. This reduces the size of the belt graph, but hardly changes
the algorithms. You might think of it like writing a grid-based
pathfinding algoirthm, then adapting it to be mesh-based.
* Why not do something simpler? If belts go into themselves, make
them loop.
Sure, but that only works for the most trivial cases. The belt
graph can be quite complicated, with loops comprising several
segments. For cases like that you'd have to do cycle detection,
which is totally not better than the 2nd algorithm.
* But Factorio has two-lane belts!
As stated earlier in the article, my explanations were made using
single-lane belts that can hold only one item per tile. This kept
things simple. If you can implement this, you can implement
two-lane belts that hold many items with little difficulty.
* In Factorio you can fix the problem using Splitters.
A splitter on the line make sushi-belts run much better - and
usually work - but they aren't a panacea. You can still jam them
up, they're just far less likely to.
* This behavior is intentional / caused by some other behavior.
Perhaps. I'm not a Factorio dev, and don't have access to the
Factorio code, so this article is just speculation on my part.
But it's still a nice way to show off a cool technique.
[Back to my homepage]