a Maze generator program

[Noizer]

What about some screenshots of the maze for the poor people of us?

[chysn]

What about some screenshots of the maze for the poor people of us?

There's a lot of great information on the Wikipedia page for maze generation algorithms, including both static pictures and video demonstrations.

My game TRBo: Turtle RescueBot uses the Sidewinder algorithm (http://weblog.jamisbuck.org/2011/2/3/ma ... -algorithm) to generate a maze with a guaranteed solution. Depending on its orientation, Sidewinder's output looks and functions like a 2D building, or underground maze, since it's all connected at a single level.

When I design a game, the game board is the first thing. The maze generation mechanism is instrumental to suggesting the mechanics of the game, much like tempo and instrumentation suggest the genre of a song. This in turn leads to the theme of the game, and the graphics, etc.

So much depends on following the mazes.

[chysn]

This thing took me four attempts, meaning that I discarded everything and started from a blank file three times, working on and off over a period of like six months. It's conceptually simple, but had some little problems that just took me a while to wrap my head around. For one thing, how do you pick a 1 bit at random from a bitfield, which can have any number of 1 bits? I tried various methods, but settled on, basically, brute force.

This is an "iterative depth-first" maze generator. It starts from a specified cell, puts the cell location on the stack, and then knocks out a random wall to an unvisited cell. When it reaches a dead end, it pops the previous cell off the stack and looks for a wall to knock out from there. Once it reaches the starting cell again (a.k.a., clears the stack), the maze is done. This method guarantees that all cells are connected, and it tends to create a maze with a single super-long passage and shorter branches.

It uses memory (here, ROM) for pseudo-random numbers, so the mazes are deterministic. This way, I can curate levels for my game.

Code: Select all

; Maze Generator
; 
; Create a deterministic depth-first maze
;
; by Jason Justian 2021; Permission is granted to use this code
; for any purpose.

; Configuration
HEIGHT    = 17                  ; Size of maze, with each cell having a "wall"
WIDTH     = 19                  ; surrounding it. So a 16x16 maze has 8x8 cells
X_OFFSET  = 1                   ; Placement of the maze on the screen
Y_OFFSET  = 5                   ; ,,
SEED      = $c000               ; Start of pseudo-random data table
CHR_WALL  = $20                 ; Wall character
CHR_OPEN  = $a0                 ; Open character

; Constants
NORTH     = 1
EAST      = 2
SOUTH     = 4
WEST      = 8

; System Resources
SCPAGE    = $0288               ; Screen location start page

; Memory
COOR_Y    = $f9                 ; y coordinate
COOR_X    = $fa                 ; x coordinate
PTR       = $fb                 ; Screen pointer (2 bytes)
LEVELS    = $fd                 ; Number of levels on the stack
P_RAND    = $fe                 ; Pointer to pseudorandom table (2 bytes)
SCRPAD    = $f8                 ; Value scratchpad

* = $1800
; Initialize Maze
; Draw the maze on the screen using the configured height, width, and offsets.
; Starting point is at (x,y), where X is the x position and Y is the y position,
; both zero-indexed.
MakeMaze:   lda #<SEED          ; Seed pseudorandom table
            sta P_RAND          ; ,,
            lda #>SEED          ; ,,
            sta P_RAND+1        ; ,,
            txa                 ; Store the specified x and y coordinates
            pha                 ;   for starting point pop
            tya                 ;   ,,
            pha                 ;   ,,
            lda #1              ; Set the number of levels on the stack to 1
            sta LEVELS          ; ,,
pop_cell:   pla                 ; Pop a cell's coordinates off the stack
            sta COOR_Y          ;   ,,
            pla                 ;   ,,
            sta COOR_X          ;   ,,
visit:      lda #CHR_OPEN       ; Visit the cell
            jsr PlotChar        ; ,,
            jsr CheckAdj        ; Check adjacent cells for unvisited neighbors
            bne move            ; If no cells are unvisited, this is a dead end,
deadend:    dec LEVELS          ;   so decrement the level counter and get the
            bne pop_cell        ;   next cell. If there are no more cells on the
            rts                 ;   stack, the maze is finished
move:       sta SCRPAD          ; Choose a direction from the CheckAdj bitfield
next_rand:  ldx #0              ;   * Get a pseudorandom number between 0 and 3
            lda (P_RAND,x)      ;     ,,
            and #$03            ;     ,,
            tay                 ;     ,,
            inc P_RAND          ;   * Increment the pseudorandom table counter
            bne get_sp          ;     ,,
            inc P_RAND+1        ;     ,,
get_sp:     lda BitNumber,y     ;   * See if the selected bit is one of the
            bit SCRPAD          ;     options for the new direction
            beq next_rand       ;     If it isn't, get a new p-random number
open_wall:  pha                 ; Move to cell based on coordinates and
            jsr MoveCoor        ;   knock out wall
            lda #CHR_OPEN       ;   ,,
            jsr PlotChar        ;   ,,
            pla                 ; Now move from the wall to the actual cell
            jsr MoveCoor        ; ,,
            lda COOR_X          ; Once the coordinates have been moved, push
            pha                 ;   the updated cell onto the stack, increment
            lda COOR_Y          ;   the level counter, and go back to visit
            pha                 ;   the new cell
            inc LEVELS          ;   ,,
            jmp visit           ;   ,,

; Move Coordinate
; Based on compass point in A
MoveCoor:   cmp #NORTH          ; Check each compass point and, if selected,
            bne ch_east         ;   move the appropriate coordinate
            dec COOR_Y          ;   ,,
ch_east:    cmp #EAST           ;   ,,
            bne ch_south        ;   ,,
            inc COOR_X          ;   ,,
ch_south:   cmp #SOUTH          ;   ,,
            bne ch_west         ;   ,,
            inc COOR_Y          ;   ,,
ch_west:    cmp #WEST           ;   ,,
            bne move_r          ;   ,,
            dec COOR_X          ;   ,,
move_r:     rts            
            
; Plot Character
; To coordinates
; Write character in A           
PlotChar:   pha                 ; Save character for later
            jsr Coor2Ptr        ; Put coordinate in pointer
            pla                 ; Get back the PETSCII character
            ldx #0              ; Put the character on the screen
            sta (PTR,x)         ; ,,
            rts
            
; Coordinates to Pointer
; Set PTR and PTR+1 with screen memory address referenced by the
; x and y coordinates, plus x and y offset values.
Coor2Ptr:   lda SCPAGE          ; Start at the upper left corner of the screen
            sta PTR+1           ; ,,
            lda #0              ; ,,
            sta PTR             ; ,,
            lda COOR_Y          ; Get y coordinate
            clc                 ; Add the y offset
            adc #Y_OFFSET       ; ,,
            beq no_y            ; If there's no offset, skip multiplication
            tay                 ; Y is the row index
-loop:      lda #22             ; Drop to the next line...
            clc                 ; ,,
            adc PTR             ; ,,
            sta PTR             ; ,,
            bcc next_y          ; ,,
            inc PTR+1           ; ,,
next_y:     dey                 ; ...Y times
            bne loop            ; ,,
no_y:       lda COOR_X          ; Get x coordinate
            clc                 ; Add the x offset
            adc #X_OFFSET       ; ,,
            adc PTR             ; Add it to the pointer
            sta PTR             ; ,,
            bcc t2p_r           ; ,,
            inc PTR+1           ; ,,
t2p_r       rts

; Is Cell Available (a.k.a. Unvisited)
; Set carry if cell is available
IsAvail:    lda COOR_X          ; Range-checking
            bmi unavail         ; ,,
            cmp #WIDTH          ; ,,
            bcs unavail         ; ,,
            lda COOR_Y          ; ,,
            bmi unavail         ; ,,
            cmp #HEIGHT         ; ,,
            bcs unavail         ; ,,
            jsr Coor2Ptr        ; Convert coordinates to pointer
            ldx #0              ; Get character at pointer
            lda (PTR,x)         ; ,,
            cmp #CHR_WALL       ; If it's a wall, it's available
            beq avail           ; ,,
unavail:    clc                 ; Clear carry means unavailable
            rts                 ; ,,
avail:      sec                 ; Set carry means available
            rts                 ; ,,
            
; Check Adjacent Cells for Unvisited Neighbors
; Based on the current coordinates
; Unvisited neighbors are returned in A, as
; Bit 0 - North is unvisited
; Bit 1 - East is unvisited
; Bit 2 - South is unvisited
; Bit 3 - West is unvisited
CheckAdj:   lda #0              ; Reset scratchpad to keep track of directions
            sta SCRPAD          ; ,,
av_west:    dec COOR_X          ; Check West
            dec COOR_X          ; ,,
            jsr IsAvail         ; ,,
            rol SCRPAD          ; ,,
            inc COOR_X          ; Reset
            inc COOR_X          ; ,,
av_south:   inc COOR_Y          ; Check South
            inc COOR_Y          ; ,,
            jsr IsAvail         ; ,,
            rol SCRPAD          ; ,,
            dec COOR_Y          ; Reset
            dec COOR_Y          ; ,,
av_east:    inc COOR_X          ; Check East
            inc COOR_X          ; ,,
            jsr IsAvail         ; ,,
            rol SCRPAD          ; ,,
            dec COOR_X          ; Reset
            dec COOR_X          ; ,,
av_north:   dec COOR_Y          ; Check North
            dec COOR_Y          ; ,,
            jsr IsAvail         ; ,,
            rol SCRPAD          ; ,,
            inc COOR_Y          ; Reset
            inc COOR_Y          ; ,,
            lda SCRPAD          ; A is return value
            rts
            
BitNumber:  .byte %00000001, %00000010, %00000100, %00001000

Here's an example result:

Here's a BASIC program for testing. I just realized that it assumes wAx is running in lines 30 and 40, but those are easily replaced with POKEs of register values and SYS.

And a demo video, with a delay added right before the jmp visited line: https://www.youtube.com/watch?v=41sFQlyjV6U

[MIRKOSOFT]

Try this:

(you can break it anywhere)

10 print chr$(205.5+rnd(1)); :goto10

Or mod this C128 program - few commands - no problem:

100 dim j,a,b,x,wl,hl,a(3)
110 a(0)=2:a(1)=-80:a(2)=-2:a(3)=80
120 wl=160:hl=32:sc=1024:a=sc+81:ym=11:xm=19
130 graphic0:print"{CLEAR}"
140 fori=1to1+2*ym:print"{REVERSE ON}";
150 forx=1to1+2*xm:print" ";:next
160 print:nexti:graphic5
170 fori=1to(xm+ym)/2:x=int(rnd(1)*xm):y=int(rnd(1)*ym)
180 poke a+y*a(3)+x*2,hl:next
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):ifj<>xthen230
250 j=peek(a):pokea,hl:ifj<4thena=a-a(j):goto220
300 a=sc+81
310 fori=1toxm+ym:do:x=int(rnd(1)*(xm-1)):y=int(rnd(1)*(2*ym-1))
320 j=a+y*a(3)/2+x*2-(yand1)+1:loop whilepeek(j)=hl:poke j,hl:next


