Let’s start by addressing the elephant in the room. Why the heck am I talking about making mazes?

Normally, I try to be practical when I’m writing or speaking. I want to give people tools they can use to make their coding lives better. So, I try to discuss things like creating DOM elements and processing JSON data. Because those things are practical. I would rather not waste people’s time on things they’re not going to use.

But, mazes, they’re not so practical.

Unless you’re working in game development, it’s unlikely that you’re going to need a maze in your web app. So, in that sense, knowing how to build a maze is useless. You’re never going to use it.

However, the nice thing about generating mazes is that they’re a challenge. A challenge that’s not too big, and not too small. You see, an issue I often have is that people ask me for ‘real world’ examples. But the trouble with ‘real world’ examples is that they’re complex. Much more complex than you can reasonably talk about in a blog post. There are all these edge cases that you have to handle. Things like error-handling, network outages, and input validation. But a maze is a contained problem that’s just complex enough to be interesting.

And it’s not a to-do list.

Furthermore, we can build our maze in such a way that we’ll learn about immutable data and recursion while we’re at it.

So let’s get into it.

Building a maze

How, then, do we build a maze? Let’s start with an example. We’ll work through building a small maze, step-by-step. We start with a grid. The one in the picture below is a 4 × 4 grid with 16 ‘rooms’ and ‘walls’ between each room.

Next, we pick a room at random. I’ve picked one near the middle, but it could be any room in the grid.

Then, we make a list of the adjoining rooms to the north, south, east, and west. But only if they that aren’t already connected to another room.

Next, we pick one of those rooms at random, and we punch a hole through the wall connecting those two rooms. In this case, we choose the room to the north.

Then, we repeat that process for the room we’ve just connected. This time, we have only two directions to pick from. This is because the room to the south is connected to this one, and we’re butting up against the north edge.

This time we’ll pick the room to the west. We join those two rooms, and move west.

Then we join the room to the south because there’s nowhere else to go.

Once again to the south, because there’s no other direction to join.

And we keep joining rooms until we reach a point where we can’t go any further. That is, there are no more directions to choose from. Once we get there, then we backtrack one square… and start again. We keep repeating this process until we have no unconnected squares left. Once that’s done, our maze is complete.

And, if we feel like it, we can add an entry and exit.

The maze-building algorithm

Now that we’ve seen an example, let’s try to write that out in words, as an algorithm.

1. Start with a grid of unconnected rooms and a randomly selected room.
2. Make a list of rooms adjacent to the current room, not yet connected to another room.
3. If this list is empty, go back one room and repeat from 2 (or finish).
4. Pick one of the rooms in the list at random and connect it.
5. Move to this new room and repeat from 2.

This algorithm will work for a grid of any size. And we’re almost ready to turn this into code. But, to make life easier for ourselves, we’re going to create our very own immutable data structure… from scratch.

Creating an immutable data structure

Now, in case you’re wondering, ‘immutable’ simply means ‘doesn’t change’. That is, we’ll write a class in such a way that once you create an object, you can’t modify it.

We’ll create a helper class, Point, that represents an x,y coordinate.

// point.js
class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

It has a constructor that takes an x-value, and a y-value, and assigns those to properties. There’s not much to it. But we now have a simple class.

Now, so far, this class doesn’t do very much. And it’s not immutable. So what we’re going to do is hide this class away. We won’t export it. Instead, we’re going to create a constructor function, point() (lowercase ‘p’). And that will be the only way to get yourself a Point.

// point.js
export function point(x, y) {
  // This is is how the function would work if it were
  // not immutable.
  const p = new Point(x, y);
  return p;
}

We have the beginnings of a constructor function. It takes an x and a y coordinate, calls the class constructor, and returns as a Point object. But we still haven’t achieved immutability yet. To achieve that, we’re going to memoise this function. That is, we’re going to create a cache of all the x,y values we’ve seen so far. And if we’ve already seen one we’ll return the point we created earlier.

