A brilliant algorithm for creating mazes in the Entombed game, which they still can not solve
In 2017, two scientists, Canadian John Aycock and British Tara Copplestone, published an analysis of the classic game Entombed for the Atari 2600 game console . The mechanics of this game, released in 1982, are extremely simple: an archeologist controlled by a player must make his way through the catacombs scrolling from bottom to top, dodging zombies.
The Atari 2600 had only 128 bytes of RAM; however, the seemingly endless maze at each launch was new, i.e. generated in memory. How did the programmers succeed? Here is a comment by Stephen Sidley, the programmer who created this game 38 years ago:
The main part of the labyrinth generator was written by some quitters. I contacted him to find out how his algorithm worked. He replied that he came up with this algorithm when he was completely smoked and in addition drunk, that he wrote it right away in assembler before he passed out, and then he couldn’t even close remember what his algorithm consisted of.
Wikipedia lists a dozen different algorithms for generating mazes . Of greatest interest to game consoles is the " Eller algorithm ", created in the same 1982 by Martin Eller of Microsoft. Eller's algorithm allows to create line-by-line connected labyrinths without cycles, and to generate a labyrinth of unlimited height, it is enough to store only a couple of last lines in memory. It would seem that this is exactly what Entombed needs! But alas, the Eller algorithm is incompatible with the game mechanics of a vertical scroller, because in the resulting labyrinth you regularly have to avoid obstacles from above. To demonstrate this, I slightly modified the Eller algorithm so that the maze was created in the matrix of “walls” and “passages” A, as in Entombed:
More sophisticated algorithms that use recursion and the like would not fit into 128 bytes of RAM. So, the requirements for the algorithm for Entombed are:
- Line-by-line generation of labyrinths of unlimited height;
- In the created labyrinths there should be as few disconnected sections as possible; (the player has a limited ability to “punch walls”, so rare inconsistencies are not a problem)
- The created labyrinths should consist mainly of branching and connecting vertical passages - so that upward movement is not required to go through the labyrinth;
- Only the last few lines generated must be used to generate new maze lines. (Since the Atari 2600 does not have a video buffer, all the lines of the labyrinth visible on the screen should be stored in 128 bytes of main memory in some form).
Who and how created this algorithm?
Two scientists who call themselves “video game archaeologists” decided to start their research with Entombed, a game about an archaeologist in a maze. In the course of their research, they spotted Steven Sidley, and asked him what algorithm he used to generate the maze. As already mentioned, Sidley answered them that even the author of the algorithm could not remember what his algorithm consisted of, and Sidley himself - even more so.Then the researchers tried to find the “stick” that created this algorithm; the second half of the story was found in an interview published in 2008:
The maze generator for Entombed was created by Duncan [Duncan Muirhead] and I [Paul Allen Newell]. One evening after work, Duncan and I went for a drink, and we got into a discussion about whether it is possible to generate an endless algorithm in which there is always a passage. Then we did not think about creating a game, we were interested in the very task of generating a maze. We came up with an algorithm together, and since I knew how to program for VCS [Atari 2600], over the weekend I created a workable prototype. We were both impressed with how elegant the implementation turned out. Then we showed this prototype to the authorities, and they decided that it would make a great game. I was no longer interested in this, so I completed Towering Inferno , using part of our algorithm there, and quit. After I left, the firm hired Stephen Sidley, and handed the maze generator to him. He had to remove a substantial part of my code to make way for game mechanics. [Atari 2600, in addition to strict restrictions on the amount of RAM and ROM, there was also a requirement that the generation of each row of pixels occupy exactly 76 cycles author’s note ].
Sidley mentioned that the maze generator code was written in assembler 6502 without any comment. This in itself looks like a feat: as noted khim , there " the set of commands is so limited and crooked that when writing programs, the main question arises is "how is there anything at all write "?" Nevertheless, the researchers picked up the game code and found out that the maze is generated as follows: for each of the eight cells of the generated row, five already-generated cells are considered (three on the top and two on the left), and in accordance with The “magic table” selects the state of the new cell (passage, wall, or random selection). The two leftmost cells are always full, and are not stored in memory. The right half of the maze is just a mirror image of the left.
The mysterious table at the heart of an unsolved algorithm
The properties of the generated maze depend on of what state of the new cell is set for each five generated earlier. The table sewn into Entombed puzzled researchers a lot: “We did not notice any patterns in it, even when we presented it in several ways as Carnot cards .” Sidley spoke in the same vein: “For me it remains a mystery: I could not unravel it, and used it as a black box.” However, the lack of regularities in the table is some exaggeration: for example, you can see on the Carnot map that if c =1 (the wall to the left of the current cell) X =1 (the wall in the current cell) will not be generated.
Archeology of video games
John Aycock commented on how Entombed was the subject of his research: he was preparing a reverse engineering task for his students, and chose a relatively little-known game, because for popular games, students could find the code already parsed on the network. If such an outstanding find occurred in a game chosen at random - does this mean that in almost any game of that time there will be brilliant programming solutions, is it worth digging a little deeper? Steven Sidley compared the development for the Atari 2600, with its poor instruction set, 128 bytes of RAM, and 76 cycles per pixel row, to “climbing Everest without oxygen tanks” : the platform limitations themselves forced programmers to invent ingenious algorithms.
“Digging deeper” is not only a metaphor. The study of classic video games is complicated both by the fragility of the media on which they were recorded, and by the attitude to old games as to uninteresting garbage. In 1983 Atari fell out landfill 47 tons of cartridges for the Atari 2600 - at least a dozen full trucks! Crushed by an asphalt roller and poured from above with concrete, these cartridges lay for thirty years, until in 2014 the “digital archaeologists” received permission to excavate and remove the surviving cartridges. None of the dug cartridges worked, but at least one of them managed to be restored by re-soldering the components.
The behavior of Atari, which filled the cartridges with concrete in order to protect them from “thieves,” is very typical of copyright holders who are more likely to lose their groundwork forever than suffer a “lost profit” from the fact that their intellectual property will go to someone for free. But perhaps it is not too late to protect the “virtual cultural layer” of the 20th century by allowing free copying of programs that have long lost their commercial value?