How Mazes Work

Mazes Are Graphs

A graph is a set of vertices (points) connected by edges (links). Every cell in a maze is a vertex, and every possible passage between cells is an edge.

A 4×3 grid has 12 vertices, each connected to its neighbors. If every connection is open, there are no walls. A maze is what you get when you selectively block some of those connections. Blocked edges = walls. Open edges = passages.

Building the Grid Graph

Each cell gets a number: vertex = row * width + col. We store the graph as an adjacency list — for each vertex, a list of its neighbors and the wall segment (LineBorder) between them:

// Vertex 5 in a 4-wide grid:
adjacencylist[5] = [
  [1, LineBorder(1,1, 2,1)],  // up
  [9, LineBorder(1,2, 2,2)],  // down
  [4, LineBorder(1,1, 1,2)],  // left
  [6, LineBorder(2,1, 2,2)]   // right
]

Two neighboring cells share the same border object. Outer walls use vertex -1 to mean "outside," with gaps left for entry and exit.

Spanning Trees = Perfect Mazes

A spanning tree is a subset of edges that connects every vertex with no cycles. It always has exactly V − 1 edges. Since there are no cycles, there's exactly one path between any two vertices — which is exactly what makes a perfect maze.

Click through to see the same 4×3 grid as a full graph, then its spanning tree, then the resulting maze:

Kruskal's Algorithm

To find a random spanning tree: shuffle all edges, then add each edge unless it would create a cycle. The cycle check uses Union-Find: each vertex starts in its own set; adding an edge merges two sets. If both vertices are already in the same set, skip it.

// Shuffle all edges, then:
for (edge of shuffledEdges) {
  rootA = find(edge[0])
  rootB = find(edge[1])
  if (rootA !== rootB) {     // different components
    parent[rootA] = rootB  // merge them
    tree.push(edge)         // keep this edge
  }
}

Watch below: each cell is colored by its connected component. When two components merge, their cells unify into one color and the wall between them disappears.

Finding the Solution

Since a spanning tree has exactly one path between any two vertices, we find it with DFS (depth-first search). Starting from the entrance, DFS records each vertex's parent. Then we trace backwards from the exit:

// After DFS fills parent[]:
path = []
u = exitVertex
while (parent[u] !== u) {
  path.push(u)
  u = parent[u]
}
// path = [exit, ..., start] reversed

To draw the solution, we connect the centers of adjacent cells along the path. Each maze type defines getCellCenter(vertex) — for a rectangle it's (col + 0.5, row + 0.5); for hexagons it's a trigonometric calculation in the sector's coordinate frame.

Beyond Rectangles

The generation algorithm only sees vertices and edges — it doesn't care about geometry. To make a hexagonal maze, we just define a different graph with different border shapes.

Our hexagonal maze divides a hexagon into 6 sectors, each containing triangular cells. Each sector is rotated 60° from the previous one:

Cells are addressed as (sector, updown, row, col) and positioned using rotated basis vectors. But the algorithm is identical — Kruskal's doesn't know or care that these are triangles arranged in a hexagon.

Try It Yourself

The whole system: graph → spanning tree → remove walls → draw borders. The abstraction lets any geometry — rectangles, hexagons, circles — reuse the same algorithm by changing only how vertices and borders are defined.