Algorithms That Create and Navigate Labyrinths
A maze is a puzzle with a surprisingly deep connection to graph theory, spanning trees, and computational complexity. Every perfect maze is a spanning tree of a grid graph, and every generation algorithm produces mazes with a distinct character—long winding corridors, branching dead ends, or fractal room structures. Watch each algorithm carve or build walls step by step, then unleash pathfinding solvers to navigate the result. The walls tell the story of the algorithm that made them.
Seven distinct approaches to creating perfect mazes, from simple coin-flipping to sophisticated set operations. Each produces a unique visual texture.
Depth-first search with a stack. Creates long, winding corridors with few branches. The most popular maze generation algorithm—watch it carve through the grid.
Grows from a frontier of walls. Picks random walls and carves if they connect new cells. Creates many short dead ends with a radial growth pattern.
Union-find on shuffled edges. Watch colored sets merge as walls dissolve. Each color is a connected component converging into one spanning tree.
The only wall-adding algorithm. Starts open, recursively bisects with walls containing single passages. Creates fractal-like rooms with long straight walls.
Loop-erased random walks produce uniformly random spanning trees. Watch the walk wander and erase loops. Slow to start, then accelerates as the maze grows.
Row-by-row generation using disjoint sets. Merges cells horizontally, then connects downward. Can generate infinitely tall mazes examining one row at a time.
The simplest generators. Binary Tree flips a coin per cell; Sidewinder extends runs then connects north. Notice each algorithm's characteristic bias.
Generate a maze, then watch algorithms find the path from start to finish. Compare heuristic-guided search against blind exploration.
Generate a maze and race two pathfinders. A* uses Manhattan distance to guide its search toward the goal; Dijkstra explores uniformly in all directions.
Two classic solving strategies. Dead-end filling works from a bird’s-eye view; Trémaux’s algorithm navigates with only local knowledge, marking passages as it walks.
Four generators race side by side on identical grid sizes. Compare DFS, Prim’s, Kruskal’s, and Recursive Division in real time. See how each shapes the maze differently.