(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は,2次元の場所をスロットとして持つ. ノードとノードの間の距離を: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