There are several ways to go about generating a maze from a grid. We would like to generate mazes with the following two properties:
This is very similar to the depth first search algorithm you used to search the maze. The version included in your code is an iterative version; below is the recursive version.
Generate( Maze m )
Choose random cell to start at and initialize stack
Call DFS( start , stack )
DFS( MazeCell current, Stack stack )
Choose a random neighbor of current that has all its walls up
If there is no neighbor of current with all its walls up
Pop a cell off of the stack and call DFS( popped cell, stack )
Else
Knock down wall between current and neighbor
Push current onto the stack
call DFS( neighbor cell, stack )
Generate( Maze m )
While (# Walls Down < Total # Cells - 1)
Choose random cell current
Choose random neighbor of current that has a wall up between it and current
If such a neighbor exists
Find the labels of current and neighbor
If they are different, union them, knock down the wall, and add to # Walls Down
Note that the condition under which a neighbor is chosen is different than the condition in depth first search. In DFS we choose a neighbor with all of its walls up (thus guaranteed to be disconnected); in Kruskal we just look for a neighbor with a wall up between it and the current cell. Union/find takes care of the rest.
Generate( Maze m )
Choose a random cell, mark it visited, and add it to the list
While there are cells on the list
Pick a cell off the list
Add its neighbors to the list
Knock down a wall between it and a neighbor
Mark that cell visited