A paper that actually talks about the algorithm and a quote that sums it up

https://arxiv.org/pdf/1811.02035.pdf

> The basic maze generating routine had been partially written by a stoner who had left. I contacted him to try and understand what the maze generating algorithm did. He told me it came upon him when he was drunk and whacked out of his brain, he coded it up in assembly overnight before he passed out, but now could not for the life of him remember how the algorithm worked.’

This is of course just plausible deniability. The truth is that the video game with its impossible algorithm is a message left by a stranded time traveller as a means to help his mates locate him.

I hate to be a party pooper but I don't see any mystery here. The maze generator is a cellular automata with small amounts randomness thrown in. The rules were picked by hand and tweaked to get the desired look. The rules were encode into a lookup table, which was an unexciting, mundane optimization at the time.

I've written very similar code for my 6502 roguelike game.

Now try to create a routine that generates mazes with no dead ends on a system with 128 bytes of total RAM.

That 128 bytes includes stack. No graphics memory at all.

That's what I did :)

I coded my maze generators in 6502 assembly - the same CPU the Atari uses. Mine was for the NES, which is more powerful than the Atari (2KB vs 128B of RAM, for example), but I think I know what I'm talking about.

Programming these old constrained 8-bitters is great fun.

I haven’t seen the actual code they’re discussing in this article, but the interesting part isn’t that this was done on a system with very little RAM. From the sound of things, it works like a finite state machine. You can represent a whole lot of possible states with 128 bytes of RAM. Like, an astrologically large number of states - 2^1024, to be exact. The ability to work within the Atari’s memory constraints isn’t what’s so interesting about this algorithm, it’s that the lookup table driving the algorithm is inscrutable.

Aren't most cellular automata bit matrices that evolve over time? They also tend to generalize to any size. This seems more like a recurrence relation/spigot algorithm or a cipher network of some kind.. several ciphers have look-up tables used for various things.

The tricky bit isn't just getting the desired look, it's having a non-repeating maze layout that doesn't hit dead ends. Seems hard to me..

If you have a one-dimensional cellular automaton (a single row of cells), and plot its states over time in successive rows, you end up with a two-dimensional picture, eg:

https://writings.stephenwolfram.com/2017/06/oh-my-gosh-its-c...

So you conceivably could generate mazes with a cellular automaton.

But Entombed doesn't. Figure 6 in the paper shows the geometry of the rule:

    c d e
  a b X

So it samples bits from the previous row, but also from the current row. In cellular automaton terms, the previous row is the previous timestep, but the current row is the current timestep, and a cellular automaton can't compute cells based on cells in the same timestep.

Reflecting back over my career, I think I can safely say that my most brilliant moments of engineering insight lay buried in code like this -- invisible and unknown, probably for the rest of time.

The idea that some day, some researcher may reverse-engineer one of these things tickles me.

In a game that has to ship, it's fine. In a product that needs to be maintained for a while at least, I personally try to avoid brilliant code. I'd like to say it's out of empathy for co-workers, but it's really to keep myself sane when I need to change my own code in 3 months time.

Your code also presumably doesn't have to run on an Atari 2600.

> I personally try to avoid brilliant code.

"Brilliant" code that is hard for engineers to understand is not necessarily brilliant code.

The things I consider to be my finest moments are not opaque in that way.

Perhaps why game devs don't call themselves software engineers.

I had a professor (who was in industry for a while) tell us to "code smart, not cleverly."

Nice article - but the BBC did get a major detail wrong. The mazes are not always solvable - Figure 5 in the paper (https://arxiv.org/abs/1811.02035) explicitly demonstrates an unsolvable maze sample from the game, which can only be solved by collecting and using a "make-break" powerup (which allows the user to create or remove a wall).

They interviewed a co-creator who claimed it did always make solvable mazes, which is probably where the BBC journalist got confused.

The BBC article says "Every time the game is played, a reliably navigable maze is pumped out. Were the table’s values random or even slightly different, the maze would likely fail to be drawn with a playable path through it." <- the example in fig 5 IS in principle playable - the point I think is that the maze is not drawn in a way that would leave a player stumped even if they had a make-break at their disposal. i.e. Endless wall in the way.

It's Cellular Autometa Rule 15, with some of the options changed to be random. (ie: "be the opposite of the cell to your top left"). This generates unbroken continuous wiggly lines varying between horizontal, diagonal and vertical within one quadrant.

Other than the random elements, there's one exception: 11001 -> 0, which directly leads to a nice downward branching structure.

He probably Carmack'ed a hack.

It's really silly to frame this as "archaeology". Archaeology is the study of long-past civilizations with only traces of clues left behind in buildings, trash piles, etc. This is a game written just a few years ago; you can just ask the folks who worked on it.

(I should add section 4 of the paper tries to explain why this is archaeology, with lots of stuff about "material culture". I did not find it convincing.)