Maze generation: Difference between revisions

=={{header|Common Lisp}}==

Uses unicode line drawing chars. Assumes they are single width on console. Code pretty horribly unreadable.

<lang lisp>(defmacro !and= (a b) `(setf ,a (logand ,a (lognot ,b))))

(defmacro wipe (y x v) `(!and= (aref arr ,y ,x) ,v))

(defun make-maze (w h)

(setf *random-state* (make-random-state t))

(let ((arr (make-array (list (+ h h 2) (+ w w 2))

:initial-element 0)))

(loop for i below (+ h h 1) do

(loop for j below (+ w w 1) do

(setf (aref arr i j) 15)))

;; initial clean up

(loop for i to h do

;(wipe (+ i i) 0 4)

;(wipe (+ i i) (+ w w) 8)

(loop for j to w do

(setf (aref arr (+ i i 1) (+ j j 1)) 0)

;(wipe 0 (+ j j) 1)

;(wipe (+ h h) (+ j j) 2)

(wipe (+ i i) (+ j j 1) 3)

(wipe (+ i i 1) (+ j j) 12)))

(labels ((walk (y x)

(setf (aref arr y x) 16)

(loop (let (xx yy)

(loop with cnt = 0 with x1 with y1

;; find a random neighbor

for (dx dy) in '((-2 0) (0 2) (2 0) (0 -2))

do (let ((x1 (+ dx x)) (y1 (+ dy y)))

(when (and (<= 0 y1 (+ h h))

(<= 0 x1 (+ w w))

(zerop (logand (aref arr y1 x1) 16))

(zerop (random (incf cnt))))

(setf xx x1 yy y1))))

(if (not (and xx yy)) (return-from walk))

;; break walls along the walk

(if (= x xx)

(let ((yy (/ (+ y yy) 2)))

(wipe yy (1+ x) 4)

(wipe yy (1- x) 8)

(setf (aref arr yy x) 0)))

(if (= y yy)

(let ((xx (/ (+ x xx) 2)))

(wipe (1+ y) xx 1)

(wipe (1- y) xx 2)

(setf (aref arr y xx) 0)))

(walk yy xx)))))

(walk (1+ (* 2 (random h))) (1+ (* 2 (random w)))))

arr))

(defun show-maze (m)

(let ((g " │││─┘┐┤─└┌├─┴┬┼"))

(loop for i below (1- (array-dimension m 0)) do

(loop for j below (1- (array-dimension m 1)) do

(loop repeat (if (oddp j) 3 1) do

(format t "~c" (char g (!and= (aref m i j) 16)))))

(write-line ""))))

(show-maze (make-maze 8 8))</lang>output<lang>┼───┴───┼───┴───┴───┼───┴───┴───┼

│ │ │ │

┼──── │ │ │ │ ┌───┐ ├

│ │ │ │ │ │ │ │

┤ ┌───┘ │ │ │ │ │ ├

│ │ │ │ │ │ │

┤ │ ┌───┘ ├───────┤ │ ├

│ │ │ │ │ │

┤ │ │ ────┤ │ │ ────┼

│ │ │ │ │ │

┤ ────┼───┐ │ │ └───┐ ├

│ │ │ │ │ │

┼───┐ │ └───────┼───┐ └───┼

│ │ │ │ │

┤ └──────────── │ └───┐ ├

│ │ │

┼───┬───┬───┬───┬───┬───┬───┼───┼</lang>