Let's build a maze in SVG

The algorithm

After digging into various maze generation algorithms, the randomized depth-first search seemed like the simplest to implement in real time. The algorithm could be described as:

• Pick a cell (I’m using the top-right corner, but you could also pick a random cell)
• Pick a random neighbor of the current cell
• Connect the current cell to the neighbor
• Make the neighbor the current cell
• Repeat until there are no unvisited cells

Whenever a cell does not have any unvisited neighbors, you have to backtrack to a previous cell with unvisited neighbors. This requires building up a stack of cells that have been visited but not yet fully explored.

A single SVG path

Let’s go ahead and dig into the code before I get too far ahead of myself. In the HTML, there is simply an inline svg with a single path inside.

<svg class="maze" xmlns="http://www.w3.org/2000/svg">
  <path stroke-width="0.15" fill="none" d="" />
</svg>

For my purposes, the SVG is before the rest of my layout elements in the DOM, and it has position: fixed.

I am also setting the stroke-width to 0.15. Technically, what looks like walls in the final maze are actually the corridors, but the aesthetic is the same. Please don’t tell anyone that my maze is a lie.

The JavaScript

The runMaze function starts by setting the viewBox of the SVG to the size of the window divided by 16, so I end up with a grid of 16x16 cells that can cover the entire viewport.

  async function runMaze() {
    const CELL_SIZE = 16;
    const w = Math.ceil(window.innerWidth / CELL_SIZE);
    const h = Math.ceil(window.innerHeight / CELL_SIZE);
    const svg = document.querySelector('svg');
    svg.setAttribute('viewBox', `0 0 ${w} ${h}`);

The next thing it does is instantiate the stack with the starting cell. I am representing a cell as an array like [2,3]. There is also a Set to keep track of which cells have been visited. Since arrays are passed by reference, I have to convert the cell to a string before adding it to the set. If I were to call visited.has([2,3]), for example, it would always return false for the same reason that [2,3] === [2,3] is false.

const start = [w, 0];
const stack = [start];
const visited = new Set([start.join(',')]);

To begin drawing the maze, the path is updated to begin drawing at the starting cell. For the sake of keeping the article concise, I am leaving out some code that resets the maze whenever the window is resized.

const path = svg.firstElementChild;
path.setAttribute('d', `M${start[0]},${start[1]}`);

Whenever we have to backtrack up the stack, we do not want to connect the last drawn cell to the next, so I have a moveNext flag that will be set to true whenever we backtrack.

let moveNext = false;

Now we can start the main loop. The loop will continue until the stack is empty. The last cell in the stack is the current cell.

    while (stack.length > 0) {
      const cell = stack[stack.length - 1];
      const neighbor = getRandomNeighbor(cell, visited, w, h);

The getRandomNeighbor function will return a random unvisited neighbor of the current cell. If there are no unvisited neighbors, it will return null.

function getRandomNeighbor(cell, visited, w, h) {
  const neighbors = getNeighbors(cell, visited, w, h);
  if (neighbors.length === 0) return null;
  return neighbors[Math.floor(Math.random() * neighbors.length)];
}

function getNeighbors(cell, visited, w, h) {
  let neighbors = [];
  const [x, y] = cell;
  if (x > 0) neighbors.push([x - 1, y]);
  if (x < w - 1) neighbors.push([x + 1, y]);
  if (y > 0) neighbors.push([x, y - 1]);
  if (y < h - 1) neighbors.push([x, y + 1]);
  neighbors = neighbors.filter((n) => !visited.has(n.join(',')));
  return neighbors;
}

Back in our loop, once we have a neighbor, we add it to the stack and mark it as visited. We also draw our SVG path to the cell and ensure moveNext is false.

      if (neighbor) {
        stack.push(neighbor);
        visited.add(neighbor.join(','));
        appendToPath(path, neighbor, moveNext);
        moveNext = false;

The appendToPath function appends the cell to the path’s d attribute. If moveNext is true, it will append an M command to move to the cell. Otherwise, it will append an L command to draw a line to the cell.

  function appendToPath(path, cell, isMove) {
    const d = path.getAttribute('d')!;
    path.setAttribute('d', d + ` ${isMove ? 'M' : 'L'}${cell[0]},${cell[1]}`);
  }

If there are no neighbors, we have to backtrack. We pop the last cell off the stack and set moveNext to true.

      } else {
        stack.pop();
        moveNext = true;
      }
    }
  }

If you were to put it all together, you would now have a function that instantly generates a maze!

Final touches

However, I wanted to have the maze draw slowly over time. I did this by adding a requestAnimationFrame promise to the loop. I also added a counter that would only call requestAnimationFrame every 3 iterations. This way, the maze would be generated in real time, but it would not be too slow.

I also decided to leave the maze incomplete. I like the way it looks with gaps, and it also helps reduce performance issues caused by having such a large path on the page. I did this by adding an additional i / w < 60 condition to the while loop.

Here is the full runMaze function:

async function runMaze() {
  const CELL_SIZE = 16;
  const w = Math.ceil(window.innerWidth / CELL_SIZE);
  const h = Math.ceil(window.innerHeight / CELL_SIZE);
  const svg = document.querySelector('svg');
  svg.setAttribute('viewBox', `0 0 ${w} ${h}`);
  const start = [w, 0];
  const stack = [start];
  const visited = new Set([start.join(',')]);
  const path = svg.querySelector('path');
  path.setAttribute('d', `M${start[0]},${start[1]}`);
  let moveNext = false;
  let i = 0;
  while (stack.length > 0 && i / w < 60) {
    const cell = stack[stack.length - 1];
    const neighbor = getRandomNeighbor(cell, visited, w, h);
    if (neighbor) {
      stack.push(neighbor);
      visited.add(neighbor.join(','));
      appendToPath(path, neighbor, moveNext);
      moveNext = false;
      if (i % 3 === 0) await new Promise(requestAnimationFrame);
    } else {
      stack.pop();
      moveNext = true;
    }
    i++;
  }
}