Skip to main content
kld.dev

Let's build a maze in SVG

February 16, 2023

If you’re viewing this on a larger screen, you might notice that a maze is being drawn in the background of this page right now. It’s very subtle because I wanted it to be more like texture than a distraction.

This is an idea I’ve had for a while. I love the aesthetics of mazes. They have an organized chaos to them. The same goes for labyrinths, though they are technically different since a labyrinth is traditionally supposed to have a single path to the center with no dead ends or forks. They are less about getting lost and more about finding your way. Also minotaurs.

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++;
  }
}

Webmentions

Kurau :tokyo: reposted this.