Entombed Secrets Partially Unearthed As Researchers Dissect Clever Maze-Generating Algorithm

If you look at enough of another developer’s code, you will eventually say, “What were you thinking, you gosh-darn lunatic?” Now, this exchange can precede the moment where you quit a company and check into a padded room, or it can be akin to calling someone a mad genius and offering them a beer. In the case of [Steven Sidley]’s 1982 game Entombed, [John Aycock] and [Tara Copplestone] found a mysterious table for generating pseudo-random mazes and wrote a whitepaper on how it all works (PDF). The table only generates solvable mazes, but if any bits are changed, the puzzles become inescapable.

The software archaeologists are currently in a labyrinth of their own, in which the exit is an explanation of the table, but the path is overgrown with decade-old vines. The programmer did not make the table himself, and its creator’s name is buried somewhere in the maze. Game cart storage was desperately limited so mazes had to be generated on-the-fly rather than crafted and stored. Entombed‘s ad-hoc method worked by assessing the previous row and generating the next based on particular criteria, with some PRNG in places to keep it fresh. To save more space, the screen was mirrored down the center which doubles the workload of the table. Someday this mysterious table’s origins may be explained but for now, it is a work of art in its own right.

Aside from a table pulled directly from the aether, this maze game leaned on pseudo-random numbers but there is room for improvement in that regard too.

Via BBC Future.

23 thoughts on “Entombed Secrets Partially Unearthed As Researchers Dissect Clever Maze-Generating Algorithm

  1. I don’t do mazes, but having spent many years cleaning up code some many years old, I will personally attest to the “what the heck were they thinking” – – usually followed by a “How in the world did they get this working” – – followed by a “now how do I fix it so it doesn’t break anymore” usually accompanied by the sound of my head banging on the desk or the closest brick wall

    But always interesting challenges – always kept the job interesting – – and yes sometimes I would find elegance also

  2. Is the yellow-and-white graphic supposed to be an escapable labyrinth? If i enter from above (white = way?) i cannot get to the bottom, and vice versa; Or is it from the left yellow border to the right yellow border (yellow = way?) – then it is not much of a labyrinth, with many dead ends beginning at the border, but the only true way having nearly no false turns.

    1. In the PDF (very long) they reference the game play as vertically scrolling and some parts of the maze are untraversable this is negated by using collectable game pieces called “make-break” that allow the play to construct walls when needed. See page 4:9

    1. It’s a look-up table. It checks the values (wall, no wall) from five adjacent spaces to determine the value of the target space. The way you would easily represent the 32 possible combinations that you would be looking up is by counting up in binary. That isn’t the interesting part. The interesting part is why those five adjacent spaces, and why the values for X for the various combinations (why must some be walls, some be no walls, and some can be either)?

  3. The last time I was really mad at a previous programmer for their terrible code, I went and looked to see who checked in the changes. My cheeks got a little red when I found out it was…. ME!! Nice to get humbled once in a while to keep you on the right track.

    1. Yeah, I know the feeling. Going back and looking at code years later … Sometimes you wonder about yourself as your ‘name’ is right ‘THERE’, yep I actually wrote that…. Experience does change ones perspective. :)

  4. Pitfall on the 2600 (and other platforms too I believe) uses a cleverly chosen PRNG with the screen number (as an 8-bit integer) as the “seed” so the game doesn’t need to store the layout of each screen to be able to retain consistency (if you go left two screens and then back right two screens you’ll be on the same map screen you started on). It’s funny how early and modern games did the procedurally generated level thing but the “middle” segment (essentially mid ’80s to mid ’00s) almost exclusively used individually designed and stored levels.

    1. It’s makes more sense when you consider that memory and storage limitations were large enough to not specifically need procedural generation; but not so large that small a dev-team couldn’t feasibly create sufficient levels manually.

      There were some games that did use procedural generation in the era you mentioned, the first two Elite games are probably the most well known examples; which is how they manage to store several galaxies worth of stars and planets on a single cassette or floppy disk.

    2. It wasn’t a random number generator. it was a straight out algorithm that produced the same thing every time. (Sure a RNG with the same seed every time does that too but…) The algorithm was derived from a function that generated coefficients for some binomial progression…oh wait.. I better go check that.

  5. Has anyone else tried to code up the maze generator and test with a better random number generator? Am finding the results unplayable. Almost as though the reason it worked is because of the bug. Though I may’ve transferred the table wrong.

    1. Yeah, considering the extreme performance restrictions of the era they would be fools to leave the specific behavior of the PRNG on the table. I’m sure it was a low-entropy generator relative to today’s stuff, and they probably mathed it out and took its behavior into careful consideration. One could always use more modern algorithms to check the maze for solvability and make modifications to it after generation, but that loses a bit of the retro-computing fun.

      Most of the ‘table’ is just counting up in binary, btw. You can pretty easily double-check it using that knowledge instead of going back and forth with your reference and painstakingly checking each bit that way.

  6. Programmer: “The basic maze generating routine had been partially written by a stonerwho had left. I contacted him to try and understand what the maze generatingalgorithm did. He told me it came upon him when he was drunk and whackedout of his brain, he coded it up in assembly overnight before he passed out, butnow could not for the life of him remember how the algorithm worked.”

    I know someone exactly like this in contemporary time. For a college class he whacked out a sorting algorithm when he was drunk at night, the next day he didn’t remember how it worked. He came to me telling, ‘this sorting algorithm works, and is quite fast, but I have no idea how it work.’ I looked at it for a good hour. I like pasta but this is something entirely else.

Leave a Reply

Please be kind and respectful to help make the comments section excellent. (Comment Policy)

This site uses Akismet to reduce spam. Learn how your comment data is processed.