迷路解答もLispで

cl-mazeという名前でgithubに置くことにした、前の迷路を構築するプロジェクトをいくつかアップデートしました。

• 部屋をroomというstructで管理する事にした
• Dijkstra法をもちいて解答を計算するようにした

以下は、そのメソッドと表示される結果

(defmethod solve ((maze <maze>))
  ;;Calcurate each cell minimum distance from start
  (let ((U (queues:make-queue :priority-queue
                              :compare (lambda (r1 r2) (< (cdr r1) (cdr r2)))))
        (V (make-hash-table))) 
    ;;Add First node
    (queues:qpush U (cons (aref (rooms maze) 0) 0))
    ;;Add Rest nodes
    (loop for idx from 1 below (* (w maze) (h maze))
          do
          (queues:qpush U (cons (aref (rooms maze) idx) most-positive-fixnum)))
    (loop while (not (zerop (queues:qsize U)))
          do
          (let ((p (queues:qtop U)))
            ;;Remove p from U add to V
            (queues:qpop U)
            ;; roomIdx -> distance
            (setf (gethash (room-idx (car p)) V) (cdr p))
            (loop for adj in (room-adjacency (car p))
                  when #1=(queues:queue-find U (lambda (n) (equalp (car n) (aref (rooms maze) adj))))
                  do
                  (setf (gethash (room-idx (car #2=(queues::node-value #1#))) V)
                        #3=(min (cdr #2#) (1+ (cdr p))))
                  (queues:queue-change U #1# (cons (car #2#) #3#)) )))
    ;;Create route from distance table
    (let ((current-idx (1- (* (w maze) (h maze)))))
      (loop
        collect current-idx into route
        do
        (setf current-idx
              (find-if (lambda (idx) (= (gethash idx V)
                                        (1- (gethash current-idx V))))
                       (room-adjacency (aref (rooms maze) current-idx))))
        until (zerop current-idx)
        finally (return (cons 0 (nreverse route)))))))

まずダイクストラ法で重さを求めてから、それを利用して最短ルートを計算しています。
それを利用して表示するようにしたのが以下のスクリーンショット