So I’ve had certain fascination with maze making since I was a kid and have filled many pages of graph paper with mazes to be solved by friends. When I first watched a computer create a maze I was fascinated by how it started by drawing a path and then backed up to an unused area of the screen to continue to build the maze until it was done.

The Recursive Backtracking Wanderer

Most computer generating mazes I’ve seen involve the Random Wanderer and Recursive Backtracker algorithms. The way these work is that you start with a grid of cells and start at a random location.

Next, pick a random direction for your wanderer to travel. In this case, North was chosen. When wandering, the main rule is that you can’t wander into a cell that has already been visited. Since only the starting cell has been visited at this point, North is a perfectly fine direction to go. As the wanderer travels North, the walls that separate the two cells are removed. This will start building a path and the location of the wander is stored on a stack to revisit later.

The wanderer keeps wandering until the it gets trapped because every direction around has already been visited.

The wanderer then backtracks one cell to see if itcan start wandering again.

It continue wandering and backtracking when trapped until the wanderer has backtracked to the starting point. Once it hits the starting point, the maze will be finished.

When creating a maze using this logarithm, every cell is visited twice. Once on the initial wandering and again when backtracking back.

To see this in action, I’ve included a BASIC program that can be run. This program uses some custom characters to draw the maze so it’s a little slow to get started. Once it’s running, you can see the process of wandering and backtracking pretty easily.

Here is a breakdown of the program.

Here’s a full listing and the .d64.

100 rem maze2d test
110 rem Michael Cassera
120 rem
130 rem copy characters from rom
140 poke52,48:poke56,48
145 cr=53248:nc=12288:ca=54272
148 poke53272,29
150 poke56334,peek(56334)and254
160 poke1,peek(1)and251
170 fori=0to2023:pokei+nc,peek(i+cr):nexti
180 poke1,peek(1)or4
190 poke56334,peek(56334)or1
195 forn=80to95:poke1024+n,n:poke1024+n+40,n+128:next
200 fori=640to767:reada:pokei+nc,a:pokei+nc+1024,255-a:nexti
210 printchr$(147)
215 poke53280,6:poke53281,6
220 forn=1064to1983:poken,95:poken+ca,12:next
230 forn=1025to1062:poken,82:poken+960,88:poken+ca,14:poken+ca+960,14:nextn
240 forn=1064to1983step40:poken,81:poken+39,84:poken+ca,14:poken+ca+39,14:nextn

Lines 100 to 240 basically shift the character definitions to RAM, copies the characters from ROM and then programs a few key graphic characters into specialized characters for displaying the maze. It then draws a graph on the screen (in grey) to create the maze in. Much of this program was taken from the Commodore 64 Programmer Reference Guide and its section on programmable characters.

250 rem start maze building
260 z=rnd(-ti):ss=49152
270 x=int(rnd(1)*38)+1:y=int(rnd(1)*22)+1

260 seeds the random number generator and sets the stack pointer to 49152. The stack is where we are going to store our x and y locations when we need to backtrack in the maze.

270 picks the starting point of our wanderer on the grid.

275 pokess,x:pokess+1,y:ss=ss+2
280 sb=1024+x+(y*40)
285 pokesb+ca,peek(sb+ca)+1

275 starts our wandering loop. It stores our current x an y coordinates on the stack and increases the stack pointer by two.

280 converts the x and y coordinates into a byte on the C64 screen and 285 changes the color of the cell we are occupying by adding 1 to it. This will cause a grey (un-visited) cell to turn light green (visited once) to light blue (visited twice). By the end of the program, all cells should be visited twice and the maze will be light blue.

290 d$=""
300 ifpeek(sb+1)=95thend$=d$+"e"
310 ifpeek(sb+40)=95thend$=d$+"s"
320 ifpeek(sb-1)=95thend$=d$+"w"
330 ifpeek(sb-40)=95thend$=d$+"n"
340 d=len(d$):ifd=0then500

Lines 290 to 340 help the wanderer determine which directions are available to go. It does this by clearing d$ and checking the screen character in each direction. If the computer returns a 95 (the empty cell character) the computer adds that direction to d$ for later processing. d$ can have the length between zero (no directions) to four (“eswn”). If only one, two or three are available, then only the directions available will be part of d$. If len(d$) = 0 then the program jumps to the backtracker part of the routine.

350 d2=int(rnd(1)*d)+1:m$=mid$(d$,d2,1)
360 ifm$="n"theny=y-1:cp=8:np=2:sd=-40
370 ifm$="s"theny=y+1:cp=2:np=8:sd=40
380 ifm$="e"thenx=x+1:cp=1:np=4:sd=1
390 ifm$="w"thenx=x-1:cp=4:np=1:sd=-1

350 to 390 chooses a direction and sets some variable to make it happen. 350 selects one of the allowable directions and sets m$ with the direction. Then a series of conditional statements adjust the x and y parameters as well as set up some variable to affect the display.

cp and np correspond to the bit that represent a piece of the maze. To illustrate this, it helps to look at the custom characters and how they are arranged. Looking at the arrangement matrix to the left, you can see that the single line sides all correspond to a single bit in the nibble that represents the character. The right line is 0001 (d. 1), bottom 0010 (d. 2), left 0100 (d. 4), and the top is 1000 (d. 8). So cp is assigned the bit that is to be taken away from the current position and np is assigned to the bit that is to be taken away from the new position.