We create our cache using the built-in Map structure. In this case, we call it allPoints.

// point.js
const allPoints = new Map();

With that in place, we can memoise our point() function. When a new call for a point comes in, we convert the x,y pair into a string. Then we use that to check to see if we’ve already seen this pair of numbers before. If we have, we return the existing point. If not, we’ll create a new one.

// point.js
export function point(x, y) {
  // Check the cache to see if we've seen this x/y
  // pair already.
  const key = `${x}-${y}`;
  if (allPoints.has(key)) return allPoints.get(key);

  // If we haven't seen this x/y pair, create a
  // new point.
  const newPoint = new Point(x, y);
  allPoints.set(key, newPoint);
  return newPoint;
}

While we’re at it, we’ll freeze the object so the JS runtime will stop anyone who tries to change those x- or y-values.

// point.js
export function point(x, y) {
  const key = `${x}-${y}`;
  if (allPoints.has(key)) return allPoints.get(key);

  const newPoint = new Point(x, y);

  // Freeze the object so its properties can't
  // be modified.
  Object.freeze(newPoint); 

  allPoints.set(key, newPoint);
  return newPoint;
}

Okay. We now have a helper class. And let’s face it, it doesn’t do much. So why do we bother? Why not just use a plain ol’ JavaScript object? Zero code needed.

Well, building a special class like this lets me do something plain objects can’t. I can compare them using triple equals.

So let’s try this. We create an object, objA, and another object, objB, and compare them with ===. And we get false. This is because objA and objB are pointing to two different locations in memory. But if we use our point() function, and compare with ===, we get true. Because we memoised our function, pA and pB are pointing to the same memory location.

const objA = {x: 3, y: 5};
const objB = {x: 3, y: 5};
objA === objB; // false

const pointA = point(3, 5);
const pointB = point(3, 5);
pA === pB // true

Again, you might legitimately ask, ‘So what?’ But things become much more interesting when we combine this with other data structures.

For example, we could use these points as keys in a Map structure. For this example, we’ll use the Map structure from the venerable Immutable.js library here. But it will work just fine with the built-in JavaScript Map too.

import { Map } from 'immutable';
import { point } from './point';

const mapWithObjects = Map([
  [{x: 3, y: 5}, 'object A'],
  [{x: 3, y: 5}, 'object B']
]);
console.log(mapWithObjects.toArray());
// Logs: [
//   [{x: 3, y: 5}, 'object A'],
//   [{x: 3, y: 5}, 'object B']
// ]

const mapWithPoints = Map([
  [point(3, 5), 'First Point 3,5'],
  [point(3, 5), 'Second Point 3,5']
]);
console.log(mapWithPoints.toArray());
// Logs: [
//   [Point {x: 3, y: 5}, 'Second Point 3,5']
// ]

So, we import the Map structure from Immutable. Then we create a Map using two identical plain objects. And this results in a Map with two entries—even though the values in the objects are the same. But if we use our point() constructor, the second point overwrites the first. We get a Map with a single entry. And this is where things start to get interesting. Because using the right data structures will be crucial for our maze-building algorithm.

Coding the algorithm

So, let’s get into writing our algorithm. We’ll go over it one more time.

1. Start with a grid of unconnected rooms and a randomly selected room.
2. Make a list of rooms adjacent to the current room, not yet connected to another room.
3. If this list is empty, go back one room and repeat from 2 (or finish).
4. Pick one of the rooms in the list at random and connect it.
5. Move to this new room and repeat from 2.

Step 1

If we’re going to turn this algorithm into code. We need to set things up so we can start our algorithm in the right state. The two main things we need are:

1. A grid of unconnected rooms; and
2. A random room to start in.

Let’s start building those out. We’ll start with the grid. And, for now, we’re going to assume we’re only building square mazes. To help us build our set of unconnected rooms, we’ll do a bit of maths.

The total number of rooms will be $n^2$. So, we create an array with $n^2$ entries, and map over it to create a Map structure that will represent our maze.

