Author: Erdos

Date:Jan 17 1999

An Efficient Maze-Generating Algorithm Based On Kruiskal's Algorithm for Minimum Spanning Trees This maze algorithm is not the fastet available, but it is one of the most flexible and "well-behaved" algorithms available. A maze, for the purposes of this algorithm, is a selection of some set of edges from a graph. The selection is done so that every node is connected by at least one edge, and so that the graph contains no cycles. In practical terms, the rooms are "nodes" and the doors are "edges". The maze produced includes all the given rooms, and there is a unique shortest path from each room to any other room. (If cycles are desired, they can be added later, of course.) No restrictions are placed on the type of graph started with. You may initialize the algorithm with a completely connected graph, a square lattice of rooms, a 4-d grid, a hexagonal grid, or anything else. The algorithm proceeds by randomly connecting segments of the maze into larger and larger sets, until the entire maze is connected. An efficient implementation of this requires a fast "union-find" algorithm for disjoint sets. This data structure must provide two operations: unioning together two sets, and determining whether two elements are in the same set. These can be done in (amortized) constant time, as described in the Appendix. The Algorithm Initialize the union-find structures so that every cell (room) is in its own equivalence class (set). Create a set containing all the interior walls of the maze (that is, the edges of the graph the maze is build from.) Set COUNT, the number of components, to the number of rooms. Then, while COUNT > 1, repeat the following: -- Remove a wall from the set of walls at random -- If the two cells connected by this wall are already connected (i.e., in the same equivalence class, as determined by the FIND operation), then do nothing. -- Otherwise, connect the two cells (with a door, passageway, etc.) and place them in the same equivalence class with the UNION operation. Decrease COUNT by 1. Appendix: Union-Find on Disjoint Sets An efficient union-find algorithm represents each set by some "distinguished member". Every element has a pointer associated with it; following this pointer will lead to the distinguished member of the set that the element is in. (Remember, these are disjoint sets, so an elemment belongs to at most one set.) Initially, every element points to itself as the only member of a singleton set. The UNION operation changes the pointer of the distinguished element of one set to point to the distinguished element of another set. The FIND operation compares whether the distinguished element of two sets is the same. Implementing just the strategy above would be inefficient, so two additional operations take place. First, keeping a "depth" in the nodes allows UNION to be done in a balanced way (see an algorithms textbook for details if you can't work this out youself.) Second, and more important, when a FIND operation is done, the algorithm should set the pointers of all elements traversed directly to the distinguished member. This prevents lengthy searches for the distinguished member to occur more than once. References The Maze FAQ, http://www.mazeworks.com/maze_faq

Books