Re: [FWP] Maze

[Ariel Scolnicov <ariels@compugen.co.il>]

merlyn@stonehenge.com (Randal L. Schwartz) writes:

> And a much simpler one (if I can get it from memory this early
> in the morning):
> 
> Start with all walls filled in, all cells "unmarked" except one.
> 
> Pick a marked cell at random, pick a wall at random that leads to an
> unmarked cell, knock down the wall, mark the cell.
> 
> Repeat until you mark all the cells.
> 
> Then there's one and only one way from any cell to any other cell.
> Create arbitrary entrance and exit, and you're done!

This picks *a* spanning tree of your original grid.  A "spanning tree" 
is a set of walls such that you *can* get from every cell to every
other cell, in *exactly* one way.

But the distribution of the spanning tree is not uniform -- not all
spanning trees have the same probability of being chosen.

If this is important to you (and it does seem to yield more aesthetic
mazes), look for Wilson's algorithm for finding a uniform spanning
tree.  It's reasonably easy to code, has almost-bearable performance,
and is excruciatingly elegant.  I might code it up over the weekend &
post, if nobody beats me to it.

Note also that *real* mazes will typically contain a cycle, so they're 
not really trees.

-- 
Ariel Scolnicov        |"GCAAGAATTGAACTGTAG"            | ariels@compugen.co.il
Compugen Ltd.          |Tel: +972-2-5713025 (Jerusalem)	\ We recycle all our Hz
72 Pinhas Rosen St.    |Tel: +972-3-7658117 (Main office)`---------------------
Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555    http://3w.compugen.co.il/~ariels

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe