Maze generator in ClojureScript

Tags: clojurescript, maze generation

Here’s a simple maze generation program in ClojureScript. I’m developing this using a relatively standard stack for ClojureScript development:

Maze generator

The generator is basically a depth-first graph traversal, which generates a random spanning tree out of a maze that’s looked at as a graph. I’ll dissect the code in smaller chunks.

(ns com.icyrock.clojurescript.prb.maze-gen
  (:require-macros [dommy.macros :refer [sel1]])
  (:require [clojure.string :refer [join]]
            [dommy.core :as dommy]))

Standard ns declaration with a couple of requires.

(def board-dim {:h 24 :w 48})
(def doors (atom #{}))
(def visited-rooms (atom #{}))

Define:

  • The board dimensions (:h and :w stand for height and width, respectively)
  • Set of doors
  • Set of visited rooms
(defn is-door [pt1 pt2]
  (let [curr-doors @doors]
    (or (contains? curr-doors [pt1 pt2])
        (contains? curr-doors [pt2 pt1]))))

(defn set-door [pt1 pt2]
  (swap! doors conj [pt1 pt2]))

(defn visit-room [room]
  (swap! visited-rooms conj room))

A few helper functions:

  • The first determines whether there’s a door between two points / rooms in the maze
  • The second actually sets the doors there (i.e. connects the two rooms)
  • The third marks the room visited, so we don’t visit it twice when traversing
(defn pending-rooms [[row col]]
  (remove nil?
          (for [[rd cd] [[-1 0] [0 1] [1 0] [0 -1]]]
            (let [trow (+ row rd)
                  tcol (+ col cd)
                  room [trow tcol]]
              (when (and (<= 0 trow)
                         (<= 0 tcol)
                         (< trow (:h board-dim))
                         (< tcol (:w board-dim))
                         (not (@visited-rooms room)))
                room)))))

This one is used to determine which way we can go. Given any room (defined as [row col] point of a maze), it will try the four possible directions clockwise ([-1 0] [0 1] [1 0] [0 -1]) – i.e.:

  • Previous row (direction up)
  • Next column (direction right)
  • Next row (direction bottom)
  • Previous column (direction left)

For each of these rooms, it will make sure each of them is not:

  • Out of the bounds of the maze (the first four checks in the and call)
  • Already visited

It will collect all the rooms using for, then remove all that are nil (meaning they do not satisfy the above conditions).

(def maze-stack (atom []))

(defn push-maze-stack [pt]
  (swap! maze-stack conj pt))

(defn pop-maze-stack []
  (let [val @maze-stack]
    (reset! maze-stack (rest val))
    (first val)))

This piece defines:

  • The maze stack atom (i.e. the stack of rooms visited used for depth-first search)
  • Function to push a room to the stack
  • Function to pop the room off the stack
(defn start-building-maze [start-room]
  (reset! doors #{})
  (reset! maze-stack [start-room])
  (reset! visited-rooms #{start-room}))

This one resets all the state to start a new maze building cycle.

(defn maze-building-step []
  (loop []
    (when-let [room (first @maze-stack)]
      (let [pending (pending-rooms room)]
        (if (empty? pending)
          (do
            (pop-maze-stack)
            (recur))
          (let [shuffled (shuffle pending)
                next-room (first shuffled)]
            (push-maze-stack next-room)
            (visit-room next-room)
            (set-door room next-room)))))))

Guts of the maze building:

  • Get the top room from the stack, if there are any
  • Get the pending rooms (all that can be visited given the constraints, as provided above) from that room
  • If no pending rooms, discard this room and recur into the loop
  • Otherwise, shuffle the pending rooms (to randomize the maze), pick the next room, push it to the stack, mark it visited and make a door between the current room and that one
(def content (sel1 :#content))

(defn make-gui []
  (dommy/replace-contents! content [:pre {:id "maze"}]))

(def doors-to-char 
  (into cljs.core.PersistentHashMap/EMPTY
        {[false false false false]  "⬞"
         [true  false false false]  "╵"
         [false true  false false]  "╶"
         [true  true  false false]  "└"
         [false false true  false]  "╷"
         [true  false true  false]  "│"
         [false true  true  false]  "┌"
         [true  true  true  false]  "├"
         [false false false true ]  "╴"
         [true  false false true ]  "┘"
         [false true  false true ] "─"
         [true  true  false true ] "┴"
         [false false true  true ] "┐"
         [true  false true  true ] "┤"
         [false true  true  true ] "┬"
         [true  true  true  true ] "┼"}))

(defn board-str []
  (join "\n"
        (for [row (range (:h board-dim))]
          (join
           (for [col (range (:w board-dim))]
             (let [top-door (is-door [row col] [(dec row) col])
                   right-door (is-door [row col] [row (inc col)])
                   bottom-door (is-door [row col] [(inc row) col])
                   left-door (is-door [row col] [row (dec col)])]
               (doors-to-char [top-door right-door bottom-door left-door])))))))

(defn print-board []
  (dommy/replace! (sel1 :#maze) [:pre {:id "maze"} (board-str)]))

GUI-related code:

  • content is the parent div that will contain the maze
  • make-gui will create a pre HTML element with ID maze and put it inside the above content div

I’m actually using this pre element to output the Unicode string representation of the maze. Thus the doors-to-char map used for character lookup. It’s build like this to speed it up – see this StackOverflow question and David’s answer for explanation.

The lookup map is simple – the key is a vector of [top-door right-door bottom-door left-door], where each of the items are true / false monikers signifying whether the door is present or not, and the value is an Unicode character representing the correct room “image” given the possible exits out of that room.

  • board-str is actually making the string representation by traversing all rows, then all cells within each of the rows and getting the correct character to represent the door
  • print-board is just a helper function to output this to the pre element we created in make-gui
(defn run-maze-gen []
  (let [runs 50]
    (if (not-any? nil? (repeatedly runs maze-building-step))
      (do
        (print-board)
        (js/setTimeout run-maze-gen 50))
      (do (print-board)
          (dommy/append! content [:pre "Finished"])))))

(defn main []
  (make-gui)
  (start-building-maze [(quot (:h board-dim) 2)
                        (quot (:w board-dim) 2)])
  (run-maze-gen))

Top-level functions:

  • run-maze-gen runs the maze building step in batches of 50 (let [runs 50]), prints the board after each, then sets a timer to 50ms to run these again until the whole maze is generated
  • main makes the GUI, resets the maze and sets the starting room to the middle of the maze (parameters to start-building-maze), then calls run-maze-gen to actually start building the maze.

The result is something like this:

sample-maze

Note that maze corridors here are actually the lines, not the empty space between them, which I guess is more often how a maze is represented.