[Back to MISC SWAG index]  [Back to Main SWAG index]  [Original]

{
LOU'S MAZE ALGORITHM

We all want to create mazes at some time or other; I devised one effective
maze-generating algorithm.  I will be discussing a rectangular maze, but
it should be possible to use the principles I describe to create mazes of
different shapes.  I will also be discussing mazes with no "islands" in
them or any other features that would make it impossible to walk the
entire maze with one hand against the wall.

First of all, you need to create a two-dimensional array to describe the
maze territory.  Each grid element should, at the very least, contain
a boolean to indicate whether or not there is a wall at that spot.  Your
grid should have *ODD* dimensions, so that you can maintain a wall /
corridor / wall / corridor / wall / etc. pattern.  Now flag the outside
edges of the grid as "walls", and the entire interior as non-walls.

Next, select an entrance and exit to the maze.  The entrance and exit
will be on the edges of the grid, but with *EVEN* coordinates (so they
will open up into a corridor and not a wall).  Flag the entrance and
exit as non-walls.

Now select several spots on the edges of the grid, from which to
start generating the insides of the maze.  All these spots must have
*ODD* coordinates, so that they will not ever grow into corridors.
What we will be doing is growing walls from these "seed points" to
fill the maze.  (Each seed point is a record that should just consist
of an x and y coordinate, indicating a maze location to grow a wall
segment from.)

You will need to set up a large array to accommodate a great number of
seeds: every time you add a wall segment, you add seed points.  By my
guesstimates, the maximum number of seeds you're ever going to need is:
(mazeheight - 3)*(mazewidth - 3) / 2.

Keep executing this loop until you run out of seeds:

  - Randomly select a seed.  Extend the wall in some valid direction
    from this seed point, by turning into walls the grid locations one
    unit and two units away from the seed.  To prevent the maze from
    closing off at any point, DO NOT EXTEND A WALL TO ANY POINT THAT
    IS ALREADY MARKED AS A WALL!  (With this rule, you never close off
    the maze; you simply complicate the path from beginning to end.)

  - Remove this seed.  It's done its job.

  - Add three seed points at this new location.  (The assumption is
    that the wall could grow in three directions from this new point;
    if you want to be more exacting, you can add as many seeds as there
    are directions that the wall could extend from that point.  It
    really doesn't matter much, except for the possibility of running
    out of seed point array elements if you always add 3.)

  - Seed maintenance: go through your list of seeds and eliminate any
    seeds that cannot extend in any valid direction.

Once you are out of seeds, the maze is complete.  You are done.
------------------------------------------------------------------------

As for traversing a maze: you are likely aware of the "right-hand rule"
for walking a maze, by starting at the entrance, keeping your right hand
on the wall at all times, and following your nose.  Sooner or later, you
will get to the exit.  I will suggest how to implement the right-hand
rule.  First, you will always need to keep track of what direction you're
walking.  Now to simulate the right hand on the wall: check the grid
location in the direction just clockwise to the direction you're walking.
In other words, if you're walking to the right, check the downward
direction.  Is there a wall there?  If not, go in that direction.  But if
there is a wall there, keep checking directions going counter-clockwise
until you find a spot that isn't a wall.  (Using the same example, if you
couldn't go down, check right, then up, then left until you find a
non-wall.)  As soon as you find a non-wall, go in that direction.
------------------------------------------------------------------------

There are probably all sorts of ways to solve a maze, but here is the
approach I use.  First of all, you will need to associate another
boolean variable with each maze location, indicating whether or not
you've passed that spot already while trying to solve the maze.  (Think
of leaving a trail of bread crumbs and you have the right idea.)  Set
all your "bread crumbs" to false.  Now start at the beginning of the
maze, and walk the maze via the right-hand rule.  Whenever you move to
a new location, check to see if there's a bread crumb there already.  If
there is not, put one there, *and also in the location you were just at*.
If there is already a bread crumb there, remove it, *and also remove the
bread crumb from the location you were just at*.  When you finally reach
the exit, the only bread crumbs remaining, will comprise the solution.
(All that bit about "the location you were just at", keeps bread crumbs
from appearing improperly at corners and dead ends.)
}

[Back to MISC SWAG index]  [Back to Main SWAG index]  [Original]