This simulation builds a perfect maze on a square grid and animates the carving in real time. Every cell stores its open passages as a 4-bit mask (north, east, south, west), and an algorithm decides which walls to knock down. All four methods produce a spanning tree over the grid: a maze with exactly one path between any two cells and no loops. You can watch the structure grow cell by cell.
The Algorithm selector chooses between Recursive Backtracker (DFS), Prim's randomised, Kruskal's randomised and Wilson's loop-erased random walk. The Grid size slider sets the W×H dimensions (5 to 60), and Speed controls how many carving steps run per frame. After generation, Solve runs a breadth-first search to trace the shortest route from the top-left start to the bottom-right exit. Maze algorithms underpin game level design, robotics path planning and graph theory teaching.
What is a maze generator?
It is a program that carves a grid of cells into a connected network of passages and walls. This version produces perfect mazes, meaning there is exactly one path between any two points and no closed loops. The result is mathematically a spanning tree drawn over the grid.
What do the four algorithms do differently?
DFS Backtracker carves long, winding corridors; Prim's randomised method grows from a frontier and yields short, bushy branches; Kruskal's joins random disjoint regions for a uniform texture; and Wilson's produces an unbiased maze where every possible layout is equally likely. They build the same kind of maze with very different visual character.
How does the solver find the path?
Clicking Solve runs a breadth-first search from the start cell (top-left) outward, recording each cell's predecessor. Because BFS explores in order of distance, the first time it reaches the exit (bottom-right) it has found the shortest path, which is then traced back and drawn in green.
Grid size sets both the width and height of the square maze, from 5×5 up to 60×60 cells, so the total cell count is that value squared. Speed maps to a steps-per-frame schedule (1, 1, 2, 4, 8, 15, 30, 60, 150, 500), letting you slow the carving to a crawl or finish a large maze almost instantly.
A perfect maze is fully connected and contains no loops, so there is precisely one route between any pair of cells. In graph terms it is a spanning tree of the grid graph: every cell is reachable, and removing any passage would disconnect the maze.
Wilson's algorithm uses loop-erased random walks: it walks randomly from an unvisited cell until it hits the existing maze, erasing any loops it forms along the way. This procedure samples uniformly at random from all possible spanning trees, so every maze of that size is equally probable. David Wilson published it in 1996.
It starts at a cell, marks it visited, and repeatedly moves to a random unvisited neighbour, carving the wall between them and pushing the cell onto a stack. When a cell has no unvisited neighbours it backtracks by popping the stack. This depth-first exploration produces the long, snaking corridors typical of DFS mazes.
Each cell holds a one-byte bitmask where bits represent open passages to the north, east, south and west (values 1, 2, 4 and 8). Carving a wall sets the relevant bit in both adjacent cells. The renderer reads these bits to draw connecting bridges between cells, and the solver reads them to know which moves are legal.
Yes. Each algorithm is implemented faithfully: DFS with an explicit stack, Prim's with a random frontier, Kruskal's with a shuffled edge list and union-find connectivity, and Wilson's with genuine loop-erased walks. The BFS solver is a standard shortest-path search, so the highlighted route is always optimal for a perfect maze.
Kruskal's shuffles every wall and considers them one at a time, carving a wall only if the two cells it separates belong to different regions. A union-find (disjoint-set) structure tracks which cells are already connected, so the algorithm can avoid creating loops while merging the grid into a single tree.
They appear in video game level and dungeon generation, procedural content tools, and as classic teaching examples for graph traversal and spanning trees. The same ideas extend to robotics and network routing, where finding connected, loop-free paths through a space is essential.
Four generation algorithms — DFS Backtracker, Prim's, Kruskal's and Wilson's loop-erased random walk — animated live. Then solve instantly with BFS to find the shortest path.
Each algorithm creates a different "texture" of maze. DFS makes long corridors, Prim's creates branching patterns, Kruskal's is uniform, Wilson's is unbiased.
Pick a generation algorithm and watch it carve the maze. Then click Solve to see BFS find the shortest path from start to finish.
Wilson's algorithm produces a perfectly uniform random spanning tree — every possible maze is equally likely. It uses loop-erased random walks, discovered by David Wilson in 1996.