Recursive Backtracker Maze Generator

The recursive backtracker algorithm is really a general purpose depth-first search. When used for maze generation, it it slightly modified to pick the path at random, whereas if used for actual search purposes, one would typically just search each level in linear order. It tends to produce mazes with long, winding corridors and a very long, twisting solution.

A perfect maze is a maze in which there is exactly one path from any point in the maze to any other point. That means you can't end up going around in circles, but you will often encounter dead ends, forcing you to turn around and go back.

The maze maps generated here includes a default version without any start and finish positions, so you can decide those for yourself: there will be a solution from any point in the maze to any other point. If you want inspiration, you can enable a suggested start and finish position - and even see the solution between the two.

The recursive backtracker algorithm is a depth-first search method for generating perfect mazes (mazes with no loops and a single path between any two points). It is simple, efficient, and produces visually appealing mazes with long, winding corridors.

Despite its name, it doesn't necessarily have to been implemented using recursion. It is often implemented in an iterative approach using a LIFO queue (i.e. a stack). For very large mazes, using recursion is more likely to result in call stack overflow, depending on programming language and available memory. A LIFO queue can more easily be adapted to handling large amounts of data, even keeping the queue on disk or in a database if available memory is insufficient.

How It Works

The algorithm operates using a stack-based depth-first search approach. Here’s the step-by-step breakdown:

1. Choose a starting cell and mark it as visited.
2. While there are unvisited cells:
   • Look at the neighboring cells that have not yet been visited.
   • If at least one unvisited neighbor exists:
     • Randomly choose one of the unvisited neighbors.
     • Remove the wall between the current cell and the chosen neighbor.
     • Move to the chosen neighbor and mark it as visited.
     • Push the current cell onto the stack.
   • If no unvisited neighbors exist:
     • Backtrack by popping the last cell from the stack.
3. Continue this process until the stack is empty.

An interesting fact about this algorithm is that it works both as a maze generator and as a maze solver. If you run it on an already generated maze and just stop when you hit the decided end point, the stack will contain the solution to the maze.

I actually have two versions of this algorithm in play on this site: a LIFO queue based one for generating mazes on this page and a recursion based one for solving mazes, also mazes generated by other algorithms (that's how the maps with the solutions are made). Having two different versions is just for sports because I'm a nerd who finds it interesting, either could have worked for both ;-)