About

Maze generation is a subset of graph theory concerned with producing spanning trees over grid graphs. A correct maze has exactly one path between any two cells. This tool implements 8 distinct generation algorithms - from the bias-heavy Binary Tree to the uniform Aldous-Broder - each producing structurally different passage distributions. Getting algorithm choice wrong matters: Binary Tree creates obvious diagonal bias, Recursive Backtracker creates long corridors with low branching factor, and Kruskal's produces short, uniform dead ends. The generator operates on an W × H grid where each cell stores 4 wall bits. Generation time scales as O(W ⋅ H) for most algorithms. The solver supports BFS for guaranteed shortest path, A* with Manhattan heuristic for directed search, and Wall Follower for simulating physical traversal. Note: Wall Follower fails on mazes with isolated loops, which cannot occur in perfect mazes but can in modified ones.

Formulas

The maze is modeled as a grid graph G = (V, E) where |V| = W × H and each vertex connects to at most 4 neighbors. A perfect maze is a spanning tree of this graph: exactly W ⋅ H − 1 edges, zero cycles.

Walls per cell = 4 bits: N = 1, S = 2, E = 4, W = 8

A* heuristic uses Manhattan distance:

h(c) = |c_x − goal_x| + |c_y − goal_y|

where c is the current cell and goal is the target. The cost function is f(c) = g(c) + h(c), where g(c) is the actual distance from start.

Total passages in a perfect maze: P = W ⋅ H − 1. Total possible walls in the interior grid: W_total = 2 ⋅ W ⋅ H − W − H. Walls removed equals passages created.

Reference Data

Algorithm	Type	Bias	Dead-End %	River (Corridor Length)	Time Complexity	Perfect Maze
Recursive Backtracker	DFS + Stack	Long corridors	10%	High	O(n)	Yes
Kruskal’s	Edge-based	Uniform short	25%	Low	O(n log n)	Yes
Prim’s	Frontier	Radial from start	20%	Low	O(n log n)	Yes
Aldous-Broder	Random Walk	None (uniform)	20%	Medium	O(n²) avg	Yes
Binary Tree	Per-cell coin flip	NW diagonal	30%	Low	O(n)	Yes
Sidewinder	Row-based runs	Horizontal runs, N bias	25%	Medium-H	O(n)	Yes
Hunt-and-Kill	Walk + Scan	Long corridors	12%	High	O(n²) worst	Yes
Eller’s	Row-by-row sets	Slight horizontal	18%	Medium	O(n)	Yes
Solver Algorithms
BFS	Queue	Shortest path	-	-	O(n)	-
DFS	Stack	First found path	-	-	O(n)	-
A* (Manhattan)	Priority Queue	Directed shortest	-	-	O(n log n)	-
Wall Follower (Left)	Physical rule	Follows left wall	-	-	O(n)	-

Frequently Asked Questions

A perfect maze is a spanning tree of the grid graph: every pair of cells is connected by exactly one path. There are zero loops and zero isolated regions. All 8 algorithms in this tool produce perfect mazes. An imperfect maze contains loops (multiple paths between cells) or walled-off areas. Imperfect mazes are created by removing additional walls after generation.

Binary Tree makes an independent random choice at each cell: remove either the North wall or the West wall (never both, never neither). This forces the top row to be a single corridor running East and the left column to run straight North. The result is a consistent NW-to-SE diagonal texture. For unbiased results, use Aldous-Broder, which produces a uniform spanning tree at the cost of higher expected runtime.

BFS (Breadth-First Search) and A* both guarantee the shortest path in an unweighted grid. BFS explores all cells at distance d before distance d + 1. A* achieves the same result with fewer visited cells by using the Manhattan heuristic to prioritize cells closer to the goal. DFS and Wall Follower do not guarantee shortest paths.

Generation algorithms run in O(n) to O(n²) time where n = W × H. Canvas rendering is the bottleneck. Grids up to 150 × 150 (22,500 cells) render smoothly on modern hardware. Above 200 × 200, disable animation for instant generation. Aldous-Broder should be avoided above 50 × 50 due to its O(n²) expected time.

Yes. The PNG export produces a raster image at the canvas resolution. The SVG export produces a scalable vector file with clean line geometry suitable for laser cutting, CNC routing, or import into Unity/Unreal as a texture. For print, use the browser's print function - the tool includes print styles that hide UI controls and center the maze on an A4 page.

In a perfect maze (no loops), the left-hand Wall Follower always reaches the exit. If the maze contained loops - which this tool does not generate - the follower could circle indefinitely around an island of walls disconnected from the boundary. This tool only generates perfect mazes, so Wall Follower always terminates.