SoylentNews

upstart writes in with a story, submitted via IRC, for SoyCow9427 that was the inspiration for:

The BBC has posted a story, The mysterious origins of an uncrackable video game, which describes the investigation by two Game Archaeologists into the Atari 2600 game "Entombed".

The article is a narration of the story outlined in the abstract: Entombed: An archaeological examination of an Atari 2600 game (DOI: https://doi.org/10.22152/programming-journal.org/2019/3/4) and full article (pdf):

The Atari 2600 was an extremely limited device with 128 bytes of RAM, a scaled down version of the venerable 6502 processor called the 6507 which had only 13 address liness restricting it to 8 kB of addressable memory, no interrupt processing, and it had no frame buffer, so each line of pixels to be displayed had to be calculated in real time — racing the beam — so being limited to exactly 76 machine cycles per line. The paper succinctly puts it: "Given that 6507 instructions all take two or more cycles, there was no room for inefficiency."

As if that were not enough of a challenge, there were no libraries in ROM, all code had to be hand-crafted. No programmer documentation meant that to even get started programming, one had to reverse engineer how the 2600 even worked.

The word "uncrackable" in the title is not of the crypto flavor one would normally assume, but instead of the "How did they come up with that?" variety. Specifically: create a scrolling maze that had a path through it, all with the aforementioned hardware limitations.

The part that defies understanding is how did the programmer ever conceive of — and go about implementing — an algorithm that only needed to know the values of 5 neighboring pixels and a 32-entry lookup table?

In this case a pixel was either on (1=wall) or off (0=no wall).

Given the values of a, b, c, d, and e: compute the value of X: wall, no wall, or random().

The actual journal article goes into considerable depth as to how they deduced this code and even went so far as to write Python code to implement it which they included in an appendix.

As the BBC put it:

It seems straightforward, but the thing is, no-one can work out how the table was made.

Aycock and Copplestone have tried retro-engineering the table. They looked for patterns in the values to try and reveal how it was designed, but this was to no avail. Whatever the programmer did, it was a stroke of mild genius. 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. It just seems impossible to explain.

[...] The best guess the pair have is that the programmer behind the maze algorithm must have manually fine-tuned the table values until the game worked as desired, but that still doesn’t really explain the logic behind it.

Original Submission