# Paul Blasucci's Weblog

## To the A-maze-ment of All: Generating Mazes in F#

Published:

Little more than a week ago, I had the great pleasure of attending the inaugural Lambda Jam conference in Chicago, Illinois. It was a terrific experience, and highly recommended for anyone interested in functional programming. One of the more interesting aspects of the conference was the daily "Jam Sessions". Part hack-a-thon, part coding contest, each jam saw groups of participants trying to solve some interesting challenges in a variety of functionally-oriented languages. And, it just so happens, I was a "Jam Mentor", supervising and facilitating a jam centered around mazes. So, now that it's all said and done, I'd like to present my take on the problem of maze generation (in F#, of course).

The problem statement (as given to jam participants):

The goal is to produce a two-dimensional rectangular maze of arbitrary size. The actual dimensions of the maze should be accepted parametrically (ex: inputs to a function, command-line arguments, et cetera). The maze itself should be output... as an array of arrays of integers, where each inner array represents one row of the maze and the number in each cell is a bitmask indicating the number of passages leading out of the cell (Note: the bitmask pattern is: North = 1, South = 2, East = 4, West = 8).
So, it seems the very first thing we'll need (since I tend to be a "visual" thinker) is a way to turn the maze description into something graphical. Since the format is an array of arrays, it's very convenient to treat the maze as a series of cells. The greatly reduced issue, then, is: how to draw a single cell? Well, given a value for the width and height (assuming square cells, `cellSize` in the actual function), we only need an origin point (`x` and `y`) and the actual value of the cell (`cell`). These numbers, together with a little GDI+, gives us this:
``````let drawCell (x,y) cell =
let x1,y1 = cellSize * x,cellSize * y
let x2,y2 = x1 + cellSize,y1 + cellSize

if cell |> hasWall N then graphics.DrawLine(Pens.Black,x1,y1,x2,y1)
if cell |> hasWall S then graphics.DrawLine(Pens.Black,x1,y2,x2,y2)
if cell |> hasWall E then graphics.DrawLine(Pens.Black,x2,y1,x2,y2)
if cell |> hasWall W then graphics.DrawLine(Pens.Black,x1,y1,x1,y2)
``````

We first calculate the top-left and bottom-right corners of the cell (`x1`,`y1` and `x2`,`y2`, respectively). Then, if the cell has a wall on a particular side, we use the calculated points to draw a line representing said wall. This will let us take data like:

``````let maze = [|
[| 2, 14, 10, 14,  8 |],
[| 5,  9, 11, 13, 11 |],
[| 3, 15,  9, 15,  9 |],
[| 7, 15, 13, 15, 11 |],
[| 1, 13,  9,  9,  9 |]
|]
``````

and turn it into: Great! So now that we can visualize, it's time for some random maze generation.

At Lambda Jam, participants were given two algorithms to try (both being well-documented on the web). One, called Growing Tree, is stack-based and "carves" passages through the maze. Again, quoting from the materials given to jam participants:

Growing Tree
This passage-carving algorithm maintains a list of “carved” cells as it traverses the maze. The general approach is:
1. choose a cell from this list 2. select one of its uncarved neighbors 3. carve that neighbor 4. add the newly carved cell to the list 5. repeat from step 1
If a cell has no uncarved neighbors (at step 2), it is removed from the list and another cell is chosen (return to step 1). The maze is finished when there are no cells left in the list. To start the process, simply pick a cell at random from the (initial) block of uncarved cells (i.e. the maze). This algorithm can simulate several other algorithms and/or produce very interesting results by varying how the next cell is chosen from the list (in step 1). Some strategies include: most-recently added, oldest, or random. One can even blend strategies.
The other algorithm, meanwhile, "builds" walls by a process of (potentially infinite) sub-division. Hence, its name: Recursive Division. More formally:
Recursive Division
This wall-building algorithm starts with the maze as an empty, but bounded, area. It then proceeds as follows:
1. Pick a location at random to build a wall running either the height (vertically) or width (horizontally) of the bounded area (maze) 2. Place an opening randomly within the new wall 3. Recursively repeat from step 1 on each of the two subdivisions created by building the wall (e.g. step 1, but now the bounded area is a subset of the overall maze) 4. Halt the process when an (arbitrary) number of subdivisions has been reached
The orientation of the wall should be biased towards the proportions of a given (subdivision) area. In other words, an area where the height is twice the width should be divided horizontally more often than vertically (and vice-versa for inverse ratios). Please note, this algorithm “builds walls”, but the output format should describe passages. Therefore, an extra conversion step may be warranted.
At Lambda Jam, the first algorithm was chosen unanimously. So, while I'll include my version of it in the full source for this post, I'd instead like to focus on the neglected Recursive Division approach to maze generation. Rather than take a "purely functional" approach, I chose to exploit F#'s multiparadigmatic nature. So, first step is to initialize an empty rectangular array.
``````let grid = Array.init height (fun _ -> Array.zeroCreate width)
``````

The meat of the code though is a function which, given a starting point (`x` and `y`), a set of bounds (`width` and `height`), and an orientation (horizontally or vertically, via `orientation`),

``````let rec divide (grid:int[][]) x y width height orientation =
``````

will "build" a wall by setting values in a slice of the aforementioned rectangular array (from `x`,`y` to `wx`,`wy`). Note, however, that a passage is left into a random location (`px`,`py`) during the building of the wall.

``````let mutable wx,wy = x + (if isHorizontal then 0 else rand.Next (width - 2))
,y + (if isHorizontal then rand.Next (height - 2) else 0)

let px,py = wx + (if isHorizontal then rand.Next width else 0)
,wy + (if isHorizontal then 0 else rand.Next height)

let dx,dy = if isHorizontal then (1,0) else (0,1)

let length,dir = if isHorizontal then (width ,S)
else (height,E)

for _ in 1 .. length do
if wx <> px || wy <> py then
grid.[wy].[wx] <- grid.[wy].[wx] ||| dir
wx <- wx + dx
wy <- wy + dy
``````

It then calls itself on each of the two new smaller sub-divisions created by building the wall.

``````let mutable nx,ny = x,y
let mutable w,h =
if isHorizontal then (width,wy-y+1) else (wx-x+1,height)
divide grid nx ny w h (chooseOrientation w h)

nx <- if isHorizontal then x      else wx + 1
ny <- if isHorizontal then wy + 1 else y
w  <- if isHorizontal then width               else x + width - wx - 1
h  <- if isHorizontal then y + height - wy - 1 else height
divide grid nx ny w h (chooseOrientation w h)
``````

It could continue this recursive process indefinitely. However, the line

``````if width >= 2 && height >= 2 then
``````

places a limit on the depth of the recursion. We don't sub-divisions less than two cell high by two cells wide (a sensible-but-arbitrary limit). It's also worth noting the call to `chooseOrientation`. This simple function balances the ratio of horizontal and vertical walls. It prefers horizontal walls for a region whose height is greater than it's width and vertical walls when the relationship between width and height is inverted. If it can't determine a relationship between the dimensions of a given area, it picks an orientation at random.

``````let chooseOrientation width height =
if    width < height  then HORIZONTAL
elif  width > height  then VERTICAL
elif  rand.Next 2 = 0 then HORIZONTAL
else                       VERTICAL
``````

So, all together, the function `buildMaze_RecursiveDivision` looks like

``````let buildMaze_RecursiveDivision width height =
let grid = Array.init height (fun _ -> Array.zeroCreate width)

let HORIZONTAL,VERTICAL = 1,2

let chooseOrientation width height =
if    width < height  then HORIZONTAL
elif  width > height  then VERTICAL
elif  rand.Next 2 = 0 then HORIZONTAL
else                       VERTICAL

let rec divide (grid:int[][]) x y width height orientation =
if width >= 2 && height >= 2 then
let isHorizontal = (orientation = HORIZONTAL)

let mutable wx,wy =
x + (if isHorizontal then 0 else rand.Next (width - 2))
,y + (if isHorizontal then rand.Next (height - 2) else 0)

let px,py = wx + (if isHorizontal then rand.Next width else 0)
,wy + (if isHorizontal then 0 else rand.Next height)

let dx,dy = if isHorizontal then (1,0) else (0,1)

let length,dir = if isHorizontal then (width ,S)
else (height,E)

for _ in 1 .. length do
if wx <> px || wy <> py then
grid.[wy].[wx] <- grid.[wy].[wx] ||| dir
wx <- wx + dx
wy <- wy + dy

let mutable nx,ny = x,y
let mutable w,h =
if isHorizontal then (width,wy-y+1) else (wx-x+1,height)
divide grid nx ny w h (chooseOrientation w h)

nx <- if isHorizontal then x      else wx + 1
ny <- if isHorizontal then wy + 1 else y
w  <- if isHorizontal then width               else x + width - wx - 1
h  <- if isHorizontal then y + height - wy - 1 else height
divide grid nx ny w h (chooseOrientation w h)
divide grid 0 0 width height (chooseOrientation width height)
grid
``````

At this point (and this blog entry is getting rather lengthy), we've mixed the functional and procedural qualities of F# to produce a reasonable implementation of a clever algorithm. But we're not quite done yet. The maze definition generated by this function describes the location of walls. However, our visualization function expects to be told where the passages are -- total mismatch! So, one last little routine is needed.

``````let translate (x,y) cell =
let mutable cell' = cell
if y = 0          then cell' <- cell' ||| N
if y+1 >= height  then cell' <- cell' ||| S
if x = 0          then cell' <- cell' ||| W
if x+1 >= width   then cell' <- cell' ||| E
All - cell'
``````

This function simply examines the walls in a cell, adding wall values (via bit-wise OR'ing) for being at the "edges" of the overall maze. It then determines the corresponding passages by subtracting the (possibly adjusted) cell value from the total possible number of passages (again via a bitwise OR'ing of values: `All = 15 = 1 OR 2 OR 4 OR 8`). So, in the end, passages exist where the walls aren't. We can call this on each cell, in turn, to convert an entire maze

``````built |> Array.mapi (fun y row  ->
row |> Array.mapi (fun x cell -> translate (x,y) cell))
``````

from a "built" defintion to a "carved" definition.

Now, we can put it all together. Calling

``````let mazeRD = buildMaze_RecursiveDivision 10 10
(builtToCarved >> viewMaze 30) mazeRD
``````

produces the final output. I've found the whole subject of maze generation to be fascinating. Hopefully, if you've read this far, you do as well. As always, thanks for reading. I look forward to your comments.

And happy coding.