Maze generation algorithms

Two common maze generation techniques, see http://www.mazeworks.com/mazegen/ for more techniques and an excellent Java applet which demonstrates some of these.

Depth first search:

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

1. Start at a particular cell.

1. Mark the current cell as visited, and get a list of its neighbors. For each neighbor:

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

Kruskal's algorithm:

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

1. For each wall in some random order:

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

1. 1. 1. Remove the current wall.

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