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.

Mta

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.

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

Other Links to this Post

WordPress Themes