grid-DFS.ss

(define path-lst '())

(define expand
  (lambda (point)
    (let* ((lst0 (adjacentv point))
           (lst (randomize lst0)))
      (set-lst-frontier lst)
      (add-to-path-lst lst point)
      (push lst))))

(define randomize
  (lambda (lst)
    (let ((size (length lst)))
      (cond
        ((< size 2) lst)
        (else
          (let* ((node-num (random size))
                 (nodex (list-ref lst node-num))
                 (new-lst (removex node-num lst)))
            (cons nodex (randomize new-lst))))))))

(define removex
  (lambda (num lst)
    (if (= num 0)
        (cdr lst)
        (cons (car lst) (removex (- num 1) (cdr lst))))))

(define add-to-path-lst
  (lambda (lst point)
    (if (not (null? lst))
        (let ((child-parent (list (car lst) point)))
          (set! path-lst (cons child-parent path-lst))
          (add-to-path-lst (cdr lst) point)))))

(define set-lst-frontier
  (lambda (lst)
    (if (null? lst)
        '()
        (let ((x (car lst)))
          (draw-pt-frontier x)
          (block-set! x frontier)
          (set-lst-frontier (cdr lst))))))

(define draw-pt-frontier
  (lambda (pt)
    (draw-frontier (car pt) (cadr pt))))

(define search
  (lambda (grid stop-count)
    (block-set! start frontier)
    (set! path-lst (list (list start '())))
    (search2 grid 1 stop-count)))

(define search2
  (lambda (grid count stop-count)
    ;(display stack) (newline)
    (pause pause-num)
    (display count)
    (newline)
    (expand robot)
    (let ((next-robot (top)))
      (cond
        ((null? next-robot)
         (display "Cannot reach the goal")
         (newline))
        ((equal? next-robot goal)
         (set! robot (pop))
         (draw-moved-robot (robot-x) (robot-y))
         (display "Found")
         (newline)
         (let ((path (get-path goal)))
           (draw-path path)
           (display path))
         (newline))
        ((>= count stop-count)
         (display "Took too long")
         (newline))
        (else
          (draw-visited (car robot) (cadr robot))
          (set! robot (pop))
          (draw-moved-robot (robot-x) (robot-y))
          (search2 grid (+ count 1) stop-count))))))

(define get-path
  (lambda (last-node)
    (if (equal? last-node start)
        (list start)
        (let ((next-node (cadr (assoc last-node path-lst))))
          (append (get-path next-node) (list last-node))))))

(define draw-path
  (lambda (path)
    (cond
      ((not (null? path))
       (draw-pt-path-node (car path))
       (draw-path (cdr path))))))