CODEX
Random maze from Entombed
A mysterious algorithm from Atari 2600 to Commodore 64
Thanks to a random Twitter list I have found an interesting paper and I have become aware of the existence of a field of research called Archeogaming which uses the approaches and the methodology coming from archeology, historiography, and software engineering to dissect and analyze the design and the implementation of ancient video games.
The paper is Entombed: An archaeological examination of an Atari 2600 game and is a first, successful (in my opinion) attempt to formalize the Archeogaming field of research.
The paper is really interesting and it is fun to read and, as the title suggests, it provides a detailed analysis of the implementation of the videogame Entombed for Atari 2600: I will not go in details here because the paper has everything you need to know well explained but, for the sake of clarity, you just need to know that the game is about a character, driven by the player, that has to run across a randomly generated maze.
The emphasis on the word randomly is because having a different maze on every new game would greatly benefit the replayability of the game, that is the fact of being suitable for or worth playing more than once.
The generation of a new line of the maze
In the video is clearly shown how the game works: the player has to keep moving downward while the maze scrolls toward him. The maze is composed by
The algorithm provides a simple way to generate a new line of the maze as long as it scrolls upward. The maze is 20 blocks wide and each line of the maze has the two leftmost and rightmost blocks always occupied by a wall.
Every new line is a function of the line immediately above and it has to fill the remaining 16 blocks of the line. Another simplification, which also adds some kind of aesthetic to the generated maze, is the fact that only 8 leftmost blocks are generated while the remaining 8 blocks are just the same blocks but mirrored: in the next figure you can see a schematic representation of the algorithm.
Drunk late-night programming
The generation of each new block takes into account the context of that block. In the next figure you can see how this happens: to generate the block in position X the content of the blocks in position a,b,c,d,e is considered.
The algorithm uses a table to decide the content in block X the table has an entry for each combination of the blocks. In the following figure you can see the first 12 rows the table:
It is worth noting that the table, is dubbed as Mystery table in the paper because there is no clear pattern describing how the rows were defined nor the original programmer was able to recall how he actually did it because “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”
Each row of the table, depending on the values of the cells in the position a,b,c,d, and e, contains a 0, 1, or random: 0 means that the x cell will contain empty space, in which the player’s character will be able to walk; 1 will generate a wall block in the x cell and random will randomly generate a block or space.
Porting to Commodore 64 Basic
Porting to Commodore 64 Basic v2 in the 21st century is an interesting job. At the core, there is the Mystery table that has been rendered as an array loaded from that DATA statement of C64 Basic. Another detail of the C64 version is that it uses the standard random number generator instead of the implementation of a pseudo-random number generator, as described in the paper.
Following you will find the source code in pure C64 Basic:
10 DIM Z(31):FOR I=0 TO 31:READZ(I):NEXTI:?"{CLEAR}":S=1986:K=102
20 FOR I=0TO1:POKE 1984+I,K:POKE2003-I,K:NEXT I
30 FOR X=S TO 1993
40 A=-(PEEK(X-2)>32)*16:IF X=S THEN A=16
50 B=-(PEEK(X-1)>32)*8:IF X=S THEN B=0
60 C=-(PEEK(X-41)>32)*4:IF X=S THEN C=INT(RND(1)+.5)*4
70 D=-(PEEK(X-40)>32)*2
80 E=-(PEEK(X-39)>32)
90 V=Z(A+B+C+D+E):IF V=2 THEN V=(INT(RND(1)+.5))
100 IF V=1 THEN POKEX,K:POKE3987-X,K
110 NEXT X:SYS 59626:GOTO 20
120 DATA 1,1,1,2,0,0,2,2,1,1,1,1,2,0,0,0
130 DATA 1,1,1,2,0,0,0,0,2,0,1,2,2,0,0,0Line 10 — Initialization of the array Z that contains the Mystery table with data read from lines 120–130. Initialization of a couple of variables: S is the first position generated by the algorithm (two cells rightward to the lower-left screen cell)
Line 20 — Draws the two cells stripes on the leftmost and rightmost part of the newly generated line, which is always the lowest line on the screen
Line 30 — Here it begins the proper drawing cycle whose body finishes on line 110. On each line is calculated the value for a,b,c,d, and e by PEEKing in the C64 screen memory. The five values are combined in a bit string whose value, as an integer, is used for the index to select the proper line in the Mystery table, kept in an array Z().
Lines 40 to 80 — Calculate the letters a,b,c,d, and e. Note that lines 40, 50, and 60 a special check is performed: as described in the original paper, the leftmost cell of the new line of the maze is calculated differently because a, b and c will coincide with the always present two cells stripe (generated on line 20). The values, in this special case, are a=1, b=0, and c equal to a random number between 0 and 1.
Line 90 — Recover the proper line Z by adding a,b,c,d, and e. If the value the array Z() is 2 then the cell can be randomly empty or full.
Line 100 — Draw a cell if, in the previous line, we got a 1 from the lookup in the table or generated it: in this case the cell, at the address X, is POKEd with the character whose code is kept in K.
Line 110 — Close the cycle. The SYS call will just scroll upward the screen adding a blank line. The GOTO will restart the cycle drawing a new line of the maze.
The result is shown in the following image, your run will (hopefully) be different.
Conclusion
Where to move on from here, a couple of hints: the code presents can be compressed in order to have a compact version and, maybe, participate in the BASIC TENLINER CONTEST. An example is the following code (CAVEAT: not totally functionally equivalent to the previous) that runs on just 5 lines of code:
10dIZ(31):fOI=0TO31:rEZ(I):nE:?"{CLEAR}":S=1986:K=102:
20fOI=0TO1:pO1984+I,K:pO2003-I,K:nE:fOX=STO1993
40V=Z(-(pE(X-2)>32)*16-(pE(X-1)>32)*8-(pE(X-41)>32)*4-(pE(X-40)>32)*2-(pE(X-39)>32)):IFV=2tHV=INT(rN(1)+.5)
50IF V=1 THEN POKEX,K:POKE3987-X,K
60NEXT:SYS59626:gO20:dA1,1,1,2,,,2,2,1,1,1,1,2,,,,1,1,1,2,,,,,2,,1,2,2,,,The code above, which can still be compressed, even more, leaves room for adding the game logic, for a fully functional Entombed clone.
