Maze in Lisp

TomToad · October 27, 2019, 10:36:06

Here is an example of a maze generated using Common Lisp

;;;seed the random number generator
(setf *random-state* (make-random-state t))
;;;constants to hold width and height of maze
(defconstant WIDTH 20)
(defconstant HEIGHT 10)

;;; the cell structure, north, south, east, west -> t = path, nil = wall
(defstruct cell
	(position '(0 0))
	(north nil)
	(south nil)
	(east nil)
	(west nil)
	(visited nil))
	
;;; the array of cells,	
(setf maze (make-array (list HEIGHT WIDTH)))

;;; this function takes a cell as input and returns a list of valid directions
;;; i.e. not across border, not visited
(defun get-valid-directions (cell)
	(let ((directions nil)
		 (position (cell-position cell)))
		(if (and (> (first position) 0) (not (cell-visited (aref maze (- (first position) 1) (second position)))))
			(push 0 directions))
		(if (and (< (second position) (- WIDTH 1)) (not (cell-visited (aref maze (first position) (+ (second position) 1)))))
			(push 1 directions))
		(if (and (< (first position) (- HEIGHT 1)) (not (cell-visited (aref maze (+ (first position) 1) (second position)))))
			(push 2 directions))
		(if (and (> (second position) 0) (not (cell-visited (aref maze (first position) (- (second position) 1)))))
			(push 3 directions))
		directions))

;;; fill the array with cells
(dotimes (column WIDTH)
	(dotimes (row HEIGHT)
		(setf new-cell (make-cell))
		(setf (cell-position new-cell) (list row column))
		(setf (aref maze row column) new-cell)))

;;; our stack for the recursive-backtracker algorythm.
(setf stack nil)

;;; pick a cell at random and place it on the stack
(setf current-cell (aref maze (random HEIGHT) (random WIDTH)))
(setf (cell-visited current-cell) t)
(push current-cell stack)
;;; repeat until the stack is empty
(do ((current-cell (first stack) (first stack)))
	((null stack))
	(let  ((directions (get-valid-directions current-cell))
			(position (cell-position current-cell))
			(direction 0)
			(chosen-cell nil))
	(cond ((= (length directions) 0)
			(pop stack))
		(t (setf direction (nth (random (length directions)) directions))
			(cond ((= direction 0)
					(setf chosen-cell (aref maze (- (first position) 1) (second position)))
					(setf (cell-north current-cell) t)
					(setf (cell-south chosen-cell) t)
					(setf (cell-visited chosen-cell) t))
				((= direction 1)
					(setf chosen-cell (aref maze (first position) (+ (second position) 1)))
					(setf (cell-east current-cell) t)
					(setf (cell-west chosen-cell) t)
					(setf (cell-visited chosen-cell) t))
				((= direction 2)
					(setf chosen-cell (aref maze (+ (first position) 1) (second position)))
					(setf (cell-south current-cell) t)
					(setf (cell-north chosen-cell) t)
					(setf (cell-visited chosen-cell) t))
				((= direction 3)
					(setf chosen-cell (aref maze (first position) (- (second position) 1)))
					(setf (cell-west current-cell) t)
					(setf (cell-east chosen-cell) t)
					(setf (cell-visited chosen-cell) t)))
			(push chosen-cell stack)))))
			
;;;print the maze :):):):)
(format t "~&+")
(dotimes (column WIDTH)
	(format t "--+"))
(dotimes (row HEIGHT)
	(format t "~&|")
	(dotimes (column WIDTH)
		(if (equal (cell-east (aref maze row column)) t)
			(format t "   ")
			(format t "  |")))
	(format t "~&+")
	(dotimes (column WIDTH)
		(if (equal (cell-south (aref maze row column)) t)
			(format t "  +")
			(format t "--+"))))

SyntaxBomb - Indie Coders

Maze in Lisp

TomToad