This (immutable) Map structure will have points as keys. And each value for the map will be a List of rooms it’s connected to.

Building the grid

So let’s build our grid.

import {Map, List} from 'immutable';

const emptyArray = new Array(n ** 2).fill(undefined);
const roomList = emptyArray.map(
  (_, i) => [point(i % n, Math.floor(i / n)), List()]
);
const grid = Map(roomList);

All we do is create an array with $n^2$ entries, then we map over it to create an array of pairs. The left item in each pair is a point. The x-value for the point is i modulo n. The y-value is i divided by n. And the right item in the pair is an empty list. We then pass that list of pairs to the immutable Map constructor, and that creates our Map.

A random room to start in

Next, we need a room picked at random to start in. But for this exercise, we’re trying to work with pure functions as much as possible. And something that’s different every time you call it, like Math.random(), is considered ‘impure’. So, we’re going to quickly whip up our own pseudo-random number generator to sidestep this problem.

// random.js
const M = 2 ** 31; // This defines our range of ints
const A = 110351245;
const C = 12345;

export function randomInt(seed) {
  return (A * seed + C) % M;
}

I won’t go into the details of how this one works, but it’s using prime numbers to generate a pseudorandom sequence. And this implementation is a lot like the random number generator used by the C language. (Most implementations of it, anyway).

import { randomInt } from './random';

// The seed can be any integer. Often, we
// use Date.now().
const seed = 1093487523;
const randomValue1 = randomInt(seed);
const randomValue2 = randomInt(randomValue1);

Here’s how we use that function. To get a random number, we start with a seed. And this seed can be any integer. We pass that seed to our randomInt() function. And, once we’ve called that, we can get another pseudorandom value. We do that by passing the returned value to randomInt() again. And if we keep doing that, we can get as many pseudorandom numbers as I want. But, if we give it the same starting seed, I will always get the same sequence of integers.

export function randomInRange(seed, n) {
  const nextSeed = randomInt(seed);
  const randVal = Math.abs(nextSeed) % n;
  return [nextSeed, randVal];
}

For our purposes, though, we mostly want a random number in a range between 0 and some number. So we’ll use another helper. All it does is a bit of maths to make the random number fit the range we want. But, it also returns the raw integer, so we can use it as a seed for future generation.

With that in place, we’re now able to pick a starting room at random from the grid. And we can put that all into a single function that generates our initial state.

// maze.js
import {Set, List} from 'immutable';
import {randomInRange} from './random.js';

function buildInitialState(n, seed) {
  const emptyArray = new Array(n ** 2).fill(undefined);
  const roomList = emptyArray.map(
    (_, i) => [point(i % n, Math.floor(i / n)), List()]
  );
  const grid = Map(roomList);

  const [newSeed, roomIdx] = randomInRange(
    seed,
    n ** 2
  );
  const room = roomList[roomIdx][0];

  return [room, grid, newSeed];
}

Recursion

We’re ready to code our actual algorithm. Now, we’re going to do this using recursion. And recursion has a bad reputation. People think it’s scary. One reason they think it’s scary is because it’s easy to accidentally cause infinite recursion. And that’s fair. I understand that. But I would argue that it’s just as easy to get yourself into a situation where you write a loop that never terminates.

You probably don’t do that, though, because you’ve been taught how to write loops safely. You’ve most likely been taught (or have taught yourself) two rules:

1. Pay attention to the state you’re changing; and
2. Know the exit condition.

let i = 10;
while (i > 0) {
  // Do something
  i--;
}

Suppose you’re writing a while loop, for example. One that repeats something 10 times. In that case, you make darn sure you’ve got some counter, i and that you decrement it each time around the loop. That counter i is the state we’re changing. It’s the thing we need to pay attention to.

And the exit condition is built in to while loops. In this case, i > 0.

When we’re writing recursive algorithms, we pay attention to the same things. They simply happen to live in different locations.

