Wikipedia: History of Maze generation algorithms

Difference (from prior major revision) (no other diffs)

Changed: 4,6c4,6

# Start with a rectangular array of the proper width and height with all the cells marked as unvisited, and all walls up between the cells.
# Start at a particular cell.
# Mark the current cell as visited, and get a list of its neighbors. For each neighbor:

# 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:

Added: 8a9,13

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.

Changed: 10,11c15,16

# Start with a rectangular array of the proper width and height, with all the cells given a different number, and all walls up between the cells.
# For each wall in some random order:

# 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:

Added: 14a20,26

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

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.

	Revision 2 . . October 4, 2001 3:31 am by Damian Yerrick [added notes on the algorithms and a sketch of a small-memory algorithm; anybody want to flesh it out?]
	Revision 1 . . October 3, 2001 7:53 pm by NickelKnowledge [First cut at propre spelinng of allghoreithmme :-(]