Xref: utzoo comp.sources.wanted:14523 alt.sources.d:1184 rec.games.misc:12870 rec.games.programmer:2709
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!rpi!gordon
From: gordon@itsgw.rpi.edu (Gordon E. Greene)
Newsgroups: aus.games,comp.sources.wanted,alt.sources.d,rec.games.misc,rec.games.programmer
Subject: Re: Maze generation
Keywords: how-to maze generate program wanted
Message-ID: <6WH^XJ_@rpi.edu>
Date: 16 Dec 90 21:38:10 GMT
References: <1215@syacus.acus.oz> <1990Dec15.122555.20420@cs.ubc.ca>
Organization: Rensselaer Polytechnic Institute, Troy NY
Lines: 23
Nntp-Posting-Host: risk.its.rpi.edu

In article <1990Dec15.122555.20420@cs.ubc.ca> pphillip@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@rpi.edu    USERF023@RPITSMTS   USERF023@mts.rpi.edu