Maze generation

[Peter Phillips]

In article <1215 at syacus.acus.oz> martins at syacus.acus.oz (Martin Schwenke) writes:
>
>I am interested in software or algorithms for generating mazes with
>unique solutions. I am also, but less, interested in maze solving
>algorithms, and programs.

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.

This method has a few advantages.  First, you aren't stuck
with using a grid.  You could use this to make a maze out of a map
of countries or some other familiar graph. Second, you can create
different effects by varying how you choose your weights without
worrying about screwing up the algorithm. Third, it runs in time
close to order n. (n = number of nodes).

I wrote some code to do this once as an application of Kruskal's
minimal spanning tree algorithm (a rather nifty little algorithm).
I've still got code to do this in C lying around somewhere.

Hmm, you could work this in reverse.  Create a program which takes
an arbitrary tree and turns it into a grid maze.  You could use this
to turn a UNIX file system tree into a maze, as if it isn't already. :-)

--
Peter Phillips, pphillip at cs.ubc.ca | "It's worse than that ... He has
{alberta,uunet}!ubc-cs!pphillip    | no brain." -- McCoy, "Spock's Brain"