Maze generation & solving

Perfect mazes

Every maze generated here is perfect: there is exactly one path between any two cells, no loops, no isolated regions. Mathematically, this means the maze is a spanning tree of the grid graph — a connected subgraph that includes every cell exactly once with no cycles. Different algorithms produce different spanning trees with different characters. The recursive backtracker tends toward long, winding corridors. Prim’s tends toward short branches in every direction. The difference is not in the destination but in the data structure: a stack produces depth, a random list produces breadth.

DFS vs BFS in generation

The recursive backtracker uses depth-first search with an explicit stack. It picks a random unvisited neighbor, carves a passage, and pushes the new cell. When it hits a dead end (no unvisited neighbors), it pops back. The last-in-first-out discipline means it always pushes forward until completely stuck, producing long, winding corridors with a strong directional bias. Prim’s algorithm, by contrast, maintains a frontier of all walls adjacent to the visited region and picks one at random. This means it can grow in any direction at any time, producing short, organic branches — bushy and fractal-looking. The data structure is the maze’s personality.

Union-Find and Kruskal’s

Kruskal’s algorithm treats each cell as a node and each potential passage as an edge. It shuffles all edges randomly and processes them one by one, only carving a passage if the two cells on either side are not already connected. This requires efficiently checking connectivity — the union-find data structure with path compression and union by rank does this in nearly O(1) amortized time. The resulting maze has a uniform, random feel because edge selection is global rather than local. No cell is preferred over another. The maze grows everywhere at once.

Shortest path and A*

BFS guarantees the shortest path because it explores all cells at distance d before any at distance d+1. The wavefront expands uniformly from the start until it reaches the goal. A* does the same but smarter: it uses a priority queue ordered by f(n) = g(n) + h(n), where g is the distance traveled so far and h is the Manhattan distance to the goal. The heuristic tells A* which direction to look first. In an open grid, A* would go nearly straight to the goal. In a maze, walls force detours — but A* still dramatically reduces the search space compared to blind BFS, because it avoids exploring corridors that lead away from the goal.

The topology of mazes

A perfect maze is a tree, so it is simply connected — any closed curve drawn on the maze can be continuously shrunk to a point without crossing a wall. This is exactly the condition that makes the wall-follower algorithm work: place your left hand on the wall and walk, and you will eventually trace every reachable passage and reach the exit. Add even a single loop and this guarantee breaks. The wall follower can get trapped circling the loop forever. Real-world mazes — the Cretan Labyrinth, Hampton Court — are usually multiply connected. The shift from tree to graph changes which algorithms work, and which fail.

Mazes in computer science

Maze generation is graph algorithm pedagogy made visible. But mazes appear in serious computer science too: procedural game level generation (Rogue, 1980, used maze algorithms to generate dungeon layouts), VLSI chip routing, network topology design, and robot navigation testing. The recursive division algorithm has a particularly elegant application: it naturally produces rooms connected by doorways, which is why it appears in roguelike dungeon generators. The maze is one of humanity’s oldest computational puzzles — Cretan labyrinth designs date to 1200 BCE, carved into clay tablets by people who understood, intuitively, the relationship between topology and solvability.