; maze solving example
; recursive backtracking
; for win2c64 by Aart Bik
; http://www.aartbik.com/

;
; encode SYS 2064 line in BASIC program space
;
        .org  $0801                          
        .byte     $0c $08 $0a $00 $9e $20 $32
        .byte $30 $36 $34 $00 $00 $00 $00 $00
lab2064 jmp main

;
; define the maze
;   place - at start
;   place + at goal
;   place 0 at walls
; program will find path - -> + (if it exists)
;
maze   .byte "0000000000000000000000000000000000000000"
       .byte "0-                                     0"
       .byte "000000000 00000000000 000000000000000000"
       .byte "0  0    0 0     0   0 0                0"
       .byte "0    0    0  0  0   0 0 0000000 00000000"
       .byte "0 000000000  0 00 0 0 0 0       0      0"
       .byte "0 0   0 0 0  0 0  0 0 0 0 0000000  000 0"
       .byte "0   0        0    0 0   0 0        0 0 0"
       .byte "0 0000000000000 000000000 0 00 000 0 0 0"
       .byte "0      0      0         0 0 0  0 0 0 0 0"
       .byte "0 0000 000 00000000 00000 0 00 0 0 0 0 0"
       .byte "0 0  0 0    0 0     0   0 0 0  0 0 0 0 0"
       .byte "0    0    0   00000 0 0 0 0 0  0   0 0 0"
       .byte "000000000000      0 0 0 0 0 0000 0 0 0 0"
       .byte "0            0000 0 0 0 0   0  0 0 0 0 0"
       .byte "0 0000 0000000  0 0 0 0 000 00 0 0 0 0 0"
       .byte "0 0  0 0     0 00 0   0 0   0    0 0   0"
       .byte "0    0    0  0    0 0 0 0000000 00000000"
       .byte "0 000000000  00000000 0 0       0      0"
       .byte "0 0  0    0         00000 000 0000 0 0 0"
       .byte "0 0     0    0  0   0   0   0 0    000 0"
       .byte "0000 0 00 0000 00 00000 0 0 0    0   0 0"
       .byte "0  0 0 0   0 0  0 0   0 0000000000000000"
       .byte "0    0 0   0    0   0                 +0"
       .byte "0000000000000000000000000000000000000000", 0

;
; zero page vectors
;
mazel   .equ $f7
mazeh   .equ mazel + 1
screenl .equ mazel + 2
screenh .equ mazel + 3
colorl  .equ mazel + 4
colorh  .equ mazel + 5
stackl  .equ mazel + 6
stackh  .equ mazel + 7
found   .equ mazel + 8

;
; commodore 64 stuff
;
screen   .equ   $0400
color    .equ   $d800

;
; reset found and transfer maze into screen
;
main  lda #$00
      sta found
      lda #<maze
      sta mazel
      lda #>maze
      sta mazeh
      lda #<screen
      sta screenl
      lda #>screen
      sta screenh
      lda #<color
      sta colorl
      lda #>color
      sta colorh
      lda #$00         ; start
      sta stackl       ; of
      lda #$c0         ; free
      sta stackh       ; RAM
      ldy #$00
loop  lda (mazel),y
      beq find
      sta (screenl),y
      lda #14
      sta (colorl),y
      iny
      bne loop
      inc mazeh
      inc screenh
      inc colorh
      jmp loop

;
; find - in the maze and start search from there
;
find  lda #<screen
      sta screenl
      lda #>screen
      sta screenh
      ldy #$00
scan  lda (screenl),y
      cmp #'-'
      beq start
      inc screenl
      bne scan
      inc screenh
      jmp scan
start lda #' '
      sta (screenl),y
      jsr dojsr
      rts

;
; the search method
;
search ldy #$00
       lda (screenl),y
       cmp #'+'
       bne nogoal
       lda #$01
       sta found
       jmp dorts    ; found
;
; still not at goal
;
nogoal cmp #' '
       beq empty
       jmp dorts    ; dead end
;
; empty path found, extend path
;
empty  lda #'*'
       sta (screenl),y
       lda screenl
       sta colorl
       lda screenh
       clc
       adc #$d4
       sta colorh
       lda #$01
       sta (colorl),y
;
; the following introduces an artificial delay to follow the recursion;
; remove it to get an appreciation of the speed of machine code!
;
       ldy #$08
       ldx #$00
delay  inx
       bne delay
       dey
       bne delay
;
; recursively search east
;
goeast inc screenl
       bne noinc1
       inc screenh
noinc1 jsr dojsr
       lda screenl
       bne nodec1
       dec screenh
nodec1 dec screenl
       lda found
       beq gosouth
       jmp dorts
;
; recursively search south
;       
gosouth clc
        lda screenl
        adc #40
        sta screenl
        lda screenh
        adc #0
        sta screenh
        jsr dojsr
        sec
        lda screenl
        sbc #40
        sta screenl
        lda screenh
        sbc #0
        sta screenh
        lda found
        beq gowest
        jmp dorts
;
; recursively search west
;
gowest lda screenl
       bne nodec2
       dec screenh
nodec2 dec screenl
       jsr dojsr
       inc screenl
       bne noinc2
       inc screenh
noinc2 lda found
       beq gonorth
       jmp dorts
;
; recursively search north
;       
gonorth sec
        lda screenl
        sbc #40
        sta screenl
        lda screenh
        sbc #0
        sta screenh
        jsr dojsr
        clc
        lda screenl
        adc #40
        sta screenl
        lda screenh
        adc #0
        sta screenh
        lda found
        beq deadend
        jmp dorts
;
; we could put a SPACE back and this position and explore the paths
; through here again later; although this will work, it is more efficient
; to mark this simply as a dead end
;
deadend ldy #$00
        lda #'.'
      ; lda #' '
        sta (screenl),y
        lda screenl
        sta colorl
        lda screenh
        clc
        adc #$d4
        sta colorh
        lda #14
        sta (colorl),y
        jmp dorts

;
; Since the 6510 only supports 256 bytes of stack,
; using regular jsr/rts to implement recursive
; backtracking places a restriction on the maximum
; "path length". This restriction is removed by
; using free RAM to implement the stack as follows:
;     replace jsr search -> jsr dojsr
;             rts        -> jmp dorts
;
dojsr   ldy #$00         ; record rta
        pla              ;
        sta (stackl),y   ;
        inc stackl       ;
        bne noincp1      ;
        inc stackh       ;
noincp1 pla              ;
        sta (stackl),y   ;
        inc stackl       ;
        bne noincp2      ;
        inc stackh       ;
noincp2 jmp search       ;
                         ;
dorts   ldy #0           ; restore rta
        lda stackl       ;
        bne nodecp1      ;
        dec stackh       ;
nodecp1 dec stackl       ;
        lda (stackl),y   ;
        pha              ;
        lda stackl       ;
        bne nodecp2      ;
        dec stackh       ;
nodecp2 dec stackl       ;
        lda (stackl),y   ;
        pha              ;
        rts              ;