Where did the lookup table in Entombed come from?

Question

Entombed is an Atari 2600 game where you move through an infinite vertically-scrolling maze and try not to die. This maze is procedurally generated, with two bits from a PRNG (underlined) added each row, by looking up five bits from the maze in a lookup table:

^{Figure 7 from Entombed - An archaeological examination of an Atari 2600 game by John Aycock and Tara Copplestone, used under CC BY 4.0}

a b c d e │ X
──────────┼──
0 0 0 0 0 │ 1
0 0 0 0 1 │ 1
0 0 0 1 0 │ 1
0 0 0 1 1 │ —
0 0 1 0 0 │ 0
0 0 1 0 1 │ 0
0 0 1 1 0 │ —
0 0 1 1 1 │ —
0 1 0 0 0 │ 1
0 1 0 0 1 │ 1
0 1 0 1 0 │ 1
0 1 0 1 1 │ 1
0 1 1 0 0 │ —
0 1 1 0 1 │ 0
0 1 1 1 0 │ 0
0 1 1 1 1 │ 0
1 0 0 0 0 │ 1
1 0 0 0 1 │ 1
1 0 0 1 0 │ 1
1 0 0 1 1 │ —
1 0 1 0 0 │ 0
1 0 1 0 1 │ 0
1 0 1 1 0 │ 0
1 0 1 1 1 │ 0
1 1 0 0 0 │ —
1 1 0 0 1 │ 0
1 1 0 1 0 │ 1
1 1 0 1 1 │ —
1 1 1 0 0 │ —
1 1 1 0 1 │ 0
1 1 1 1 0 │ 0
1 1 1 1 1 │ 0

This lookup table determines whether the bits of the maze should be 1, 0 or generated by the PRNG. It was probably modified from an algorithm developed by Duncan Muirhead and Paul Allen Newell, but what were once variables were apparently replaced by hard-coded values.

Are there any details of this original algorithm available? How does this version work? What's the reasoning behind the choice of values, and how do they create a difficult-but-usually-solvable maze so reliably?

The maze algorithm for Entombed was created by Duncan and me. The opportunity to do the game based on the algorithm happened afterwards and I elected to not take that chance, so I never actually did the game. The story of the algorithm is that one night after work, Duncan and I went out for a beer and ended up coming up with this "problem" of wondering whether one could generate an endless maze that always had a solution. […] We worked out the algorithm and, since I knew how to program a VCS system (Duncan was Vectrex only), I spent a weekend coding something up. We were surprised at the elegance of the algorithm as it gave us the ability to dial in a "difficulty factor" (via a bit setting) and we could prove that there was not only a point where it became unsolvable, but also a point on the other end of the spectrum where it became just an obstacle course as the sense of paths vanished because there were too many possibilities. It always auto-generated the next line, top or bottom, so when you scrolled down and then scrolled back up, you would often get a new solution. It was not symmetrically mirrored down the middle as the final game ended up. We knew we could extend it to work in a sideways direction, but the VCS didn't allow for lateral scrolling. — Paul Allen Newell, Digital Press interview

The algorithm was once understood so well that it could be modified to work in two dimensions, instead of one. So: what's the core idea of this algorithm? How does it work? Where does this infamous lookup table come from?

Answer 1

Note on the implementation:

This is some variation of a linear-feedback shift register. These look at some of the bits in the value, and then produce another bit which is shifted in to form the next value. They can be made to loop through (almost) all possible values of a word, and so have even been used as program counters.

It looks as though the output values (i.e. the left-most column in your table) are mostly 0 if the input contains a lot of 1s, and mostly 1 where the input contains a lot of 0s. This will have the effect of "balancing" the LFSR, and not make it get stuck at some value or in a loop.

Because there are only 5 bits of input, the LFSR cannot be made to generate a sequence longer than 32. The maze has a width of 8, so that would mean only 4 rows before the pattern repeats, which would be a very boring maze. This is the reason to occasionally inject a value from a PRNG. It is also the case that an LFSR is usually much faster than the PRNG given in the paper you cited, which is one reason they didn't use the PRNG alone.

So: what's the core idea of this algorithm?

The core idea is to reduce the problem of generating solvable mazes to a few invariants. The choice of invariants and implementation means the mazes won't be terribly complicated, such as having very long dead-ends or having elaborate but provably unreachable sub-mazes, and the generated mazes will not have wide open spaces.

Where does this infamous lookup table come from?

There are at least a couple of accounts.

One story is that Duncan and Paul went out for a beer and for amusement they were talking about the problem of generating endless, solvable mazes. It's possible (even probable) they talked about the LFSR as a solution, but either way, the idea was in their heads by then. Anyhow, LFSRs are well known, easy to implement in a few bytes of 6502 machine code, and so were often used in procedural generation in VCS games. Another game that uses LFSR for procedurally generated content is Pitfall.

Sidley, who wrote at least some of the code for Entombed, notes:

The basic maze generating routine had been partially written by a stoner who had left. I contacted him to try and understand what the maze generating algorithm did. He told me it came upon him when he was drunk and whacked out of his brain, he coded it up in assembly overnight before he passed out, but now could not for the life of him remember how the algorithm worked.

It's possible that Duncan and Paul went for a beer to talk about the stoner's code, which was "partially written". Another possibility is that the code was working well by that point, and Duncan and Paul wanted to tweak the code to not always generate solvable mazes (this is an important game mechanic in Entombed).

What's the reasoning behind the choice of values, and how do they create a difficult-but-usually-solvable maze so reliably?

Do you see, how the function's inputs are the bits to the top and to the left of the space where the output is? It reminds me of the Floyd-Steinberg dithering algorithm. It's a computationally cheap way to apply a function to a 2D grid.

So the solvability of the maze depends on the choice of wall or open for every space in the grid. We know it must depend only on very local context, and only on the context immediately above or to the left of the space in the grid. So the algorithm is explained in Mächler and Naccache. They list the invariants necessary for the algorithm to work. My understanding of that paper is the following. I will list the invariants here in the order given by the paper, but I will explain them in a different order.

The invariants:

1. No 2 × 2 squares of the same type are allowed
2. No wall or path is allowed to start or end with thickness one
3. Every path in any given line must be connected to a path in the next line

Invariant #3 ensures that there are no dead ends as you travel in the vertical direction, since it makes sure there's somewhere for the player to go. And sure enough, that's the easy case. Using this rule alone, you could just have a single corridor running up and down the screen: a very simple and boring but obviously solvable maze. That's why the other two invariants are there.

Invariant #1 has to do with the feedback function of the LFSR. A poorly-chosen feedback function would make the LFSR cycle round a few uninteresting values. That's because the function's input space is as little as five bits; if three of those are the same, the LFSR would cease to generate more interesting maze.

Invariant #2 has a missing word in the description in the numbered list: it means that walls or paths may not end vertically unless they have a width of at least 2. This invariant means that the algorithm will not generate a boring, single, vertical corridor like I described in the note to invariant #3. (There is an exception to invariant #2, and it has to do with the "imagined" values across the edge of the maze, which means that an unreachable vertical corridor is possible at the edge of the maze)

These three rules are enforced by the choice of 0 or 1 for the LFSR's output bit. In some cases where the choice of 0 or 1 cannot violate any of the three invariants, the input is instead taken from the PRNG so that more state is injected to the maze generation.