The maze shown on the right has been generated by the

Table of contents |

2 Some other algorithm 3 Kruskal's algorithm 4 Small-memory algorithm 5 External links |

- 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.
- Start at a particular cell and call it the "exit."
- Mark the current cell as visited, and get a list of its neighbors. For each neighbor, starting with a randomly selected neighbor:
- 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 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.

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.

Choose between using a cell list or a wall list

- 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.
- 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.
- While there are cells/walls in the list:
- Pick a random cell/wall from the list, and remove it from the list.
- 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:
- Break down the wall.
- Mark the cell as part of the maze.
- Add the neighbouring cells or walls of the cell to the cell/wall list.

- 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.
- For each wall that is not a part of the border, in some random order:
- See if the cells on each side of the current wall have the same number, and if their numbers are different:
- Remove the current wall.
- 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.

- See if the cells on each side of the current wall have the same number, and if their numbers are different:

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.

- Kruskal's and Prim's algorithms illustrated by a Java applet, Hilbert and Moore's mazes
- Making Mephistophelean Mazes, 1995 webpage with source code
- techniques and an excellent Java applet
- Think Labyrinth: Maze algortithms (scroll down page to maze creation algorithms section)