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.
• 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.