Recursive Backtracking Maze Generation
Backtracking AlgorithmThis algorithm creates a new maze from a grid of cells. A random starting cell is chosen, and marked as visited. Then repeat the following steps:
- If there are unvisited neighbors, choose a random one and remove the wall between them. Mark this new cell as visited.
- If all neighbors have been visited, back up until finding a cell that has unvisited neighbors.
This is not the most efficient algorithm for generating a maze, but it does result in mazes with longer paths that are more attractive and more challenging to solve. The mazes are fully connected, meaning you can travel from any cell to any other cell.
This applet was last updated July 2019.