読者です 読者をやめる 読者になる 読者になる

Let's write β

趣味で書いたこととか、RustとLispが好き

迷路生成をLispで

迷路を生成したいとおもい、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)))

このように部屋の間の接続がなされている事がわかります。
次はこの迷路をどのように視覚化するかですね。あとは、すこし壁がすくない気がするので、アルゴリズムを変項するとかしても良いかもしれませんね。

僕が働いているAzit.incでは一緒に働けるエンジニアを募集しています!
採用情報 — 株式会社アジット|Azit Inc.