Researchers Study an Impenetrable Vintage Atari Game Algorithm

Legend has it that alcohol was involved in creating the puzzling table that makes the Atari game’s maze.

Dan Carney, Senior Editor

November 24, 2021

3 Min Read
IMG_3355 2.JPG
Dan Carney, with Prisma AI

Algorithms are a hot topic of conversation, as Facebook, er, Meta, finds itself criticized for employing algorithms that promote anger and strife for the purpose of increasing customer engagement with the website.

But it is difficult to drill into algorithms to see exactly how they work, especially very complex social media algorithms. The magnitude of this challenge is illustrated by University of Calgary researchers John Aycock and Tara Copplestone’s paper, “The Art, Science, and Engineering of Programming."

Entombed_for_the_Atari_2600.gif

The player moves through Entombed's vertically scrolling maze.

The paper examines an Atari 2600 console game from 1982 called “Entombed.” This vertically scrolling game generated a maze in real time as the player progressed through catacombs, but the algorithm that creates the solvable maze on the fly using the Atari’s minimal computing resources has modern programmers scratching their heads.

The game’s manual introduces it like this: “You and your team of archeologists have fallen into ‘the catacombs of the zombies.’ The longer you survive, the faster you have to move.”

As a reminder, the Atari 2600 console, like the Apple II and Commodore 64 PCs, was powered by a MOS Technologies 6507 processor. It ran at 1.19 MHz and had 128 bytes of RAM on a MOS 6532 RAM, I/O, and Timer (RIOT) chip. Bytes. Not gigabytes, megabytes, or even kilobytes. The game cartridges brought with them 4 kilobytes of ROM that held the game.

Related:Facebook Goofed up - Here's How to Avoid the Same Mistake

The 2600’s last chip was a Television Interface Adapter. As Aycock and Copplestone explain, “A 2600 programmer had to structure their code to render the display on a line by line basis and repeat that for every single video frame.”

Working within these constraints demanded that the game generate a new maze on the fly every time because there was no space to store an existing maze design. Indeed, the paper explains that “The programming challenges are noted by former 2600 programmers in interviews. John Harris said ‘The way the machine had to be programmed was so obscure and so challenging that you had to write extremely optimal code.’”

DSC_0075.JPG

The Atari 2600 was produced from 1977 until 1992 because of the large number of games that were available for the console.

So optimal, it seems, that in the case of the maze-generating algorithm, no one can figure out how the table that creates it works today. Programmer Paul Allen Newell remembers its creation this way: ‘Duncan and I went out for a beer and ended up coming up with this “problem” of wondering whether one could generate an endless maze that always had a solution and that ‘We worked out the algorithm and [...] I spent a weekend coding something up.’”

Newell’s colleague Steve Sidley remembers it this way: ‘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.’”

Related:40 Years of Pac-Man Fever!

It is no surprise to Sidley that today’s engineers don’t know how the game’s maze is generated because he couldn’t figure it out at the time. “It was a mystery to me too,” he said. “I couldn’t unscramble it. I just used it to generate the new [maze] row at the bottom of the screen.”

About the Author

Dan Carney

Senior Editor, Design News

Dan’s coverage of the auto industry over three decades has taken him to the racetracks, automotive engineering centers, vehicle simulators, wind tunnels, and crash-test labs of the world.

A member of the North American Car, Truck, and Utility of the Year jury, Dan also contributes car reviews to Popular Science magazine, serves on the International Engine of the Year jury, and has judged the collegiate Formula SAE competition.

Dan is a winner of the International Motor Press Association's Ken Purdy Award for automotive writing, as well as the National Motorsports Press Association's award for magazine writing and the Washington Automotive Press Association's Golden Quill award.

AstonMartinVanquish_©AndyMorgan_025_copy_2.JPG

He has held a Sports Car Club of America racing license since 1991, is an SCCA National race winner, two-time SCCA Runoffs competitor in Formula F, and an Old Dominion Region Driver of the Year award winner. Co-drove a Ford Focus 1.0-liter EcoBoost to 16 Federation Internationale de l’Automobile-accredited world speed records over distances from just under 1km to over 4,104km at the CERAM test circuit in Mortefontaine, France.

He was also a longtime contributor to the Society of Automotive Engineers' Automotive Engineering International magazine.

He specializes in analyzing technical developments, particularly in the areas of motorsports, efficiency, and safety.

He has been published in The New York Times, NBC News, Motor Trend, Popular Mechanics, The Washington Post, Hagerty, AutoTrader.com, Maxim, RaceCar Engineering, AutoWeek, Virginia Living, and others.

Dan has authored books on the Honda S2000 and Dodge Viper sports cars and contributed automotive content to the consumer finance book, Fight For Your Money.

He is a member and past president of the Washington Automotive Press Association and is a member of the Society of Automotive Engineers

Sign up for the Design News Daily newsletter.

You May Also Like