One afternoon, the thought randomly struck me that I should learn about graph theory. I'd heard of it before but never wanted to dig into it properly. After reading some articles and watching a few tutorials, I came away with a basic understanding of what graph theory is and how graph traversal works. To cement that knowledge, I decided to build something with it. That's how Mazier was born.

Live Preview

Visit https://mazier.sihilel.com to fully experience the maze generator.

What Is Graph Theory?

I'm still a beginner at this as I write, so I'll keep the explanation simple. Graph theory is a branch of mathematics that studies networks made of points (called nodes or vertices) connected by lines (called edges). Think of it like a map where cities are the vertices and roads between them are the edges. Graph theory gives you the tools to reason about how everything is connected.

What Is Graph Traversal and Depth-First Search?

Graph traversal means visiting every vertex in a graph in a systematic way. Imagine starting from one city and traveling to every other city by following the roads, without missing any.

Depth-First Search (DFS) is one specific traversal strategy. You start at a single vertex, pick one of its unvisited neighbors, move to it, and repeat. You always go deeper along one path before trying a different direction. When you reach a dead end (a vertex whose neighbors have all been visited), you backtrack to the previous vertex and explore its remaining unvisited neighbors. This continues until every vertex has been visited.

In the city analogy, you start in one city, drive to a connected city, then keep driving as far as you can along one route. When you hit a city where every road leads somewhere you've already been, you turn back to the last intersection and try a different road.

How Mazier Works

Now that we have a basic idea of graph theory, let's walk through how Mazier generates a maze.

The Graph Data Structure

Before anything else, Mazier needs a way to represent a graph in code. It uses a Graph class backed by an adjacency list. This is basically a Map where each key is a vertex and each value is a Set of that vertex's neighbors. When an edge is added between two vertices, it's recorded in both directions (making the graph undirected), so you can traverse from either side.

Generating the Maze Grid

Mazier starts by creating a grid of vertices and connecting each one to its immediate neighbors (up, down, left, right) to form a graph.

Vertices are numbered $0$ through $(h \times w) - 1$, laid out in column-major order. That means the index increases going down each column first, then moves to the next column. Given a vertex index $i$, its position in the grid is:

$$x_{\text{col}} = \lfloor\, i \;/\; h \,\rfloor \qquad y_{\text{row}} = i \bmod h$$

Each vertex is connected to its bottom neighbor ($i + 1$) if it isn't already at the bottom of its column, and to its right neighbor ($i + h$) if it isn't already in the rightmost column.

For example, a 4×4 grid looks like this:

 0 — 4 — 8  — 12
 |   |   |    |
 1 — 5 — 9  — 13
 |   |   |    |
 2 — 6 — 10 — 14
 |   |   |    |
 3 — 7 — 11 — 15

Every vertex here has edges to its adjacent neighbors, giving us a fully connected grid graph.

Selecting a Starting Vertex

DFS needs a starting vertex. At first, I just used 0 (the top-left corner). It worked, but the mazes tended to look similar because the algorithm always began its exploration from the same spot.

The fix was to pick a random perimeter cell, which is a vertex that sits on any of the four outer edges of the grid. The code collects all cells along the left, right, top, and bottom borders into a list, then picks one at random. Starting from different perimeter positions gives the DFS different paths to explore, which produces more varied mazes.

Running Depth-First Search

I used a recursive function to run DFS. Getting it right took three iterations.

First iteration, plain DFS pre-order

The simplest approach. Visit a vertex, record it, then recurse into a random unvisited neighbor. The recorded order of vertices is the "path" of the maze.

function randomDFS(graph: Graph, startCell: string): string[] {
  const visited: Set<string> = new Set();
  const order: string[] = [];

  function dfs(startVertex: string) {
    visited.add(startVertex);
    order.push(startVertex);
    const neighborsInRandomOrder = Array.from(
      graph.getNeighbors(startVertex),
    ).sort(
      (a, b) => Number(a) * Math.random() - Number(b) * Math.random(),
    );
    for (const n of neighborsInRandomOrder) {
      if (visited.has(n)) continue;
      dfs(n);
    }
  }

  dfs(startCell);
  return order;
}

