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?