4 ms·

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

by 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.
  - vardump 7y ago
    Programming these old constrained 8-bitters is great fun.
- lowtolerance 7y ago
  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.

by pubby 7y ago

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.
- vardump 7y ago
  Programming these old constrained 8-bitters is great fun.
lowtolerance 7y ago
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.