Recursive Backtracking Maze Generation

Backtracking Algorithm

This 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:

1. If there are unvisited neighbors, choose a random one and remove the wall between them. Mark this new cell as visited.
2. If all neighbors have been visited, back up until finding a cell that has unvisited neighbors.

Cells that have been visited but not "backed over" are shown in light blue. Eventually, the original cell is again reached and the process is complete.

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.

About the Applet

This applet was created using JavaScript and the P5 library. No other libraries/dependencies are required. If you are having trouble viewing the applet, be sure JavaScript is enabled in your browser. Click here for instructions. Internet Explorer is not recommended for this applet.

This applet was last updated July 2019.