Around a year ago (it might have been more, my memory can be spotty) I experienced the raycaster rite of passage almost every game developer goes through. I was reading Lode's tutorial, watching the 'Make Your Own Raycaster' series on YouTube by 3DSage (both resources highly recommended by the way), when I came across the Entombed algorithm: a maze generation algorithm found in the Atari 2600 game Entombed (1983), in which the player must escape a maze while chased by zombies.

What intrigued me about this algorithm is that the maze was being generated procedurally based on some old (almost arcane now) logic that dictated how the next line was going to be generated while working within the constraints of the Atari 2600.

The Atari 2600 has 128 bytes (yes, with a b) of RAM and in Entombed, the maze scrolls upward continuously while the player walks down into it. That means a stored maze is practically impossible, given the device memory limitation. So the maze has to be made one row at a time and thrown away as it scrolls off. Which raises the question: how do you build a maze one line at a time, when you can only keep a handful of lines in memory? Enter the mystery table!

The real reason the Entombed game gained the interest of game archaeologists is the mystery table behind the maze generation, and the fact that to this day nobody has quite managed to explain why it works. For years the story was that it had been written by someone "drunk and whacked out of his brain". Turns out the real story isn't that far off: Paul Allen Newell and Duncan Muirhead, a maths grad student, sketched it out on napkins over a couple of beers at a bar, and Newell had it running on the Atari by the end of the weekend.

Here is how the logic works: Each cell of the maze is generated from its five neighbours: two already filled to its left in the same row, and three from the row above. Those five bits form an index from 0 to 31 into the lookup table above that returns a wall (1), a passage (0) or a coin-flip (random). And that's the whole thing. No backtracking, no searching: the row gets filled in one sweep, with a tetromino-like window sliding along it a cell at a time.

One could go as far as to characterize the algorithm as a cellular automaton, but according to Paul Allen Newell, John Aycock and Katie M. Biittner:

The algorithm defies easy categorisation, and may be unique. With its reliance only on local information, it is tempting to view the algorithm as based on cellular automata (Sarkar 2000), yet the lack of parallelism and the strange shape of the 'neighbourhood' of cells surrounding X makes the cellular-automata notion contrived.

This is pretty much the opposite of how maze algorithms normally work. Usually you hold the whole grid in memory and the algorithm guarantees you end up with a maze you can actually solve. Entombed never sees more than eleven rows at a time and guarantees nothing at all. It just generates something that looks like a maze.

Given that there are no guarantees in the Entombed case, two correction passes are introduced. They run once a line is complete, looking back at the rows behind it: if the maze has started repeating itself or walling sections off, they just blank the whole line, or half of it.

After consuming all the references I could find, I immediately started thinking of ways I could implement this logic on a raycaster! It turned out to be quite a fun side-project which combined learning the ins and outs of raycasting and creating a simple Wolfenstein 3D renderer with the exception that the map must be procedurally generated by logic taken from this ancient (depending on your age) Atari game!

I decided to represent the state of each maze row as a uint32 where each bit shows whether there is a wall or not. This would make things easier to calculate and memory efficient as the maze grows while the player moves further and further in.

My version differs from the original in a few ways: I dropped the mirror (seen in the screenshot above), widened the playfield to 30 cells, and never throw away rows once they're generated, since memory isn't exactly a problem these days (or is it?).

I also gave the player and the enemies the ability to break the walls in front of them, which (in theory) could feed back into the maze generation, but in practice it never does: rows are generated far enough ahead that by the time you break anything, the generator has long moved past it.

The funny thing is that I realized pretty recently that the original game also provided players with the same wall-breaking ability. It makes sense though, as you need to provide players with an easy way to proceed out of dead-ends... especially if you are getting chased by mysterious entities.

I based the C implementation on top of the one provided by 3DSage and fixed some corner cases I could find where the player and the enemy entities could get stuck. Overall it was a really fun and unique experience.

Once I got it working I pretty much forgot about it. Then a couple of weeks ago after watching the 'Backrooms' movie I got reminded of this short experiment, so I thought I could spruce it up, solve some minor issues, skin it as a Backrooms-y type of game (please don't sue me lol) and show it to the world.

As a cherry on top, I told Claude to write a Three.js version of it playable in the browser with some more effects (tried my best to recreate a Diablo-like minimap), in case you don't fancy compiling and running a C game on your machine.

How far can you go until you get entombed?

References