Maze Generation

Introduction

During my summer holiday, in between long walks and nice food & drinks, I felt like writing some code for fun. Unfortunately, I didn’t bring my laptop. Luckily, Mike Fikes created a ClojureScript REPL for mobile devices to write some Clojure(script) without a laptop close at hand.

A REPL, or a Read Eval Print Loop, reads your input, evaluates it, prints the result and waits for new inputs to read. In the meantime, the code you wrote lives in REPL memory. So if I define a function in the REPL, it will be read and evaluated and in my next input I can call this function, because it lives in REPL space.

So, back to this REPL on my phone. Permanently saving work is not possible in this REPL, there are no debugging capabilities, no code completion, no test runners … just a REPL: 35 characters wide in portrait mode, 79 characters wide in landscape mode. To give you an idea of my ‘Integrated Development Environment’ and the resulting mazes, I recorded a 30 seconds screen cast:

At home, I created a gist containing all 70 lines of maze code (56 lines according to the command-line tool cloc). In this blog I’m going to explain the concepts and code.

Grids, Cells and Neighbours

First of all, we’ll need a grid and a coordinate system to point to individual cells in the grid. The reason is that most maze generators expect to be able to traverse a grid and lookup information about cells and neighbours of cells.

A grid can be modeled as a vector of vectors, representing rows and columns:

(def grid
  [[1 2 3]
   [4 5 6]
   [7 8 9]])

A cell can be pinpointed by its [row col] coordinate which matches perfectly with the get-in function in clojure. This get-in function is used to find items in nested data structures. For instance, (get-in grid [2 1]) will result in the value 8.

To find the neighbours of a cell, I created a couple of helper functions:

(defn north-of [[row col]] [(dec row) col])
(defn south-of [[row col]] [(inc row) col])
(defn west-of  [[row col]] [row (dec col)])
(defn east-of  [[row col]] [row (inc col)])

The function argument is destructured (taken apart and named) and the north-of, south-of, west-of or east-of neighbour coordinate is calculated by incrementing or decrementing the row or column number. For instance, (north-of [1 1]) results in the value [0 1].

Using the juxt function we can now calculate all neighbours in one go. juxt takes a variable number of functions as arguments and returns a new function. This new function returns a vector containing the result of applying each function to the arguments provided. So for instance ((juxt north-of south-of west-of east-of) [1 1]) results in the value [[0 1] [2 1] [1 0] [1 2]].

Unfortunately, these functions don’t care about the grid. ((juxt north-of south-of west-of east-of) [0 0]) will happily return [[-1 0] [1 0] [0 -1] [0 1]] containing cell coordinates inside AND outside the grid. Therefore, in order to calculate all neighbours in the grid, we need to filter out the ones that are not part of the grid. This results in the following neighbours function:

