## Recursive Backtracking

Here’s yet another maze, produced by a method called recursive backtracking. Unlike the previous algorithm, which is something I came up with myself, this is a well-known algorithm with rather delightful properties, as you can see for yourself.

The algorithm is straightforward:

- Create a new, blank maze in which all cells are free. (A free cell is connected to no other cell). You can think of the free cells as square rooms with a closed door in each of the four walls.
- Initialize an empty stack of cells.
- Let C be a cell chosen randomly.
- Repeat:
- If there is at least one free cell next to C,
- Let D be a free cell next to C, chosen randomly.
- Open a door from C to to D.
- Push C onto the stack.
- Let C = D.

- Otherwise,
- Pop an old C from the top of the stack.

- If there is at least one free cell next to C,
- Until the stack is empty.

The maze shown above uses a slight variant called “inertia”, which makes it a little more likely that the next free cell chosen will be in the same direction as the previous. This makes the straight corridors just a little longer.

Like the previous algorithm, it produces a “dendritic” maze: one in which each cell is connected to every other cell by exactly one path. That’s cool if you’re printing the maze on a place mat, but a little boring if you’re using the maze in a game, so the next step is to take a maze like this and modify it in various ways.

By Marie, November 13, 2012 @ 6:53 pm

I haven’t programmed anything in 20 years, and never graphics,

but how do you make sure you have exactly one entrance and one exit?

By Will Duquette, November 17, 2012 @ 6:52 pm

You generate a maze in which every cell connects to every other cell, with a box around the whole thing. Then you poke two holes in the box.