Q2 Computer - Maze Generator

A slightly longer example that demonstrates recursion. This makes some assumptions about values in the zero page, like the common functions.

.def  maze_width    20
.def  maze_height   16
.def  maze_data     0x080
.def  maze_stack    0x7FE

; Generate a maze.
; Destroys x0-x11
; Uses 0x080 for the maze array.
  .align  128
maze:
  sta   =x11

  ; Fill the maze array with 1s (walls).
  lda   maze_ptr
  sta   =x2
  lda   maze_size
maze_init:
  add   =neg1
  sta   =x1
  lea   =1
  sta   @=x2
  lea   =1
  add   =x2
  sta   =x2
  lda   =x1
  jfc   maze_init
  
  ; Draw 0s on all sizes.
  lda   maze_ptr
  sta   =x2
  lea   =maze_height
maze_init_lr:
  add   =neg1
  sta   =x1
  lea   =0
  sta   @=x2
  lea   =maze_width
  add   =x2
  sta   =x2
  lda   =x1
  jfc   maze_init_lr
  lda   maze_ptr
  sta   =x2
  lda   maze_bottom
  sta   =x3
  lea   =maze_width
maze_init_tb:
  add   =neg1
  sta   =x1
  lea   =0
  sta   @=x2
  sta   @=x3
  lea   =1
  add   =x2
  sta   =x2
  lea   =1
  add   =x3
  sta   =x3
  lda   =x1
  jfc   maze_init_tb

  ; Carve the maze
  lda   maze_stack_ptr
  sta   =x9
  lda   maze_start
  sta   =x5
  lea   $+3
  jmp   @$+1
  .dw   maze_carve

  ; Carve out start/end
  lda   maze_entry
  sta   =x0
  lea   =0
  sta   @=x0
  lda   maze_exit
  sta   =x0
  lea   =0
  sta   @=x0

  ; Return
  jmp   @=x11

maze_size:
  .dw   maze_width * maze_height
maze_bottom:
  .dw   maze_data + maze_width * maze_height
maze_start:
  .dw   maze_data + (maze_width * 2) + 2
maze_entry:
  .dw   maze_data + maze_width + 2
maze_exit:
  .dw   maze_data + (maze_width * (maze_height - 1)) + maze_width - 2
maze_ptr:
  .dw   maze_data
maze_stack_ptr:
  .dw   maze_stack

  .align  128
; Carve maze at x5, using x9 as a call stack
; Carve attempts remaining in x7
; Direction in x8
maze_carve:

  ; Push return address.
  sta   @=x9
  lda   =x9
  add   =neg1
  sta   =x9

  ; Mark the current location.
  lea   =0
  sta   @=x5

  ; Get a random number in x8.
  lea   $+3
  jmp   @$+1
  .dw   rand    ; Destroys x0-x4
  sta   =x8

  lea   =4
maze_carve_loop:
  add   =neg1
  sta   =x7

  ; Offset in x0.
  lda   =x8
  nor   =zero
  sta   =x0
  lda   maze_offset_mask
  nor   =x0
  add   maze_offsets_ptr
  sta   =x0
  lda   @=x0
  sta   =x0

  lda   =x5
  add   =x0
  sta   =x1   ; First move in x1
  add   =x0
  sta   =x10  ; Second move in x10

  ; Check if we already carved here.
  lda   @=x1
  jfc   $+2
  jmp   maze_carve_next
  lda   @=x10
  jfc   $+2
  jmp   maze_carve_next

  ; Carve.
  lea   =0
  sta   @=x1

  ; Push x8, x7, x5
  lda   =x8
  sta   @=x9
  lda   =x9
  add   =neg1
  sta   =x9
  lda   =x7
  sta   @=x9
  lda   =x9
  add   =neg1
  sta   =x9
  lda   =x5
  sta   @=x9
  lda   =x9
  add   =neg1
  sta   =x9

  ; Carve at x10
  lda   =x10
  sta   =x5
  lea   $+2
  jmp   maze_carve

  ; Pop x5, x7, x8
  lea   =1
  add   =x9
  sta   =x9
  lda   @=x9
  sta   =x5
  lea   =1
  add   =x9
  sta   =x9
  lda   @=x9
  sta   =x7
  lea   =1
  add   =x9
  sta   =x9
  lda   @=x9
  sta   =x8

maze_carve_next:
  lea   =1
  add   =x8
  sta   =x8
  lda   =x7
  jfc   maze_carve_loop

  ; Return.
  lea   =1
  add   =x9
  sta   =x9
  lda   @=x9
  sta   =x0
  jmp   @=x0

maze_offsets:
  .dw   1
  .dw   -1
  .dw   maze_width
  .dw   -maze_width
maze_offsets_ptr:
  .dw   maze_offsets
maze_offset_mask:
  .dw   0xFFC
maze_ptr_carve:
  .dw   maze_data