• For a recursive function, the changing state always goes into the function parameters. (That is, assuming we’re working with pure functions). And if you need to update more pieces of state, then you’ll need more function parameters.

• When we write a recursive function, we check our exit condition as early as possible. Much like how the exit condition is the first thing you write in a for-loop.

What is the state for our maze algorithm?

Let’s apply this to our maze algorithm. What state do we update as we go through the process? We have three components:

1. The current room: At each step, we’re considering a particular room. And the room we’re considering changes, so that means it’s part of our state.
2. The maze so far: Another thing we do as we go along is we update our maze by updating the list of rooms a given room is connected to.
3. The random seed: And there’s one final piece of state that might not be obvious. That’s our random number seed. We pass that along to the next iteration of our algorithm. This allows it to continue generating random numbers.

So we have enough here to create the signature for our buildMaze() function.

// maze.js
function buildMaze(room, mazeSoFar, seed0) {
  // Maze building code goes here
}

Step 2

We’re now all set up to create the initial state. So let’s figure out step 2 of our algorithm. That is, we want to make a list of adjacent rooms that aren’t yet connected. We’ll write a function to do that.

We start by creating some constants. One for each direction: NORTH, SOUTH, EAST, and WEST.

// point.js
export const NORTH = point(0, -1);
export const EAST = point(1, 0);
export const SOUTH = point(0, 1);
export const WEST = point(-1, 0);

And then we’ll create a helper function to add two points together:

// point.js
export const addPoint = (a, b) => point(
  a.x + b.x,
  a.y + b.y
);

And with those in place, we can write a function to find unconnected adjacent rooms. We make an array of the four directions, and map over it with addPoint() to get all the adjacent rooms. Then we filter out the rooms that are already connected.

// maze.js
import {point, NORTH, SOUTH, EAST, WEST} from './point';

function getCandidates(room, mazeSoFar) {
    return [NORTH, SOUTH, EAST, WEST]
        .map(direction => addPoint(room, direction))
        .filter((pt) => mazeSoFar.get(pt)?.size === 0);
}

We can then use that in our main function.

// maze.js
function buildMaze(room, mazeSoFar, seed0) {

  // Find adjacent unconnected rooms.
  const candidates = getCandidates(room, mazeSoFar);
}

Step 3

Now, it might be that there are no unconnected rooms left adjacent to the current room. That means we’ve gone as far as we can along this path. We’ve reached our exit condition.

// maze.js
function buildMaze(room, mazeSoFar, seed0) {

  // Find adjacent unconnected rooms.
  const candidates = getCandidates(room, mazeSoFar);
  if (candidates.length === 0) {
    return /* ????? */;
  }
}

So, we’re now supposed to go back one room. In our case, that means we’ll return. But we don’t quite know what we need to return yet. We’ll come back and fill that in momentarily.

Step 4

We’ve completed the first three steps, and we’re now at step four.

We want to pick a room from the candidate list at random. That gives us a new seed that we’ll hold on to for now.

// maze.js
function buildMaze(room, mazeSoFar, seed0) {

  // Find adjacent unconnected rooms.
  const candidates = getCandidates(room, mazeSoFar);
  if (candidates.length === 0) {
    return /* ????? */;
  }

  // Pick a room from the list of candidates.
  const [seed1, idx] = randomInRange(
    seed0,
    candidates.length
  );
  const roomToConnect = candidates[idx];
}

So, we now know which room to move on to next. We connect two rooms by updating our Map, pushing each room onto the list. And we move on to the next room by calling our buildMaze() function recursively. We just have to make sure that we update each piece of state that we pass on. And again, we still need to figure out that return value.

// maze.js
function buildMaze(room, mazeSoFar, seed0) {
  
  // … Snip …

  // Construct a new maze with the connected room.
  const mazeWithConnectedRoom = mazeSoFar
    .set(room, mazeSoFar.get(room).push(newRoom))
    .set(newRoom, mazeSoFar.get(newRoom).push(room));

  // Move to the newly connected room.
  const someReturnValueWeHaventFiguredOut = buildMaze(
    roomToConnect,
    mazeWithConnectedRoom,
    seed1
  );
}

