A Bigger Maze

For Mark Lambert, here’s a bigger maze with an entrance and an exit.

Bigmaze

Kardde was curious how it was produced.

First, a maze is represented as a rectangular array of cells. Each cells is square, and has a wall on each side, and each wall has a door. When the algorithm begins, all of the doors are closed. The algorithm proceeds by judiciously opening doors into neighboring cells until all of the cells are reachable. A cell with all of its doors still closed is said to be “free”. Here’s the algorithm:

  • First, create a maze in which all of the doors are closed.
  • Pick a cell randomly, and add it to the list of growth candidates. (It will be the only entry.)
  • While there is at least one cell in the list of growth candidates,
    • Take a cell, C, from the list of candidates.
    • Find any free cells adjacent to C (north, south, east, or west), and pick one randomly. Call it F. If there are none, continue with the next candidate cell.
    • Let D be the direction from C to F.
    • Randomly pick a number N, from 1 to 4.
    • Beginning at cell C, drive in direction D, opening doors into free cells, until you’ve reached the Nth room, or the edge of the map, or a cell that’s not free.
    • If there are still free cells left adjacent to C, add it to the list of candidates.
    • Add the last cell to the list of candidates.
  • When no candidates remain, all cells are connected, and the maze is complete.

There are a number of things you can change about this. In particular, you can change how you pick the next candidate: the first entry, the second entry, a random entry, and so forth. Different choices will result in different looking mazes. Second, you can vary the number of steps to drive while opening cells. In the maze shown above, you drive up to four cells, random chosen from 1 to 4. Again, different numbers of cells make a difference. For example, suppose that instead of choosing a number from 1 to 4, I simply always choose 4:

Bigmaze2

As you’ll note, it looks quite a bit different.

  • By karrde, November 10, 2012 @ 9:16 am

    I had kind of figured that the generator worked from some sort of list of points, and some way of identifying connections…

    I was mostly curious because I’ve seen a screensaver which randomly generates mazes with a single entry and single exit, then attempts to iteratively find a path through it.

  • By Mark Lambert, November 13, 2012 @ 5:39 am

    Thanks, Will. Solved it in 15 seconds.

Other Links to this Post

WordPress Themes