Miro

[chysn]

Try this:

(you can break it anywhere)

10 print chr$(205.5+rnd(1)); :goto10

Ah, yes, a classic!

I remember also doing it with 182.5.

[Mike]

Or mod this C128 program - few commands - no problem: [...]

This maze generator had been published in Compute! and has been discussed in another thread,

"Compute! Maze Generator in Basic, C and now Assembly!!!"

here in Denial, resulting in several flavours - text mode and graphics, several languages, several platforms, spaghetti code or structured, etc.

Take your pick.

[chysn]

For games, the strict depth-first algorithm generates mazes that are slightly annoying. You can go long distances without hitting any intersections because the algorithm can go quite some distance before hitting its first dead end.

Remove a few walls after generation to improve a depth-first maze. Pick a random location, and clear it. You don't need to check for a wall at that location, just clear it. Do this a number of times equal to about 3% of the number of characters in the maze (for example, ten iterations in a 16x22 maze). It doesn't take the removal of many walls to turn a closed maze into a more interesting one with loops and maybe some little rooms.

[malcontent]

Yes, I used the Compute algo for Katabatia (c64) and dropping rooms in later greatly increases how good of a maze it is. It still suffers from a few long passages and zig-zag paths, but it is much better. You can also pre-seed the map with different patterns and the algo will chug away and do it's best around the data to different effects.

[furroy]

Bit of a necro post, but I couldn't get the asm version posted above to work until I changed:

Coor2Ptr: lda SCPAGE // Start at the upper left corner of the screen

to

Coor2Ptr: lda #>SCPAGE // Start at the upper left corner of the screen

[Mike]

chysn's original source code above is correct, and unless you also had changed the assignment "SCPAGE = $0288" to either "SCPAGE = $1E00" (for an unexpanded or +3K expanded VIC-20) or "SCPAGE = $1000" (for +8K RAM expansion or more), your code change does not make any sense. On most assemblers a change to "lda #>SCPAGE" will load the high byte of the symbol value into A. This is $02 for the original source, and this value is completely unrelated to the high byte of the screen base address.

The KERNAL holds the high byte of the current screen base address in $0288, which is referenced as intended by "lda SCPAGE". This works regardless which amount of RAM is present.

[furroy]

oh haha yea i moved screen ty for the extra insight!