What do we do when we get back?

When we call buildMaze(), our algorithm starts to connect a bunch of rooms in a long branch off this current room. But, there’s a chance that when it comes back, there still might be unconnected rooms adjacent to this one. So, we make another recursive call, but pass the same room to try out the remaining candidates.

However, when we call the recursive function, we need to make sure we update the state. And for that, we need the previous call to tell us what the new state should be. In particular, we need 2 things:

1. The updated maze.
2. A new random seed.

This list tells us what our return value from the function needs to be. Each time we call buildMaze() we will have to pass back each of these two values.

// maze.js
function buildMaze(room, mazeSoFar, seed0) {
  
  // … Snip …

  // Construct a new maze with the connected room.
  const mazeWithConnectedRoom = mazeSoFar
    .set(room, mazeSoFar.get(room).push(newRoom))
    .set(newRoom, mazeSoFar.get(newRoom).push(room));
  
  // Move to the newly connected room.
  const [newMaze, seed2] = buildMaze(
    roomToConnect,
    mazeWithConnectedRoom,
    seed1
  );
  
  // There may still be other directions we can connect
  // to this room, so we call buildMaze() again.
  return buildMaze(room, newMaze, seed2);
}

So we fill in those return values. And with those in place, we can make the final recursive call.

// maze.js
function buildMaze(room, mazeSoFar, seed0) {

  // Find adjacent unconnected rooms.
  const candidates = getCandidates(room, unconnected);
  if (candidates.length === 0) {
    return [mazeSoFar, seed0];
  }

  // Pick a room from the list of candidates.
  const [seed1, idx] = randomInRange(
    seed0,
    candidates.length
  );

  // Construct a new maze with the connected room.
  const mazeWithConnectedRoom = mazeSoFar
    .set(room, mazeSoFar.get(room).push(newRoom))
    .set(newRoom, mazeSoFar.get(newRoom).push(room));
  
  // Move to the newly connected room.
  const [newMaze, seed2] = buildMaze(
    roomToConnect,
    mazeWithConnectedRoom,
    seed1
  );
  
  // There may still be other directions we can connect
  // to this room, so we call buildMaze() again.
  return buildMaze(room, newMaze, seed2);
}

Once we sort out the other return values, then that’s it. We have everything necessary to build our maze.

Wiring it all together

All we need to do is wire it up with the initial state. We’ll do that in a new function.

// maze.js
export function maze(n, seed0) {
  const [room, emptyMaze, seed1] = buildInitialState(n, seed0);
  const [maze] = buildMaze(room, emptyMaze seed1);
  return maze;
}

We craft the initial state, then we build our maze and return it.

Demo

And putting that all together, we get something like the following demo. If you have JavaScript enabled, try it out.

Rendering

Now, all we’ve done so far is to create a map of point objects. We haven’t talked at all about how we render it. And the beauty of the web platform is that we have so many options. But there’s a lot to discuss there, so I’ve broken that out into a separate article.

So what?

Is this the most performant way to create a maze?

No.

Is this the most memory-efficient way to create a maze?

No.

Why bother with all this, then? Why muck around with recursion and immutable data structures?

Two reasons.

1. Because it helps you think differently
   Orson Welles supposedly said “The enemy of art is the absence of limitations.”¹ That is to say, imposing constraints encourages creativity. Programming with immutable data structures and recursion is a constraint. But it’s a constraint that forces you to look at challenges differently. And this can (and often does) lead to more elegant, creative solutions.

2. Because it’s fun
   I called this article the ‘joy’ of immutable data, recursion, and pure functions. Every so often, it’s fun to just explore an idea and see where it takes you. Every so often, it’s fun to create a maze, just for the heck of it. And, personally, I think with all that’s going on in the world, we could use a bit more fun and joy in our lives.