Three Maze Generators on the Commodore 64

By Michael Doornbos

May 30, 2025 - 10 minutes read - 1925 words

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

In the December 1981 issue of Compute, Charles Bond published a very clever program that we’ve discussed in detail in previous articles.

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!