迷路を生成したいとおもい、Lispで簡単なクラスタリング法で生成してみました。
;;迷路のデータ構造 (defclass <maze> () ((width :initarg :w :accessor w) (height :initarg :h :accessor h) (rooms :initarg :rooms :accessor rooms))) ;;部屋の情報を管理するリストをつくる (defun make-room-list (w h) (let ((array (make-array (* w h) :initial-element 0))) (loop for idx from 0 upto (1- (* w h)) do (setf (aref array idx) (list idx idx nil))) array)) ;;単純なグリッドの部屋をつくる (defun make-base-maze (w h) (make-instance '<maze> :w w :h h :rooms (make-room-list w h))) ;;対応する番号の部屋を返す (defmethod get-room ((maze <maze>) idx) (aref (rooms maze) idx)) ;;部屋のクラスタ番号を返す (defmethod get-cluster-id ((maze <maze>) idx) (cadr (get-room maze idx))) ;;部屋のクラスタ番号を設定する (defmethod set-cluster-id ((maze <maze>) idx new-id) (setf (cadr (aref (rooms maze) idx)) new-id)) ;;全ての部屋がクラスタ0に属していたら終了 #| | 初期状態ではクラスタ番号 i は i >= 0 を満している | 部屋と部屋を接続する時には、かならず小さい方のクラスタ番号に属させるようにしている、よって | 0 n = 0 | n m = if n > m then m else n | とクラスタ番号が決められていくので、部屋を繋げていくたびに、クラスタ番号は単調減少していく。 | よって最終状態では、クラスタ番号は確実に全て0になっている。 |# (defmethod build-finished-p ((maze <maze>)) (every (lambda (room) (zerop (cadr room))) (rooms maze))) ;;x座標とy座標を計算 (defmethod calc-x-y ((maze <maze>) idx) (values (mod idx (w maze))) (truncate idx (w maze))) ;;隣接した部屋かどうか (defmethod neighbor-room-p ((maze <maze>) from to) (multiple-value-bind (from-x from-y) (calc-x-y maze from) (multiple-value-bind (to-x to-y) (calc-x-y maze to) (= (+ (abs (- from-x to-x)) (abs (- from-y to-y))) 1)))) ;;隣接した部屋ならば、繋げる (defmethod connect-room ((maze <maze>) i j) (let ((id-i (get-cluster-id maze i)) (id-j (get-cluster-id maze j))) (when (and (not (equal id-i id-j)) (neighbor-room-p maze i j)) ;それぞれの部屋の隣接リストに相手の部屋を追加する (push j (caddr (aref (rooms maze) i))) (push i (caddr (aref (rooms maze) j))) ;小さい方のクラスタ番号を採用 (set-cluster-id maze i (min id-i id-j)) (set-cluster-id maze j (min id-i id-j))))) ;;初期迷路を生成し、全ての部屋が同じクラスタに属するまで ;;部屋をつなげていく (defun build-maze (w h) (let ((maze (make-base-maze w h))) (loop until (build-finished-p maze) do (connect-room maze (random (* w h)) (random (* w h)))) maze))
実行すると
CL-USER(46): (rooms (build-maze 5 5 )) #((0 0 (1 5)) (1 0 (0 2 6)) (2 0 (7 3 1)) (3 0 (2 4 8)) (4 0 (9 3)) (5 0 (0 6 10)) (6 0 (7 5 11 1)) (7 0 (8 2 6 12)) (8 0 (7 3)) (9 0 (4 14)) (10 0 (15 11 5)) (11 0 (6 10 16 12)) (12 0 (13 17 7 11)) (13 0 (14 12 18)) (14 0 (13 19 9)) (15 0 (20 10 16)) (16 0 (21 17 15 11)) (17 0 (18 22 12 16)) (18 0 (17 23 19 13)) (19 0 (14 18 24)) (20 0 (15 21)) (21 0 (16 20 22)) (22 0 (17 23 21)) (23 0 (18 22 24)) (24 0 (19 23)))
このように部屋の間の接続がなされている事がわかります。
次はこの迷路をどのように視覚化するかですね。あとは、すこし壁がすくない気がするので、アルゴリズムを変項するとかしても良いかもしれませんね。
