5 ms·

A maze puzzle hidden within an Atari 2600 video game

62 points by cpeterso 7y ago

throwaway66920 7y ago
A paper that actually talks about the algorithm and a quote that sums it up https://arxiv.org/pdf/1811.02035.pdf 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.’
- Udik 7y ago
  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.
JohnFen 7y ago
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.
- guitarbill 7y ago
  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.
  - Wowfunhappy 7y ago
    Your code also presumably doesn't have to run on an Atari 2600.
  - JohnFen 7y ago
    > 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.
    - karmakaze 7y ago
      Perhaps why game devs don't call themselves software engineers.
  - acomjean 7y ago
    I had a professor (who was in industry for a while) tell us to "code smart, not cleverly."
cellular 7y ago
He probably Carmack'ed a hack.
pubby 7y ago
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.
- sterlind 7y ago
  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..
  - twic 7y ago
    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-covered-in-rule-30s/ 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.
- vardump 7y ago
  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.
  - pubby 7y ago
    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.
nneonneo 7y ago
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 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.
- motorogo 7y ago
  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.
NelsonMinar 7y ago
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.)
sonofgod 7y ago
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.

62 points by cpeterso 7y ago

A paper that actually talks about the algorithm and a quote that sums it up https://arxiv.org/pdf/1811.02035.pdf 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.’

Udik 7y ago
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.

JohnFen 7y ago

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.

guitarbill 7y ago
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.
- Wowfunhappy 7y ago
  Your code also presumably doesn't have to run on an Atari 2600.
- JohnFen 7y ago
  > 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.
  - karmakaze 7y ago
    Perhaps why game devs don't call themselves software engineers.
- acomjean 7y ago
  I had a professor (who was in industry for a while) tell us to "code smart, not cleverly."

cellular 7y ago

He probably Carmack'ed a hack.

pubby 7y ago

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.

sterlind 7y ago
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..
- twic 7y ago
  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-covered-in-rule-30s/ 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.
vardump 7y ago
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.
- pubby 7y ago
  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.

nneonneo 7y ago

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 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.

motorogo 7y ago
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.

NelsonMinar 7y ago

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.)

sonofgod 7y ago

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.