Re: a Maze generator program
Posted: Wed Nov 04, 2020 1:05 pm
What about some screenshots of the maze for the poor people of us?
The Commodore Vic 20 Forum
http://www.sleepingelephant.com/ipw-web/bulletin/bb/
http://www.sleepingelephant.com/ipw-web/bulletin/bb/viewtopic.php?t=2783
There's a lot of great information on the Wikipedia page for maze generation algorithms, including both static pictures and video demonstrations.
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
This maze generator had been published in Compute! and has been discussed in another thread,MIRKOSOFT wrote:Or mod this C128 program - few commands - no problem: [...]