Maze algorithms
8 generators and 7 solvers. Tap one to watch and hear it.
Generators: how a maze gets made
- Recursive BacktrackerThe Recursive Backtracker carves a maze by walking to a random unvisited neighbour until it gets stuck, then backing up to the last cell with a way forward.
- Prim's AlgorithmRandomized Prim's algorithm grows a maze outward from one cell by repeatedly connecting a random cell on its frontier.
- Kruskal's AlgorithmRandomized Kruskal's algorithm shuffles every wall in the grid and removes each one that joins two separate regions.
- Wilson's AlgorithmWilson's algorithm builds a maze from loop-erased random walks, and every possible maze is equally likely.
- Aldous-BroderAldous-Broder wanders the grid at random and carves a passage every time it steps into a cell it hasn't seen before.
- Hunt-and-KillHunt-and-Kill carves a random walk until it gets stuck, then scans the grid for an unvisited cell next to the maze and starts again from there.
- Eller's AlgorithmEller's algorithm builds a maze one row at a time, remembering only the current row.
- Binary TreeThe Binary Tree algorithm visits every cell and opens a passage either north or west, chosen at random.
Solvers: how a maze gets solved
- Breadth-First SearchBreadth-First Search explores a maze in rings: every cell one step away, then two, then three, until it reaches the exit.
- Depth-First SearchDepth-First Search follows one corridor as far as it goes, and only backs up when it hits a dead end.
- A* SearchA* search explores the cells that look closest to the exit first, while still guaranteeing the shortest path.
- Wall FollowerThe Wall Follower keeps one hand on the wall and walks, which always gets you out of a maze whose start and exit are on the outside wall.
- DijkstraDijkstra's algorithm always expands the cell with the lowest distance from the start, so it finds the shortest path.
- Greedy Best-FirstGreedy Best-First Search always moves to the cell that looks closest to the exit, ignoring how far it has already come.
- Random MouseThe Random Mouse picks a random direction at every step. It has no memory and no plan, and it almost never finds the exit in time.