## Saturday, April 11, 2015

### 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.

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))))))))