Three Maze Generators on the Commodore 64
Back in the 1980s, memory was precious. With only kilobytes to work with, storing pre-designed levels was a luxury many games couldn’t afford.
One solution was to generate content on the fly using algorithms.
Three Algorithms, Three Approaches
Let’s examine three different maze generation algorithms, each with its own personality and implementation strategy.
Understanding how each works will deepen your appreciation for the art of procedural generation.
Setting Up the Grid
The first two maze examples use a 37×21 grid. Intentionally odd numbers to ensure walls and paths alternate properly:
40 DIM M(37,21):REM MAZE ARRAY (ODD DIMENSIONS)
We start with everything as “walls, creating a solid block of white characters on screen.
Memory mapped visuals so you can see what’s going on
When learning, there is value in seeing what’s happening as the program unfolds. 8-bit computers, being slow, have a distinct advantage over modern programming here, where you’d have to introduce considerable time delays to be able to see an algorithm like these run.
We’ll use screen memory for visual feedback:
POKE 1024+Y*40+X,160:REM WALL CHARACTER
POKE 55296+Y*40+X,1:REM WHITE COLOR
By POKEing values directly to screen memory (starting at 1024) and color memory (starting at 55296), we get a smooth, real-time animation.
Depth-First Search: The Explorer
DFS is like an eager explorer with tunnel vision. It picks a direction and commits, carving as far as possible before being forced to backtrack. This creates long, winding corridors that snake through the maze.
10 REM DFS MAZE GENERATOR FOR C64
15 REM MICHAEL DOORNBOS 2025
20 PRINT CHR$(147):REM CLEAR SCREEN
30 POKE 53280,0:POKE 53281,0:REM BLACK BORDER/BACKGROUND
35 V=1024:C=55296:REM SCREEN MEMORY AND COLOR MEMORY
40 DIM M(37,21):REM MAZE ARRAY (ODD DIMENSIONS)
50 REM INITIALIZE MAZE - ALL WALLS
60 FOR Y=0 TO 20:FOR X=0 TO 36
70 M(X,Y)=1:POKE V+Y*40+X,160:POKE C+Y*40+X,1
80 NEXT:NEXT
90 REM STARTING POSITION
100 X=1:Y=1:M(X,Y)=0
110 POKE V+Y*40+X,42:POKE C+Y*40+X,7:REM YELLOW ASTERISK
120 S=0:DIM SX(400),SY(400):REM STACK
130 REM MAZE GENERATION LOOP
140 D=0:REM COUNT UNVISITED NEIGHBORS
150 REM CHECK NORTH
160 IF Y>1 THEN IF M(X,Y-2)=1 THEN D=D+1
170 REM CHECK EAST
180 IF X<34 THEN IF M(X+2,Y)=1 THEN D=D+1
190 REM CHECK SOUTH
200 IF Y<18 THEN IF M(X,Y+2)=1 THEN D=D+1
210 REM CHECK WEST
220 IF X>1 THEN IF M(X-2,Y)=1 THEN D=D+1
230 IF D=0 THEN GOTO 450:REM BACKTRACK
240 REM CHOOSE RANDOM DIRECTION
250 R=INT(RND(1)*4)
260 REM TRY NORTH
270 IF R=0 AND Y>1 THEN IF M(X,Y-2)=1 THEN GOTO 350
280 REM TRY EAST
290 IF R=1 AND X<34 THEN IF M(X+2,Y)=1 THEN GOTO 370
300 REM TRY SOUTH
310 IF R=2 AND Y<18 THEN IF M(X,Y+2)=1 THEN GOTO 390
320 REM TRY WEST
330 IF R=3 AND X>1 THEN IF M(X-2,Y)=1 THEN GOTO 410
340 GOTO 250:REM TRY AGAIN
350 POKE V+Y*40+X,32:M(X,Y-1)=0:M(X,Y-2)=0
360 POKE V+(Y-1)*40+X,32:POKE V+(Y-2)*40+X,42:POKE C+(Y-2)*40+X,7
365 SX(S)=X:SY(S)=Y:S=S+1:Y=Y-2:GOTO 130
370 POKE V+Y*40+X,32:M(X+1,Y)=0:M(X+2,Y)=0
380 POKE V+Y*40+X+1,32:POKE V+Y*40+X+2,42:POKE C+Y*40+X+2,7
385 SX(S)=X:SY(S)=Y:S=S+1:X=X+2:GOTO 130
390 POKE V+Y*40+X,32:M(X,Y+1)=0:M(X,Y+2)=0
400 POKE V+(Y+1)*40+X,32:POKE V+(Y+2)*40+X,42:POKE C+(Y+2)*40+X,7
405 SX(S)=X:SY(S)=Y:S=S+1:Y=Y+2:GOTO 130
410 POKE V+Y*40+X,32:M(X-1,Y)=0:M(X-2,Y)=0
420 POKE V+Y*40+X-1,32:POKE V+Y*40+X-2,42:POKE C+Y*40+X-2,7
425 SX(S)=X:SY(S)=Y:S=S+1:X=X-2:GOTO 130
450 REM BACKTRACK
460 IF S=0 THEN GOTO 500
470 POKE V+Y*40+X,32:REM CLEAR CURRENT MARKER
480 S=S-1:X=SX(S):Y=SY(S)
490 POKE V+Y*40+X,42:POKE C+Y*40+X,7:GOTO 130
500 REM CLEAR FINAL MARKER AND ADD ENTRANCE/EXIT
510 POKE V+Y*40+X,32
520 POKE V+40,81:POKE C+40,5:REM ENTRANCE 'Q' GREEN
530 POKE V+18*40+34,81:POKE C+18*40+34,5:REM EXIT 'Q' GREEN
540 REM POSITION CURSOR BELOW MAZE
550 PRINT CHR$(19);:FOR I=1 TO 23:PRINT:NEXT
560 PRINT "DFS MAZE"
570 GET A$:IF A$="" THEN 570
How DFS Works:
- Start at position (1,1) and mark it as visited
- Check all four directions for unvisited cells (2 spaces away)
- Choose a random valid direction
- Carve a path to that cell AND the wall between them
- Push current position onto the stack
- Move to the new cell and repeat from step 2
- Backtrack when no valid moves exist by popping from the stack
- Continue until the stack is empty
The key to DFS is the stack—it remembers every position where we made a choice, allowing us to return and try different paths. This creates the characteristic long, meandering passages.
The DFS Approach: Stack-Based
DFS uses a stack (Last In, First Out) to remember where it’s been:
120 S=0:DIM SX(400),SY(400):REM STACK
When it hits a dead end, it pops positions off the stack to backtrack:
470 POKE 1024+Y*40+X,32:REM CLEAR CURRENT MARKER
480 S=S-1:X=SX(S):Y=SY(S)
Randomized Prim’s Algorithm: The Growing Tree
Prim’s algorithm takes a completely different approach. Instead of following a single path, it maintains a “frontier” of cells adjacent to the maze and randomly adds them, creating an organic, expanding pattern.
10 REM BFS PRIM'S MAZE GENERATOR FOR C64
15 REM MICHAEL DOORNBOS 2025
20 PRINT CHR$(147):REM CLEAR SCREEN
30 POKE 53280,0:POKE 53281,0:REM BLACK BORDER/BACKGROUND
35 V=1024:C=55296:REM SCREEN MEMORY AND COLOR MEMORY
40 DIM M(37,21):REM MAZE ARRAY
50 REM INITIALIZE MAZE - ALL WALLS
60 FOR Y=0 TO 20:FOR X=0 TO 36
70 M(X,Y)=1:POKE 1024+Y*40+X,160:POKE C+Y*40+X,1
80 NEXT:NEXT
90 REM RANDOMIZED PRIM'S ALGORITHM (BFS-LIKE)
100 DIM FX(400),FY(400):FC=0:REM FRONTIER CELLS
110 DIM NX(4),NY(4):REM NEIGHBOR ARRAYS
120 REM START AT 1,1 AND CLEAR IT
130 X=1:Y=1:M(X,Y)=0
140 POKE V+Y*40+X,32
150 REM ADD STARTING CELL'S NEIGHBORS TO FRONTIER
160 IF Y>2 THEN IF M(X,Y-2)=1 THEN FX(FC)=X:FY(FC)=Y-2:FC=FC+1:M(X,Y-2)=2
170 IF X<34 THEN IF M(X+2,Y)=1 THEN FX(FC)=X+2:FY(FC)=Y:FC=FC+1:M(X+2,Y)=2
180 IF Y<18 THEN IF M(X,Y+2)=1 THEN FX(FC)=X:FY(FC)=Y+2:FC=FC+1:M(X,Y+2)=2
190 REM MAIN LOOP
200 IF FC=0 THEN GOTO 490:REM DONE
210 REM PICK RANDOM FRONTIER CELL
220 R=INT(RND(1)*FC)
230 X=FX(R):Y=FY(R)
240 POKE V+Y*40+X,42:POKE C+Y*40+X,7:REM SHOW CURRENT
250 REM FIND VISITED NEIGHBORS TO CONNECT TO
260 N=0
270 IF Y>2 THEN IF M(X,Y-2)=0 THEN NX(N)=X:NY(N)=Y-2:N=N+1
280 IF X<34 THEN IF M(X+2,Y)=0 THEN NX(N)=X+2:NY(N)=Y:N=N+1
290 IF Y<18 THEN IF M(X,Y+2)=0 THEN NX(N)=X:NY(N)=Y+2:N=N+1
300 IF X>2 THEN IF M(X-2,Y)=0 THEN NX(N)=X-2:NY(N)=Y:N=N+1
310 REM CONNECT TO RANDOM VISITED NEIGHBOR
320 RN=INT(RND(1)*N)
330 CX=NX(RN):CY=NY(RN)
340 REM CARVE PATH TO NEIGHBOR
350 WX=(X+CX)/2:WY=(Y+CY)/2
360 M(X,Y)=0:M(WX,WY)=0
370 POKE V+Y*40+X,32:POKE V+WY*40+WX,32
380 REM ADD NEW FRONTIER CELLS
390 IF Y>2 THEN IF M(X,Y-2)=1 THEN FX(FC)=X:FY(FC)=Y-2:FC=FC+1:M(X,Y-2)=2
400 IF X<34 THEN IF M(X+2,Y)=1 THEN FX(FC)=X+2:FY(FC)=Y:FC=FC+1:M(X+2,Y)=2
410 IF Y<18 THEN IF M(X,Y+2)=1 THEN FX(FC)=X:FY(FC)=Y+2:FC=FC+1:M(X,Y+2)=2
420 IF X>2 THEN IF M(X-2,Y)=1 THEN FX(FC)=X-2:FY(FC)=Y:FC=FC+1:M(X-2,Y)=2
430 REM REMOVE FROM FRONTIER
440 FX(R)=FX(FC-1):FY(R)=FY(FC-1):FC=FC-1
450 REM SHOW FRONTIER IN RED
460 FOR I=0 TO FC-1:IF M(FX(I),FY(I))=2 THEN POKE C+FY(I)*40+FX(I),2
470 NEXT
480 FOR D=1 TO 30:NEXT:GOTO 200
490 REM CLEAN UP
500 FOR Y=0 TO 20:FOR X=0 TO 36
510 IF M(X,Y)<>1 THEN POKE C+Y*40+X,1
520 NEXT:NEXT
530 POKE V+40,81:POKE C+40,5:REM ENTRANCE
540 POKE V+18*40+34,81:POKE C+18*40+34,5:REM EXIT
550 PRINT CHR$(19);:FOR I=1 TO 23:PRINT:NEXT
560 PRINT "BFS MAZE"
570 GET A$:IF A$="" THEN 570
How Prim’s Works:
- Start with a single cell marked as part of the maze
- Add all neighboring cells (2 spaces away) to the frontier list
- Mark frontier cells with a special value (2) to track them
- Pick a random cell from the frontier
- Find which of its neighbors are already in the maze
- Connect to one random maze neighbor by carving the wall
- Add the cell’s unvisited neighbors to the frontier
- Remove the processed cell from the frontier
- Continue until the frontier is empty
The frontier visualization (red cells) shows the algorithm’s expanding wave pattern. Unlike DFS’s single active point, Prim’s considers multiple growth points simultaneously.
The Prim’s Approach: Frontier-Based
Randomized Prim’s algorithm maintains a “frontier” - cells adjacent to the maze but not yet part of it:
100 DIM FX(400),FY(400):FC=0:REM FRONTIER CELLS
The frontier expands as we add cells:
390 IF Y>2 THEN IF M(X,Y-2)=1 THEN FX(FC)=X:FY(FC)=Y-2:FC=FC+1:M(X,Y-2)=2
We mark frontier cells with value 2 to distinguish them from unvisited (1) and visited (0) cells.
The 1981 Algorithm
Here it is in action:
This algorithm is a variant of DFS, but with such clever optimizations that it deserves separate analysis. It achieves the same result using radically different techniques.
10 REM MAZE GENERATOR FOR C64
20 REM FROM P 54 OF COMPUTE! DEC 1981
30 REM BY CHARLES BOND
40 PRINT CHR$(147):REM CLEAR SCREEN
50 POKE 53280,0:POKE 53281,0:REM BLACK BORDER/BACKGROUND
99 REM ORIGINAL CODE FROM P54 OF MAG STARTS HERE
100 DIMA(3) : REM DIRECTION TABLE
110 A(0)=2:A(1)=-80:A(2)=-2:A(3)=80:REM 40 COLUMN SCREEN
120 WL=160:HL=32:SC=1024:A=SC+81:REM C64 SCREEN VALUES
130 PRINTCHR$(147)
140 FORI=1TO23
145 PRINTCHR$(18);
150 PRINT" "
160 NEXT
200 REM GENERATE THE MAZE
210 POKEA,4
220 J=INT(RND(1)*4):X=J
230 B=A+A(J):IFPEEK(B)=WLTHENPOKEB,J:POKEA+A(J)/2,HL:A=B:GOTO220
240 J=(J+1)*-(J<3):IF J<>XTHEN230
250 J=PEEK(A):POKEA,HL:IF J<4 THEN A=A-A(J):GOTO220
300 REM WAIT FOR KEYPRESS
310 GETC$:IFC$=""THEN310
1000 REM MAZE TRANSVERSAL PROGRAM
1010 POKEA,81:J=2
1020 B=A+A(J)/2:IFPEEK(B)=HLTHENPOKEB,81:POKEA,HL:A=B:J=(J+2)+4*(J>1)
1030 J=(J-1)-4*(J=0):GOTO1020
How the 1981 Algorithm Works:
- No coordinate system - Uses direct memory addresses instead of X,Y
- No separate maze array - The screen IS the maze
- Direction storage - Each cell stores which direction it was entered from (0-3 screen codes are @, A, B and C)
- Implicit backtracking - Reads the stored direction to go backwards
The Direction Storage:
When the algorithm carves a path to a new cell, it doesn’t just mark it as visited, it stores the direction it came from:
230 B=A+A(J):IFPEEK(B)=WLTHENPOKEB,J:POKEA+A(J)/2,HL:A=B:GOTO220
This line
- Calculates the new position (B=A+A(J))
- Checks if it’s a wall (PEEK(B)=WL)
- Stores the direction we came from (POKEB,J)
- Carves the wall between (POKEA+A(J)/2,HL)
- Moves to the new position (A=B)
Backtracking Without a Stack:
250 J=PEEK(A):POKEA,HL:IF J<4 THEN A=A-A(J):GOTO220
Instead of popping from a stack, it:
- Reads the stored direction (J=PEEK(A))
- Clears the current cell (POKEA,HL)
- Moves back using the inverse direction (A=A-A(J))
This is brilliantly efficient—the maze itself becomes the stack!
In my mind, this one is still the king of maze programs for 8-bit machines with mappable screen memory. I’ve been impressed with it since I was 7 years old, and it still makes me smile.
Maze Characteristics
The choice of algorithm significantly affects the resulting maze:
DFS Mazes
- Long, winding passages that can frustrate or delight players
- Dead ends throughout the maze at various depths
- Higher average solution length from the entrance to the exit
- River-like appearance with main passages and tributaries
- Better for adventure games where exploration is key
Prim’s Mazes
- Organic branching structure spreading from the center
- Shorter average paths between any two points
- More uniform distribution of passages
- Tree-like appearance with a clear root at the start
- Better for exploration games where you want multiple paths
Visual Comparison
The difference is immediately apparent when you watch them generate:
Perfect Mazes, Every Time
Despite their different approaches, both algorithms guarantee “perfect” mazes:
- No loops or circular paths
- Exactly one solution between any two points
- Every cell is reachable from every other cell
This happens because both algorithms visit each cell exactly once and only carve paths to unvisited cells, creating a spanning tree of the grid.
Choosing Your Algorithm
Which algorithm should you use? It depends on your goals:
Choose DFS when you want:
- Classic maze appearance
- Longer, more challenging solutions
- Minimal memory usage
- Traditional maze-solving experience
Choose Prim’s when you want:
- Organic, spreading growth pattern
- More balanced branching
- Visually interesting generation
- Moderate path lengths
Extra Credit
There is A LOT of room for speed improvements in these implementations. You can spend a considerable amount of time making them faster. Knock yourself out! (but show your work)
Some other ideas:
- Combine both algorithms for hybrid mazes
- Add bias to prefer certain directions
- Create rooms by carving larger spaces
- Implement a solver showing the solution path
- Add multiple start/end points
- Save interesting seeds for reproducible mazes
I still love this stuff
There’s something deeply satisfying about watching order emerge from chaos and seeing random decisions coalesce into intricate, navigable structures.
I first typed that Compute! magazine maze type in when I was single digits years old, and they continue to capture my attention.
Happy Hacking!