A-maze-ing Mazes with Clojure

Mazes can be pretty fun. Children love them. Add a dungeon theme (e.g. monsters, loot, and a dragon boss) and most computer programming adults like them, too.

In this post, I'll show you how to make some mazes in Clojure/ClojureScript. Feel free to print some off for your next trip with your kids or adapt this code to your next campaign if you are a DM.

The techniques I'll be covering are Prim's algorithm and Depth-First Search with Backtracking. Afterwords, I'll show you the code and discuss some interesting points.

Here are the algorithms:

Prim's Algorithm
This algorithm will produce mazes with a fair amount of branching and not a lot of long corridors. Here are the steps in the algorithm:

1. Mark all cells in your maze as undiscovered.
2. Select a start cell and mark it as visited.
3. Mark all neighbors of the start cell as frontier cells.
4. Randomly select a cell from the frontier as your next cell.
5. Add it to the maze.
6. Add any neighbors of the selected cell that are undiscovered to the frontier.
7. Connect the selected cell to the maze by randomly selecting an adjacent cell that is already in the maze and mark the two cells as connected.
8. If the frontier is not empty, goto 4. Otherwise, your maze is complete.
9. You can optionally mark a cell as the end, but this is just a convenience for knowing when you can leave the dungeon. The maze is fully connected so the endpoint is arbitrary.

Depth-First Search with Backtracking

DFS will produce longer corridors since it continues to move forward until it is blocked. Here are the steps in the algorithm:

1. Select a cell, mark it as in the maze, and put it on the path stack.
2. Randomly select an unvisited neighbor of the current cell, connect it to the previous cell, and put the new cell on the path stack. Since we are always stepping forward to a different cell we are going to make longer paths. This is the "Depth-First" part of the algorithm.
3. If the current cell has unvisited neighbors, goto 2. Otherwise, pop the top off the path stack, make the new top of the stack the current cell, and goto 2 (This is the "backtracking" part of the algorithm). Repeat until every cell has been visited.
4. As with Prim's algorithm, you can choose an exit if desired, but this is arbitrary.

You can read more about these here and here.

Without further ado, here are mazes generated using these algorithms. There is a reset button below the second maze to recreate them if you want.

Maze generated using Prim's algorithm

Maze generated using Depth-First Search with Backtracking

The Source
Here is the complete implementation of the maze generators. Less than 50 lines! Despite being such a small namespace, it does a lot. Continue on past the code to see my comments and observations regarding this exercise.

Note that I did not include the source for rendering the mazes onto the HTML canvas. You can see that as well as a standalone Java Swing version of the code by checking out the complete project here.

(ns mazegen.rules)

