Maze generation

[Steve Alter]

In article <6WH^XJ_ at rpi.edu> gordon at itsgw.rpi.edu (Gordon E. Greene) writes:
} 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....
}
} gordon at rpi.edu    USERF023 at RPITSMTS   USERF023 at mts.rpi.edu

The right-hand-on-the-wall algorithm, in its simple form, won't be able
to solve all mazes with loops in them (i.e. a maze that is not uniquely
connected) but a simple modification to the algorithm can fix that.
Just remember every room you've visited, and as you're walking around,
if you see that you're about to step into an already visited room, then
just pretend that there's a wall in front of you and continue to apply
the right-hand rule.  After that, you can forget about that piece of
phantom wall, because the rooms on both sides of it have been visited.

Related topic:

I remember a program that generates a 2-level maze, in which passages
can cross over each other, and to some extend, two passages can even
run in vertical parallel because the upper one is painted narrower than
the lower.  The generator paints such a maze by growing all branches
simultaneously, and the graphic effect is really strange!  Rather than
solving it, the program let's you mouse through it with no help.
Anybody else heard of such a sadistic piece of code?

-- 
Steve Alter        <alter at ttidca.tti.com>
{philabs,psivax,pyramid,quad1,rdlvax,retix,rutgers}!ttidca!alter
Citicorp/TTI, Santa Monica CA  (213) 450-9111 x2541