Download Game! Currently 93 players and visitors. Last logged in:KanisCorpGingerYeast

Library: Maze Algorithms

Books

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