# Where did the lookup table in Entombed come from?

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?

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

It looks like 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.

Where does this infamous lookup table come from?

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 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.

The algorithm was once understood so well that it could be modified to work in two dimensions, instead of one.

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.

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 `1`s, and mostly `1` where the input contains a lot of `0`s. 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. 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 probably the reason they didn't use the PRNG alone.

• Another VCS game that used a LFSR for procedurally generated maps is Pitfall. – OmarL Apr 20 '20 at 15:34
• Does this answer the question? It's pretty clear from the diagram it is based on an LFSR, yes, but how does it guarantee that there's a solvable maze? IMO that's the question that needs an answer - and I'd like to see it! – davidbak Mar 9 at 17:24