(defn neighbours [grid cell]
  (filter #(get-in grid %) ((juxt north-of south-of west-of east-of) cell)))

Mazes and Cells

Now working with the grid is easy, let’s move on to the maze. A maze is basically a grid, augmented with some information to determine if borders between cells are open or closed. That information can be easily stored in the cells themselves.

I liked the approach Mark Bastian took: in a cell, simply list the coordinates of neighbours the cell is connected to. We can even list the coordinates in a set #{}, since duplicating neighbour coordinates is useless. A 2x2 ‘maze’ with all borders closed looks like this:

[[#{} #{}]
 [#{} #{}]]

A 2x2 ‘maze’ with an open border between the 2 cells on the left looks like this:

[[#{[1 0]} #{}]
 [#{[0 0]} #{}]]

The two connected cells reference each other. It would be convenient to have a function that updates the grid when a border needs to be removed between 2 cells:

(defn remove-border [grid c1 c2]
  (-> grid
      (update-in c1 conj c2)
      (update-in c2 conj c1)))

Maze Generation

Now it’s time for the maze generation. Luckily I had a copy of the ‘Mazes for Programmers book’ on my phone. Because I like the texture of the mazes coming out of the recursive backtracker algorithm, I decided to implement that one.

The algorithm can start on any cell on the grid and I decided to start on [0 0] every single time. Every cell that is visited by the algorithm is pushed on a stack which I have called the backtrackstack. The cell on top of the stack is considered the current cell.

From the current cell, a path is created (remove-border) to a randomly selected, previously unvisited neighbour. An unvisited neighbour can easily be detected, since it’s simply an empty set #{}. That previously unvisited cell (next in my code) is also pushed unto the stack. This process repeats continuously until a cell is visited that has no unvisited neighbours. At that point, that dead-end cell is popped of the stack, making the previous cell the current cell. Again, the algorithm will check if this cell has unvisited neighbours and will either create a path to that unvisited neighbour or pop another cell from the backtrackstack. This will continue until every cell has been visited and the backtrackstack is empty.

(defn find-unvisited-neighbours [grid cell]
  (let [n (neighbours grid cell)]
    (filter #(empty? (get-in grid %)) n)))

(defn generate-maze [rows cols]
  (loop [maze           (create-grid rows cols)
         backtrackstack '([0 0])]
    (if (empty? backtrackstack)
      (print-maze maze)
      (let [unvn (find-unvisited-neighbours maze (first backtrackstack))]
        (if (empty? unvn)
          (recur maze (rest backtrackstack))
          (let [next (rand-nth unvn)]
            (recur
             (remove-border maze (first backtrackstack) next)
             (conj backtrackstack next))))))))

Fingers crossed:

 (generate-maze 4 4)

[[#{[1 0]} #{[0 2]} #{[0 3] [0 1]} #{[1 3] [0 2]}]
 [#{[0 0] [2 0]} #{[2 1] [1 2]} #{[1 1] [1 3]} #{[2 3] [0 3] [1 2]}]
 [#{[1 0] [3 0]} #{[2 2] [1 1]} #{[2 1] [3 2]} #{[3 3] [1 3]}]
 [#{[2 0] [3 1]} #{[3 0] [3 2]} #{[2 2] [3 1]} #{[2 3]}]]

 (generate-maze 4 4)

[[#{[0 1]} #{[0 0] [0 2]} #{[1 2] [0 1]} #{[1 3]}]
 [#{[1 1] [2 0]} #{[1 0] [1 2]} #{[1 1] [0 2]} #{[2 3] [0 3]}]
 [#{[1 0] [2 1]} #{[2 0] [3 1]} #{[2 3]} #{[2 2] [3 3] [1 3]}]
 [#{[3 1]} #{[3 0] [2 1] [3 2]} #{[3 3] [3 1]} #{[2 3] [3 2]}]]

 (generate-maze 6 4)

[[#{[1 0]} #{[0 2]} #{[0 3] [0 1]} #{[1 3] [0 2]}]
 [#{[0 0] [2 0]} #{[2 1] [1 2]} #{[1 1] [1 3]} #{[2 3] [0 3] [1 2]}]
 [#{[1 0] [3 0]} #{[1 1] [3 1]} #{[3 2]} #{[3 3] [1 3]}]
 [#{[2 0] [3 1]} #{[3 0] [2 1]} #{[2 2] [4 2]} #{[4 3] [2 3]}]
 [#{[4 1] [5 0]} #{[4 0]} #{[4 3] [5 2] [3 2]} #{[3 3] [4 2]}]
 [#{[5 1] [4 0]} #{[5 2] [5 0]} #{[4 2] [5 3] [5 1]} #{[5 2]}]]

Nice! Now the only thing left is printing a more human friendly view of this maze.

Maze Printing

First, the top of the maze is printed:

+---+---+---+

Then, for every row the left border is printed | and 2 passes over the cells have to be made. The first pass determines if there should be a border between the current cell and its east-of neighbour, resulting in something like this:

+---+---+---+---+
|           |   |

The second pass over the row adds a + and then determines if there should be a border between the current cell and its south-of neighbour, for instance resulting in this:

+---+---+---+---+
|           |   |
+---+---+   +   +

After repeating this for all rows, a maze like this is printed:

+---+---+---+---+
|           |   |
+---+---+   +   +
|       |       |
+   +   +---+   +
|   |       |   |
+   +---+   +   +
|       |       |
+---+---+---+---+

The code:

(defn east-open-border? [maze cell]
  (contains? (get-in maze (east-of cell)) cell))

(defn south-open-border? [maze cell]
  (contains? (get-in maze (south-of cell)) cell))

(defn print-cell-body [maze cell]
  (if (east-open-border? maze cell)
    "    "
    "   |"))

(defn print-cell-bottom [maze cell]
  (if (south-open-border? maze cell)
    "   +"
    "---+"))

(defn print-maze [maze]
  (let [result (atom [])
        rows   (range (count maze))
        cols   (range (count (get-in maze [0])))]
    (swap! result conj "+" (repeat (count cols) "---+") "\n")
    (doseq [row rows]
      (swap! result conj "|")
      (doseq [col cols]
        (swap! result conj (print-cell-body maze [row col])))
      (swap! result conj "\n" "+")
      (doseq [col cols]
        (swap! result conj (print-cell-bottom maze [row col])))
      (swap! result conj "\n"))
    (println (s/join (flatten @result)))))

Finally, we can print all the mazes we want:

(generate-maze 4 4)

+---+---+---+---+
|   |           |
+   +   +   +---+
|   |   |       |
+   +---+---+   +
|   |       |   |
+   +   +   +   +
|       |       |
+---+---+---+---+

(generate-maze 4 4)

+---+---+---+---+
|       |       |
+---+   +   +   +
|   |   |   |   |
+   +   +---+   +
|   |       |   |
+   +---+   +   +
|               |
+---+---+---+---+

(generate-maze 8 18)

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   |               |   |       |                   |       |           |
+   +   +   +---+   +   +   +   +   +---+   +---+   +   +   +---+---+   +
|   |   |   |   |   |   |   |       |   |   |           |           |   |
+   +---+   +   +   +   +   +---+---+   +   +---+---+---+---+---+   +   +
|       |   |       |   |   |           |           |   |           |   |
+---+   +   +   +---+   +   +   +---+---+   +---+   +   +   +---+---+   +
|   |       |   |       |   |   |       |   |       |       |           |
+   +---+---+   +   +   +   +   +   +   +---+   +---+   +---+   +   +   +
|           |   |   |   |       |   |           |   |   |   |   |   |   |
+   +---+---+   +   +   +   +---+   +---+---+---+   +   +   +   +   +   +
|   |           |   |       |       |   |           |   |       |   |   |
+   +   +---+---+---+---+   +   +---+   +   +---+   +   +---+   +   +   +
|   |   |               |   |       |   |       |   |       |   |   |   |
+   +   +---+   +---+   +---+---+   +   +---+   +   +---+   +---+   +   +
|               |                   |           |                   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Conclusion

So there you have it: a maze generator in ~ 30 lines of code with a 30 lines of code ascii view on top of it, build with nothing but a REPL on a phone. I really enjoyed the puzzle and the small (and large) successes while working in the REPL. I hope you enjoyed this recap.

I’d like to thanks Mike Fikes for his excellent ClojureScript REPL, Mark Bastian for the inspiration for the maze data structure, Jamis Buck for his lovely ‘Mazes for programmers’ book and Gert Goet for reviewing an earlier version of this blog. Faults and not-so-idiomatic Clojure code remaining are my own.

Back home, I’m happy to be working in Emacs with the excellent Clojure CIDER plugin again. Which reminds me that during my holiday I visited a picturesque CIDER factory in France. Cheers!

Please share your comments, suggestions and thoughts about this blog post on twitter.com/mmz_. Thanks for reading and Happy Coding!

Maze Generation

Generating Mazes from the REPL

Introduction

Grids, Cells and Neighbours

Mazes and Cells

Maze Generation

Maze Printing

Conclusion

Links