5

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:

The maze is symmetrical; the left-hand side is displayed here. It's generated left-to-right, using the two squares to the left and three bits above the current square. The left-hand wall is treated as containing the bits 1 0 (solid, empty), except for the top-left corner which contains a bit from the PRNG. The single bit used at the right-hand side is also a bit from the PRNG, as are some of the output bits.
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?

4

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.

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

| improve this answer | |
  • 1
    Another VCS game that used a LFSR for procedurally generated maps is Pitfall. – OmarL Apr 20 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.