Well, to make a long story short, this process continues until we've been in each and every room in the grid.  We will need to keep track of how many rooms have been visited, so that we know when we are done.  Once we've achieved that, the maze is close to done.  But close only counts in a game of horseshoes, so they say.

Finishing the job

The only thing remaining is opening an entrance and an exit.   It turns out, that's very easy.  Just pick any two exterior walls and break them down.  It always works and you will always have exactly one path between any two, if you've followed the rules carefully.

How's that for simple to do?  It doesn't get much simpler.

But how do you know there is one and only one solution?  Well, you'll notice that we never break through a wall into a room we've already been to.   This keeps us from creating any loops or cycles that provide more than one way to get from one place to another place.  Thus, there is only one path from any particular spot to any other particular spot.  This is a characteristic of the generated maze.  And it is why you can pick any two exterior walls and be assured that there is only one path no matter which two you pick.

In addition, all paths are connected because we always restart a new branch path from somewhere along the path we've already taken.  So branches are never allowed to exist, unconnected.  And it is always possible to get from anywhere on one branch to anywhere on another branch.

You might instead just imagine laying all those branches flat out on a sheet of paper, instead of all coiled up inside that grid.  I think you'll see what I mean.  You can always pick any spot on one branch of the tree and find one and only one path to any other branch on the tree.  Now, it's easy to see why picking any point along any one branch and picking any point along another branch (or the same one, but that's not as interesting) means that there can only be one way to go between them.

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