A maze puzzle hidden within an Atari 2600 video game

Re:A maze puzzle hidden within an Atari 2600 video game by pubby on Monday September 23, 2019 @01:46PM (#21051397)

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.

[ Parent | on HN ]

Re:A maze puzzle hidden within an Atari 2600 video game by vardump on Tuesday September 24, 2019 @07:24PM (#21065795)

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.

[ Parent | on HN ]

Re:A maze puzzle hidden within an Atari 2600 video game by pubby on Tuesday September 24, 2019 @10:11PM (#21066894)

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.

[ Parent | on HN ]

Re:A maze puzzle hidden within an Atari 2600 video game by vardump on Wednesday September 25, 2019 @03:36PM (#21074456)

Programming these old constrained 8-bitters is great fun.

[ Parent | on HN ]

Re:A maze puzzle hidden within an Atari 2600 video game by lowtolerance on Wednesday September 25, 2019 @08:22AM (#21070029)

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.

[ Parent | on HN ]

Re:A maze puzzle hidden within an Atari 2600 video game by sterlind on Monday September 23, 2019 @09:05PM (#21055455)

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

[ Parent | on HN ]

Re:A maze puzzle hidden within an Atari 2600 video game by twic on Wednesday September 25, 2019 @06:36AM (#21069403)

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.

[ Parent | on HN ]