Main Page | See live article | Alphabetical index

Maze generation algorithm

There are a number of different maze generation algorithms, that is, automated methods for the creation of mazes.

The maze shown on the right has been generated by the Some other algorithm maze generation algorithm, with a cell list. For the source code for a Java applet that was responsible, click on the maze.

Table of contents
1 Depth first search
2 Some other algorithm
3 Kruskal's algorithm
4 Small-memory algorithm
5 External links

Depth first search

  1. Start with an array (rectangular or hexagonal) of the proper width and height with all the cells marked as unvisited, and all walls up between the cells. If you want to exclude some cells from the maze (for example, to make a non-rectangular maze), mark these cells as visited.
  2. Start at a particular cell and call it the "exit."
  3. Mark the current cell as visited, and get a list of its neighbors. For each neighbor, starting with a randomly selected neighbor:
    1. If that neighbor hasn't been visited, remove the wall between this cell and that neighbor, and then recurse to step 3 with that neighbor as the current cell.

If your computer architecture has a small stack and cannot effectively use recursion, you can store the backtracking information in the maze itself; this also provides a quick way to display a solution, by starting at any given point and backtracking to the exit.

Mazes generated with a depth-first search have a low branching factor and contain many long corridors, which makes depth-first a good algorithm for generating mazes in video games.

In mazes generated by that algorithm, it will typically be relatively easy to find the way to the square that was first picked at the beginning of the algorithm, since most paths lead to or from there, but hard to find the way out.

Some other algorithm

Choose between using a cell list or a wall list

  1. Start with an array of the proper width and height, with all walls up between the cells. Have a separate cell list or a separate wall list, which starts off empty.
  2. Pick a cell, mark it as part of the maze. Add the neighbours of the cell to the cell list, or the walls of the cell to the wall list.
  3. While there are cells/walls in the list:
    1. Pick a random cell/wall from the list, and remove it from the list.
    2. If using a cell list, pick a wall between the cell and another cell already part of the maze. If using a wall list, then if the cell on one side of the wall is not marked as part of the maze:
      1. Break down the wall.
      2. Mark the cell as part of the maze.
      3. Add the neighbouring cells or walls of the cell to the cell/wall list.

It will usually be relatively easy to find the way to the starting cell, but hard to find the way anywhere else.

Kruskal's algorithm

  1. Start with an array (rectangular or hexagonal) of the proper width and height, with all the cells given a different number, and all walls up between the cells.
  2. For each wall that is not a part of the border, in some random order:
    1. See if the cells on each side of the current wall have the same number, and if their numbers are different:
      1. Remove the current wall.
      2. Then find all the cells in the array with the higher of the two cell numbers and replace them with the lower of the two cell numbers.

At any point in this algorithm, the number in a cell uniquely identifies the region to which it belongs. However, note that a naïve implementation of this algorithm takes O(n2) time because of the repeated flood filling of areas with the higher number.

The time can be reduced to O(n log n) by flood filling the smallest area with the number of the largest area, instead of looking at which number is largest. This requires remembering the size of the area associated with each number. Similarly, one could use pointers to other cells, forming trees, and when joining areas, point the root of the tree with lowest depth to the root of the other tree, storing the depth of the tree at the root, also in O(n log n) time.

Small-memory algorithm

Other algorithms exist that require only enough memory to store one line of a 2D maze or one plane of a 3D maze; they work by storing which cells in the current line are connected through cells in the previous lines. This algorithm never knocks down a wall between any two cells already connected.

External links