The problem was that when DFS backtracks from a dead end, the next vertex it records might not be a neighbor of the previous one. If you draw a line through the order, the path jumps across the grid and connects non-adjacent cells with phantom walls that shouldn't exist.

Second iteration, dead-end marker after every recursive call

To fix the jumps, I added a "DE" (dead end) marker to the order after every recursive call returns. The renderer treats "DE" as a signal to "lift the pen."

function dfs(startVertex: string) {
  visited.add(startVertex);
  order.push(startVertex);
  const neighborsInRandomOrder = Array.from(
    graph.getNeighbors(startVertex),
  ).sort(
    (a, b) => Number(a) * Math.random() - Number(b) * Math.random(),
  );
  for (const n of neighborsInRandomOrder) {
    if (visited.has(n)) continue;
    dfs(n);
  }
  order.push("DE");
}

This solved the non-neighbor problem, but introduced a new one. Every single backtrack now started a new line segment, resulting in a maze full of short, disconnected lines instead of continuous corridors.

Third iteration, conditional dead-end markers (the current solution)

The insight was to only insert a "DE" when it's actually needed. Before pushing a vertex into the order, the algorithm checks whether the previous vertex in the list is a neighbor of the new one. If it is, the path continues naturally. If it isn't (meaning we've backtracked past a dead end), a "DE" is inserted first to break the line.

function dfs(startVertex: string) {
  visited.add(startVertex);
  pushToOrder(startVertex);
  const neighborsInRandomOrder = Array.from(
    graph.getNeighbors(startVertex),
  ).sort(
    (a, b) => Number(a) * Math.random() - Number(b) * Math.random(),
  );
  for (const n of neighborsInRandomOrder) {
    if (visited.has(n)) continue;
    dfs(n);
  }
}

function pushToOrder(vertex: string) {
  const lastVertex = order.length > 0 ? order[order.length - 1] : null;
  if (lastVertex && !graph.getNeighbors(lastVertex).has(vertex))
    order.push("DE");
  order.push(vertex);
}

This produces long, winding corridors with dead-end breaks only where they belong, which is exactly what a good maze looks like.

A note on the randomization. The neighbors are shuffled by sorting with a randomized comparator (Number(a) * Math.random() - Number(b) * Math.random()). This isn't a perfectly uniform shuffle, but it introduces enough randomness to make each maze different.

Rendering the Maze onto an HTML Canvas

The output of the DFS is an array of vertex indices interspersed with "DE" markers. Turning this into a visual maze is straightforward.

Drawing the grid. First, a light gray grid is drawn onto a 600×600 HTML <canvas>. The cell width and height are calculated by dividing the canvas dimensions by the number of columns and rows, respectively.

Drawing the maze path. The renderer walks through the order array. For each vertex, it calculates the center point of that cell on the canvas using:

$$x = \text{col} \times w_{\text{cell}} + \frac{w_{\text{cell}}}{2} \qquad y = \text{row} \times h_{\text{cell}} + \frac{h_{\text{cell}}}{2}$$

It then draws a line from the previous vertex's center to the current one. When it encounters a "DE" marker, it finishes the current line stroke, "lifts the pen," and moves to the center of the next vertex to begin a new stroke.

The result is a set of connected paths separated by gaps that look like walls.

Download. There's also a download button that copies the canvas to an offscreen canvas with a white background and exports it as a PNG.

Since I built all of the maze generation logic myself, I used AI to help generate parts of the frontend code (the React components, canvas hooks, and UI controls).

Wrapping Up

This is just me building things as I learn. It was a fun, simple project even with my schedule being pretty busy these days. I'm happy with how it turned out, and I now have a much better intuition for graph traversal than I did before picking this up.