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 (1982), 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 real reason the Entombed game is famous is the mystery table behind the maze generation. Legend has it the table was devised in a bar by the original programmer and his mathematical researcher while drunk!
Source: An archaeological examination of an Atari 2600 game by John Aycock and Tara Copplestone.
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.
I also gave both the player and the enemies the ability to break the walls they face so that they could in theory affect the maze generation, though in practice rows are generated far enough ahead that a broken wall is always behind the frontier and never feeds back.
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, in case you don't fancy compiling and running a C game on your machine.
Enjoy!
References
- Wikipedia article on Entombed Atari game)
- The actual Atari 2600 Entombed game playable in Archive.org
- Explaining the Entombed Algorithm by Leon Mächler and David Naccache
- Still Entombed After All These Years: The continuing twists and turns of a maze game by Paul Allen Newell, John Aycock and Katie M. Biittner
- Entombed: An archaeological examination of an Atari 2600 game by John Aycock and Tara Copplestone
- BBC: The mysterious origins of an uncrackable video game
- Interview with Steven Boykey Sidley re: Entombed by John Aycock