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.

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:

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:     After:

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.

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:     After:

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:

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.

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:     After:

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:     After:

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.

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?

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:     After:

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

[Back to my homepage]