(defn create-empty
  "Create an empty rectangular maze."
  [rows cols]
  (vec (take rows (repeat (vec (take cols (repeat #{})))))))

(defn neighbors
  "Compute the neighbors of a given coordinate."
  [maze [i j]]
  (->> (map vector
            ((juxt inc identity dec identity) i)
            ((juxt identity inc identity dec) j))
       (filter #(get-in maze %))))

(defn open-wall
  "Create pathways between the src and dst coords of the maze."
  [maze src dst]
  (-> maze
      (update-in src conj dst)
      (update-in dst conj src)))

(defn prim-gen
  "Create a maze using Prim's method."
  [empty-maze start end]
  (loop [maze (update-in empty-maze start conj :start)
         frontier (into #{} (neighbors maze start))]
    (if (empty? frontier)
      (update-in maze end conj :end)
      (let [dst (rand-nth (vec frontier))
            n (neighbors maze dst)
            { f true s false } (group-by #(empty? (get-in maze %)) n)]
        (recur (open-wall maze (rand-nth s) dst)
               (into (disj frontier dst) f))))))

(defn depth-first-gen
  "Create a maze using a depth-first recursive search with backtracking."
  [empty-maze start end]
  (loop [maze (update-in empty-maze start conj :start)
         visited [start]]
    (if (empty? visited)
      (update-in maze end conj :end)
      (let [n (neighbors maze (first visited))
            f (filter #(empty? (get-in maze %)) n)]
        (if (empty? f)
          (recur maze (rest visited))
          (let [dst (rand-nth (vec f))]
            (recur (open-wall maze (first visited) dst)
                   (conj visited dst))))))))

Comments, Observations, Lessons Learned
Here are some points that you might find interesting from this exercise:

• The Data Model: In Java you would likely have a Maze class with Cells or some similar type hierarchy. In Clojure, you generally think about the data and model your domain in terms of simple data structures (vectors, maps, and sets). As the program grows, the data can flexibly grow with it. I modeled the maze as a 2D vector of sets. Each set represents a cell that contains links to other cells as well as any other data that I want to throw into it. In this case, I add :start and :end keywords to cells to represent entry and exit points. Had I used an object hierarchy, I would have to have made some decisions a priori regarding what can and can't go into a Cell. Would a cell have a start, be a start, or something else? Suppose I wanted to add a dragon at the exit that I had to fight to complete the maze. In Object Land, I now have to go back and redesign my type hierarchy to accommodate such a thing. In Clojure, I simply add a :dragon to the current cell set. If I decide I want something more hierarchical, I could easily change my sets in each cell to a map, or even add a map entry to the set (Maybe the dragon isn't just a keyword - Perhaps I also need to store its hit points or other attriubutes). Alternatively, I could have represented the maze as a map of [x y] coordinates as keys and another nested data structure as values.
• The neighbors function has some awesomeness that needs some explaining. First, see that I am using the juxt function (as explained here and here) to determine my neighbor's coordinates. However, I may get coordinates like [-1 0] that are off the maze (the maze has minimum coords of [0 0] and maximum of [(dec dim) (dec dim)]). Rather than checking if the coordinate is in the grid or not, I attempt to access it using the get-in function. The great thing about get-in is that it allows you to safely drill down into nested data structures. If the element is missing or the path you are navigating is bad, it returns nil (You can also provide an optional default value). Contrast this to Java or Scala, where you must be very careful about navigating into nested data structures (e.g. maps of maps). One wrong get and you will get a NullPointerException. The filter method is called on the results of calling get-in over all of the coordinates in the maze. Filter will drop all of the nils that are returned, so anything off the maze goes away.
• The neighbors and open-wall methods make use of threading macros (-> is thread first) and (->> is thread last). These deserve a post of their own, but the short explanation is that they take a value and feed it through a succession of functions. As each function is called, the result is passed to the next function. This allows you to create processing pipelines. The first vs. last distinction has to do with where the thing being threaded goes in the next function (first or last position). As I said, this is worthy of its own post and I won't go into a ton of detail here.
• Finally, we don't goto in Clojure. Any self-respecting language would use recursion instead. Clojure has a pattern for recursion called loop-recur. Loop is the first line of the pattern and initializes a set of items to be iterated upon. This is typically followed by an if or other branching statement that has a stop condition and a recursion condition. If the stop condition is met, you return. If the recur condition is met, you update the items being iterated upon. In my examples, I used recur to track the maze, the active cell, the frontier, and similar items. One important point about loop-recur is that recur must be in the tail position of the calculation (the last thing being calculated before looping). By doing so, the construct is transformed under the covers so that the stack does not grow and you are just doing a simple loop.

There is more that can be gleaned from this short application, but I think this is good for now. It is easy to see, however, that Clojure is a very powerful and expressive language.

Conclusion

Mazes are an interesting problem that can demonstrate a lot of features of functional programming. In this case, the functional language of choice was Clojure. Clojure's powerful data modeling aspects combined with its expressiveness made it easy to create a flexible and concise solution to this problem.

If you liked this page or learned anything from it, please tweet the link and/or follow me on Twitter. Your support and interest is the fuel that drives the effort.
Tweet Follow @mark_bastian Tweet #clojure