Maze generation

[Gordon E. Greene]

In article <1990Dec15.122555.20420 at cs.ubc.ca> pphillip at cs.ubc.ca (Peter Phillips) writes:
>One method is to think of a maze as a spanning tree for a connected
>graph.  Take any graph, assign random weights to each arc.  Apply some
>minimal spanning tree algorithm.  A drawing of the resulting tree will
>be maze.  It helps if you know of some way of embedding the graph in a
>plane.  All this works out simply if your starting graph is a grid.

Even more general than this is to observe that any maze (in a plane) is a
conected planar graph.  If one started the algorithm with a random connected 
planar graph and then just drew it, one would have a maze.  This method can 
give mazes with loop corridors in them.  The tree algorithms give only simple 
mazes (right hand on the wall to get out).  A more general planar graph can 
give mazes which the trailing hand method won't solve.  In addition, if one 
pays a lot of attention to the algorithm for drawing the graph, corridors 
could be curved, join at rooms, whatever.
 
To actually draw a planar graph, one could sort the graph into polygons.
One could then determine which edges lie inside which polygons, and then
deform the polygons to allow for rooms, curved hallways, and so on.

-- 
--------- You can never have too many ferrets. -----------
gordon at rpi.edu    USERF023 at RPITSMTS   USERF023 at mts.rpi.edu