There's something we've missed talking about in much detail -- we'll need some way to restart the maze generation after reaching a dead end.  How exactly?

Keeping track of the path

As I hinted earlier, one way of handling this is to simply pick anywhere in the maze, at random, and check to see if we've been there before.  If so, we can pick up at that point.  But what if not?  If not, we have to pick another place, at random.

Early on in the maze generation, our odds of randomly picking a location we've already been to aren't good.  We might have to try over and over again to find a new branching point.  But the flip side is that if we do happen to get lucky enough to actually find one, the odds that we can forge a new path from there are pretty good.

Later on in the maze generation, our odds of randomly picking a location we've been to are pretty good.  But the flip side of that is then the odds of being able to forge a new path from there aren't so good anymore.  We might have to try over and over again in order to find a branching point where there is an adjacent, previously unused room from which to continue our maze.

Either way you look at it, there's a problem.  We may have to randomly choose and choose again, until we hit the right spot.  This leaves us completely at the mercy of the random number generator.  And that can be a very bad thing.

A solution is to keep a list of places we've been to in a 'path list.'  We just add our visited locations into this list as we visit them and so long as there is more than one exit (there's no point adding them if there is only one, because we are going to take that direction and the next time there won't be any exits.)

When we need to select a new branching point, we can go back to this list and randomly pick one of them.  We can then examine that selection to see if there are any exits from it.  If there are none, we remove the room from the list and try again.  If there is only one exit, we remove the room from the list but accept the room and use the only exit available.  If there is more than one exit, we leave the room on the list but take one of the exits at random and continue.

Because of that design, even with a lousy random number generator, you can be assured of actually completing a maze.  Even if the random number generator only provided a constant and didn't otherwise work at all, it would still work.   This is a good thing.

Last updated: Thursday, June 17, 2004 19:26