Next: 8 積み木の問題 Up: ソフトウェア特論講義資料ロボットのソフトウェア Previous: 6.3 縦型，横型探索

7 迷路の問題

迷路の問題は，ノードクラスのサブクラスに迷路用ノードのクラスmaze-nodeを作ってみます．


(defclass maze-node
  :super node
  :slots
  (pos))

(defmethod maze-node
  (:init (&rest args &key ((:pos p)) &allow-other-keys)
         (send-super-lexpr :init args)
         (setq pos p)
         self)
  )

(defmethod maze-node
  (:pos (&optional p)
        (if p (setq pos p))
        pos)
  (:distance (n)
             (distance pos (send n :pos)))
  (:prin1 (strm)
          (send-super :prin1 strm 
                      (format nil ":pos ~A" pos))
          )
  )

maze-nodeは，２次元の場所をスロットとして持ちます．ノードとノードの間の距離を:distanceで計算することができます．


(defun init-maze-nodes (x-max y-max)
  (let ((res nil) (i 0))
    (do
     ((y 1 (1+ y)))
     ((> y y-max))
     (do
      ((x 1 (1+ x)))
      ((> x x-max))
      (setq res
            (cons
             (instance maze-node :init
                       :name (string (incf i))
                       :pos (float-vector x y))
             res))))
    (reverse res)
    )
  )



(defmethod node
  (:add-neighbor
   (n &key (test #'equal))
   (when (not (member n neighbors :test test))
         (send self :neighbors (cons n neighbors))
         (send n :add-neighbor self :test test)
         )
   neighbors)
  )

隣接関係にあるノード間には，互いにneighborsスロットに相手ノードをリストにして蓄えてゆくためのメソッドが :add-neighborです．



(defun init-maze ()
  (setq *maze-graph*
　　　 (instance graph
　　　　　　 :init (init-maze-nodes 5 5)))
  (dolist (path '((1 2) (2 3) (3 4) (4 9) (9 14) (9 8)
                  (8 7) (7 12) (12 13) (12 11) (11 6)
                  (11 16) (14 15) (16 17) (17 22)
                  (21 22) (22 23) (23 18) (23 24)
                  (24 19) (19 20) (20 15) (15 10)
                  (10 5) (20 25)))
    (let ((n1 (car path))
          (n2 (cadr path)))
      (send (send *maze-graph* :find-node (string n1))
　　　　　　:add-neighbor
            (send *maze-graph* :find-node (string n2)))))
  *maze-graph*)

たとえば，次のようにmaze-testを定義して実行すると以下のようになります．


(defun maze-test nil
  (init-maze)
  (setq dp (send *maze-graph* :find-route
         "21" "13" :depth-first))
  (setq bp (send *maze-graph* :find-route
         "21" "13" :breadth-first))
  nil)


eus$ (maze-test)
route length from 21 to 13 is 13 in :depth-first method.
  route path is (21 22 23 24 19 20 15 14 9 8 7 12 13).
route length from 21 to 13 is 7 in :breadth-first method.
  route path is (21 22 17 16 11 12 13).
nil

generated through LaTeX2HTML. M.Inaba 平成18年5月6日