For example, if we are starting with a new maze, the current location would have a character with the nibble 1111 (the screen is filled with them to make the graph). If we then wander one square east, the bit that we would remove from our current position would be the right line or bit 0001 (d. 1) and the the bit we would remove from our new position would be the left one which would be 0100 (d. 4).

Finally, sd is assigned the value to locate the new position byte on the screen to change its character. Left and right are plus/minus 1 and up and down are plus/minus 40.

This all comes together in the next three lines of the code.

400 ch=((peek(sb)-80)and(255-cp))+80
410 cj=((peek(sb+sd)-80)and(255-np))+80
420 pokesb,ch:pokesb+sd,cj
430 goto275

Line 400 and 410 do the visual work for the screen. As mentioned, we need to change the character at the current and future location to show a break in the wall. The variable ch gets the current character located in our current position and subtracts 80 from it because our first custom character starts at screen code 80. The effectively changes the number to a nibble of information that represent the characters in the matrix displayed above. It then does an AND function with the inverse of the bit we want to remove.

For example, we want to remove just the top line from the character displayed. If the character was a full square, the peek of the screen position would give us 95 which we would then subtract 80 from it to give us 15 which is the nibble 1111. The character with the top line is 1000 (d. 8). To invert it, we need to subtract the nibble from the full byte. So 255-8 gives us 247 or 11110111. We then do the AND function between 15 and 247. In binary it looks like this:

 15   00001111   AND
247   11110111
---------------
  7   00000111

The result is 7, which is the character with the top line missing. 80 is added to the new nibble to create the final new character value of 87. This new value is then poked into the screen byte making it look like we removed a wall on the graph. Line 400 does the current position and line 410 does the new position with line 420 poking the new values onto the screen.

With the new position now displayed on the screen we loop back up to line 275 where we store the new location on the stack and pick a new direction.

Backtracking: (not recursive)

If the wanderer got stuck with nowhere to go, the backtrack part of the algorithm will then step in to get it back on track (no pun intended).

500 rem backtrack
510 ss=ss-2:ifss=49152then600
520 x=peek(ss):y=peek(ss+1)
530 goto280

Pretty simple routine here. The computer drops the stack counter back 2 bytes and loads x and y with the saved position. It then goes back to the main loop to check if there are any positions it can wander to. If not, it drops down to here again and backs up another position. This repeats until the wanderer can start traveling again.

While the routine is called the recursive backtracker, this version is not recursive. Commodore BASIC is not capable of running recursive routines so this is written as a simple loop. To make it work, we’ve had to create and maintain our own stack. In a recursive language, this would be handled automatically.

END GAME

Line 510 in the backtracker routine checks to see if the stack has gotten back to the beginning of memory, in this case, 49152. If it has, all cells have been visited twice and there is no more room to wander and the program is done.

For this program we’ve added a little bit of cleanup:

600 rem we're done
602 x=peek(ss):y=peek(ss+1)
604 sb=1024+x+(y*40)
605 pokesb+ca,peek(sb+ca)+1
610 s1=int(rnd(1)*22)+1:s2=1024+(s1*40)+1
615 e1=int(rnd(1)*22)+1:e2=1024+(e1*40)+38
618 pokes2,((peek(s2)-80)and251)+80:pokes2-1,80
619 pokee2,((peek(e2)-80)and254)+80:pokee2+1,80
620 forn=0to5000:nextn
630 z=fre(0)
640 goto215

Lines 602-605 pull the last location off the stack and turn the character blue. Then lines 610 and 615 choose a start and end to the maze on the left and right side of the screen and 616 and 619 open the respective start and start locations on the maze.

Line 620 does a moderate delay before line 630 does garbage collection and line 640 goes to start a new maze.

A note on garbage collection. Because this program uses string variables to designate and choose directions, a lot of RAM is used over the course of making the maze. This is a product of how Commodore BASIC stores string variable and redefining a string will just take more memory instead of replacing the same memory with data. This gives the programmer a lot of flexibility when working with strings because the length doesn’t need to be declared ahead of time and can be changed dynamically in the program like it is in this one. Doing a FRE() function anytime during program execution activates BASIC’s garbage collection routine and resets the pointers for string memory freeing up space. I’ve made it a habit to do this in my BASIC programs. While BASIC will do it on its own when the string pointer hits variables at the end of your program, I like to have it a little more controlled.

Finally, all that’s left in the program is the definitions of the custom characters.

10000 data0,0,0,0,0,0,0,0
10010 data1,1,1,1,1,1,1,1
10020 data0,0,0,0,0,0,0,255
10030 data1,1,1,1,1,1,1,255
10040 data128,128,128,128,128,128,128,128
10050 data129,129,129,129,129,129,129,129
10060 data128,128,128,128,128,128,128,255
10070 data129,129,129,129,129,129,129,255
10080 data255,0,0,0,0,0,0,0
10090 data255,1,1,1,1,1,1,1
10100 data255,0,0,0,0,0,0,255
10110 data255,1,1,1,1,1,1,255
10120 data255,128,128,128,128,128,128,128
10130 data255,129,129,129,129,129,129,129
10140 data255,128,128,128,128,128,128,255
10150 data255,129,129,129,129,129,129,255

So that’s maze building. For my 3d maze generator, I did things a little different with the size of the walls and open spaces being equal (image right). The resulting maze is a little different and generates a different 3d look than this algorithm will. Moving forward, my version two of 3d maze will be incorporating this style of maze to create a better 3d look.

-Michael