Games That Weren't^®

Speaking recently with Paul Allen Newell, who helped with the Games That Weren’t book due to his Vectrex connections, Paul flagged up with us recent stories of how his endless maze algorithm (developed for the Atari 2600) caused a bit of attention. Where researchers tried to figure out how it worked and who did what, as well as resolving mythologies uncovered in the process. It made for fascinating reading and I loved how everything came to light over a period of time.

Rather than re-tell the entire story which is covered elsewhere in great detail, we are sharing links to the various papers, podcasts, and pages that have been published in chronological order, so you can see and read through the journey which would eventually lead to the original prototype code being made available.  If anything else comes to light which is new information, we will add it here.

First of all – back in 2018, an academic paper was published by Aycock and Copplestone, which would carry out an archaeological examination (archaeogaming) of an Atari 2600 game called Entombed, containing an endless maze algorithm which had staggered the researchers:

Click to access 1811.02035.pdf

This generated some pretty impressive feedback, which included this BBC article in 2019: https://www.bbc.com/future/article/20190919-the-maze-puzzle-hidden-within-an-early-video-game

At this time, no-one knew how it all fully worked and came to be, not even who was behind it all. One of those involved with Entombed, Steve Sidley, claimed that the algorithm was the work of a programmer who had developed it “whilst not entirely sober”.

Then followed a New Yorker Radio Hour Podcast, where talking with Steve – he revealed that the person behind the algorithm may have had the surname “Newell”. This would lead the group to Paul Allen Newell and his 2008 interview for Digitpress where Paul revealed he worked on the Entombed maze generation algorithm. Eventually getting hold of Paul, they talked to him about the algorithm in more detail, and later put together a podcast of the history/mythology:

https://www.wnycstudios.org/podcasts/tnyradiohour/segments/unearthing-entombed

The algorithm had been generated originally for Towering Inferno. He and a friend named Duncan Muirhead got together to create it, with Duncan doing the maths and Paul the code. As well as Towering Inferno, Paul would later would do a Vectrex adaption of Scramble, whilst Duncan did Armor Attack on the same platform. Both would eventually go to Simutrek to do the arcade game Cube Quest.

As you will learn from the above link – the algorithm wasn’t something that was done whilst being “out of it”/drunk. This had been a cover to try and protect the intellectual property of how the algorithm worked – it was provided “as is” to be the seed for Entombed without explanation of the internals and maths.

Paul still had all the source code that he had created, which was then scanned in. Afterwards, a follow up paper was then created with all the new information that had now come to light, authored by Newell, Aycock, and Biittner: https://intarch.ac.uk/journal/issue59/3/index.html

The article would go into detail of how it all worked thanks to Paul’s new information, but also with source code too. The original 1981-82 rules for the prototype game are there as well. In the end, the algorithm would be called “The Muirhead-Newell Algorithm” on the recommendation of Paul, as Duncan’s math was 51% of what was created, with the code “only being” 49%.

From this, some of the code prototypes that Paul had produced before the algorithm was used in Entombed were built and added to the Atari Protos website with details about each. Here is a page on Entombed, along with links at the very bottom to some of these prototypes:

https://www.atariprotos.com/2600/software/entombed/entombed.htm

For our piece on this Games That Weren’t site, Paul has kindly dug out a new image showing the first physical version of Amaze – an initial version of the “42 variations” that was completed in October of 1981.

“It was from this version that I and others determined that the best game possibility was a ‘cat-and-mouse’ with one player controlling the vertical scrolling of the maze and only able to move horizontally while the other player had full movement over the maze but at the whim of the first players’s maze scrolling.” explained Paul. “I knew it would need a lot of refinement but thought this was the best shot given the limited amount of space in the 4K cartridge for any more code. The attached image is the housing for that first version which, yes, I still have. Who knows if the cartridge still works … but it is academic as there was a copy of code on floppy in my archives which I was able to recover.”

Additionally, Paul revealed that after doing the second paper with John Aycock and Katie Biittner, there arose a question of “is it really endless and is it really guaranteed to always provide a path”. It had been very difficult to tell using an Atari 2600 and only slightly better with the emulator they had used (Stella).

Paul therefore wrote a Linux version in C++ using the original OpenGL for the graphics. “This gave me the ability to easily change variables and, most important, no 4K limit and no vertical blanking limit. I was able to determine that the original algorithm was close but not perfect.” explained Paul. “So I tweaked the algorithm and was able to get a better result. I was unable to prove success in an algorithmic fashion but was able to write a program that could analysis the results of a long run of the code.”

“Still not convinced I really had it, I upped the resolution. In Entombed, you have 8 blocks wide which is then mirrored to get 16 (a block being a cell of either wall or passage). In my original algorithm, I had 16 blocks wide with no mirroring. In my Linux C++ version, I kicked it up to 32 blocks. This let me see details that were hidden with 16 blocks.” continued Paul.

“Including the fact theorized by a reader of the first paper (Iikka Keranen) that the algorithm had a tendency to push the occupant in the maze to the left owing to how it created new rows. I was able to correct that and now have what I think is a maze that actually is endless, always passable with serious difficulty when trying to be a player in a cat-and-mouse game, and all algorithmically generated.”

Here is a short clip of the Linux / OpenGL / 32×32 version that Paul refers to:

–

It is a wonderful story, and with a series of early prototypes of the algorithm that Duncan and Paul had created – and carefully protected. Thanks to Paul Allen Newell for sharing and for additional details.