Mazes, Part 2: Programming Mystery

In the last blog, we saw how to draw a maze on paper. It should be a lot easier on a computer, right? After all, so many video games from my childhood involved mazes: try and find a way out of the maze before the monsters/zombies/aliens caught you.

 

As you might have guessed, the tale of those video game mazes is far more interesting. A computer scientist decided to check out the source code of an Atari game called Entombed. Now keep in mind that memory was a severe constraint:

“Although the blocky, two dimensional mazes from entombed might look simple by the standards of today’s computer graphics, in 1982 you couldn’t just design a set of mazes, store them in the game and later display them on-screen – there wasn’t enough memory on the game cartridges for something like that.”

 

And so, such games had to come up mazes on the fly, via an algorithm, instead of keeping them hard-coded in memory. Of course, this was a good thing because it meant no two mazes from the same game were identical, and thus kept the game interesting! But this raised a new question:

“But how do you do get a computer program to avoid churning out a useless maze with too many walls, or an otherwise impenetrable floorplan?”

 

The computer scientist checking out the game code hoped to “find some clever process at work in the depths of Entombed”. It was turning into a very interesting problem: with the limited memory of that era, the program couldn’t calculate too far ahead! But that just made the problem harder:

“The game needs to decide, as it draws each new square of the maze, whether it should draw a wall or a space for the game characters to move around in.”

So how did the game decide whether to draw a wall or a space?

“The game’s algorithm decides this automatically by analysing a section of the maze. It uses a five-square tile that looks a little like a Tetris piece. This tile determines the nature of the next square in each row.”

And here’s the fascinating part:

“The fundamental logic that determines the next square is locked in a table of possible values written into the game’s code. Depending on the values of the five-square tile, the table tells the game to deposit either wall, no wall or a random choice between the two.”

 

So answer found? Not really, because we have no idea “how the table was made”. It obviously couldn’t be random since that would have led to unsolvable mazes. Instead:

“Every time the game is played, a reliably navigable maze is pumped out.”

Even today, they’ve been unable to figure out how the table was arrived at:

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

 

Perhaps we’ll never know. And guess what? There’s even a term for digging into the code of old video games: “video game archaeology”:

“Digital archaeologists can dig for clues about the evolution of programming, unravel the workings of old technology and gain insights to the fading culture of the 20th Century – by excavating video games.”

 

So is this all just idle curiosity? Actually, there’s a very practical reason for video game archaeology. Today, we aim for Virtual Reality and realistic simulations. And while the memory and processing capabilities have increased tremendously compared to the days of Atari, they’re still not enough for what we aim at today. Hence the idea that whatever tricks those Atari game writers used to compensate for their memory/processing constraints may give us clues on how to handle our present-day memory/processing constraints.

 

So while I didn’t find the answer to my childhood question on how they programmed a maze in those games, this rabbit hole I stumbled into is turning out to be endlessly fascinating.