About Maze Generator
A perfect maze is a connected graph with no loops where there is exactly one path between any two cells — mathematically equivalent to a spanning tree of the grid graph. Four classic algorithms each produce perfect mazes with distinct statistical properties: the recursive backtracker (DFS) generates long winding corridors with few dead-ends; Prim's algorithm (starting from a random cell) produces mazes with many short branches and a more uniform texture; Kruskal's algorithm (randomly removing edges from a minimum spanning tree) tends towards uniform spanning trees; and Wilson's algorithm (loop-erased random walks) produces an unbiased uniform spanning tree with provable uniformity.
This simulation lets you choose grid size (up to 50×50) and algorithm, then watch the maze build in real time. Each algorithm's active frontier is colour-coded, making it easy to see how each traversal strategy explores the grid and why the resulting mazes have different visual textures and solution path characteristics.
Frequently Asked Questions
What makes a maze "perfect"?
A perfect maze has exactly one path between any two cells: it contains no loops and no isolated regions — mathematically it is a spanning tree of the grid graph. This means every cell is reachable (fully connected) and there are no cycles, so there is exactly one solution path from entrance to exit. Imperfect mazes have loops or braiding, which create multiple solutions and are used in game design for different player experiences.
How does the recursive backtracker (DFS) algorithm work?
Starting from a random cell, DFS marks it as visited and randomly chooses an unvisited neighbour, carves a passage, and recurses. When all neighbours are visited, it backtracks to the most recent cell with unvisited neighbours. The algorithm terminates when it has backtracked to the start with no unvisited cells remaining. The result has the DFS tree structure: long winding corridors with relatively few dead-end branches, and typically a single long solution path.
What visual difference can I expect between Prim's and Wilson's algorithms?
Prim's algorithm grows from a single seed cell, always choosing the random frontier edge with the minimum weight (effectively a random priority), producing mazes with short, bushy branches radiating outward — they feel more "rooted" and have many dead ends near the centre. Wilson's algorithm uses loop-erased random walks, which produce uniform spanning trees (every spanning tree equally likely), giving a statistically unbiased maze with a more organic, even distribution of branch lengths and no directional bias.
What is a uniform spanning tree and why does it matter?
A uniform spanning tree (UST) is a spanning tree chosen uniformly at random from all possible spanning trees of a graph. For an N×N grid there are astronomically many spanning trees (roughly eπN²/3 for large N). Wilson's algorithm generates USTs efficiently in expected O(N² log N) time using loop-erased random walks. USTs have connections to statistical physics (the critical Ising model) and are used in rigorous study of random maze properties.
How fast is each maze generation algorithm?
The recursive backtracker (DFS) runs in O(N²) time and O(N²) stack space (for an N×N grid). Prim's algorithm with a random priority queue is also O(N² log N) but typically faster in wall-clock time due to cache-friendly access. Kruskal's algorithm with a union-find structure runs in O(N² α(N²)) where α is the inverse Ackermann function (nearly linear). Wilson's algorithm has expected O(N² log N) time but high variance due to random walk lengths.
Can maze generation algorithms be parallelised?
DFS is inherently sequential. Kruskal's algorithm is the most parallelisable: the edges can be shuffled in parallel and union-find supports concurrent operations with careful synchronisation. Parallel maze generation typically divides the grid into rectangular regions, generates mazes within each region independently, then knocks down walls between regions to connect them — producing a valid maze but not a uniform one. GPU-based maze generation uses cellular automaton approaches for maximum parallelism.
How are mazes solved once generated?
A BFS from the entrance guarantees the shortest path in an unweighted grid maze, visiting cells level by level until the exit is found. DFS finds a path (not necessarily shortest) in O(N²) time. A* with Euclidean or Manhattan distance as a heuristic is faster in practice for large mazes. Dijkstra's algorithm handles weighted mazes (e.g., where different cells have different traversal costs, simulating terrain). All three are O(N²) worst-case for perfect mazes.
What is the "river" quality of a maze?
"River" (also called "straight-on bias") measures how often the corridor continues straight versus turning. DFS mazes have high river quality (long straight corridors) because the backtracking tends to continue in one direction until blocked. Prim's mazes have low river quality (many turns and short runs). Wilson's UST mazes have a river quality that converges to the theoretical expectation for random planar trees, intermediate between DFS and Prim's.
Are there maze algorithms designed for specific shapes?
Yes. The growing tree algorithm generalises DFS and Prim's: it maintains a list of active cells and picks the next cell to extend from this list (newest = DFS, random = Prim-like, oldest = BFS). Eller's algorithm generates mazes row by row using O(N) memory regardless of maze height, suitable for streaming or infinite mazes. Sigma mazes (hexagonal grids) and theta mazes (circular grids) use the same spanning-tree concept adapted to non-rectangular cell graphs.
How do maze algorithms relate to minimum spanning trees?
Every perfect maze is a spanning tree of the grid graph. Kruskal's maze algorithm is literally Kruskal's MST algorithm with random edge weights (assigning each wall a random number). Prim's maze algorithm is Prim's MST with random edge selection. Because the weights are random, both produce random spanning trees, though not uniformly random — they have a bias towards short edges (walls adjacent to already-visited cells). Wilson's algorithm corrects this bias to produce true USTs.