We cannot continue with the simple algorithm we've been using.   That's for sure.  So now what?

A new lease...

Well, the current room has no valid exits.  Perhaps if we selected another room at random and restarted the process?  Actually, that wouldn't work (well, it wouldn't without some additional complications -- I'll leave that thought as an exercise for you.)  It wouldn't, because the new path we'd create wouldn't have any connection at all to the path we just created.  That would suggest, at a minimum, that our resulting maze might not be solvable.  And in fact, it wouldn't be.

So, the idea is to simply go backwards into our path to anywhere else, even at random, and restart from there.  Of course, you cannot then select any of the directions out of that room that have already been taken.  A new direction will have to be found into an unentered room.  Keep in mind that the newly selected restarting point might have no legal exits, either.  Another try may be needed starting at yet another room.

In the following, I've placed the marker a at the location along the old path where I decided to restart the original algorithm.  In this case, a new wall was selected and the path branched from there.  Here's the results of this strategy, after we get stuck again (marker b shows where we finally got trapped, again):

We started at marker a, which is one of the rooms we'd already been to, and then continued on until arriving at marker b.  As you can see, this time we got quite a distance before getting stuck once again.

It's already starting to look a bit like a maze!

Last updated: Tuesday, July 06, 2004 19:07