Maze generation

[Scott Hess]

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.

A nice solution I found to this is the following algorithm (adapted from
a particularily ugly BASIC program . . .):

Your maze is made up of a bunch of cells in a 2d array.  Each looks
something like:

O?
?X

Where O is open, ? are uncertain, and X is a wall.  So, you need two
bits per cell to represent this.

To start out, set all the cells to be closed (both ? are X).
Pick a random cell (this can be anywhere, just choose somewhere).
loop
  From the current cell, do a random walk.  This means, pick a random
  direction.  Look in that direction to see if you can move there.
  If so, open a path to there (either in your cell [right/down],
  or the appropriate neighbor [up/left]).
  Assume an implicit wall on the right hand side.
until you run into a wall.

Now, you need to find a new place to start.  So, what you do is
begin scanning the array in some fashion (say, left to right, top
to bottom - reading fashion) for  closed cells.  Once you find one,
open a path to a neighbor, and then random walk . . .

Do this over and over until all cells are accounted for (as found
by running over the starting scan block again).

While this isn't the most complex solution, it generated very acceptable
mazes for my purposes (I was to write a maze-solver.  What good's
a solver without a generator :-].  To add to the fun, it was in
text mode on a PC, so I wrote a virtual window for it . . . :-)
--
scott hess                      scott at gac.edu
Independent NeXT Developer	GAC Undergrad
<I still speak for nobody>
"Tried anarchy, once.  Found it had too many constraints . . ."
"Buy `Sweat 'n wit '2 Live Crew'`, a new weight loss program by
Richard Simmons . . ."