Even if we are agreed on the basic framework for a maze, some questions remain.

Where to start?

How do we write a program to generate something like this with a computer?  How do we guarantee only one solution, with one entrance and one exit to the maze?   Do we just grab a blank sheet of paper and start drawing lines?   Should we start with the enclosed rectangle and then erase an entrance hole and an exit hole and go on from there?  What method do we use?

Well, there are several answers and no one right one.

I will discuss the one I invented for myself, in 1974.  I don't know if others developed it, but it is so obvious that it has probably been reinvented thousands of times.   Frankly, I haven't investigated other methods since then since this has never been a professional interest of mine, just one for fun.  But I do know that there are a number of maze programs out there and I'd bet that there are several different approaches taken by them.

I'll describe the approach I developed.

Start out with a grid, like this one:

The above grid, in fact, is exactly what my program started out with before it generated the finished maze shown earlier.  All of the walls are in place and there is no path anywhere.  The easy part of this is that turning this into a maze is much like kicking down walls, but with a few special rules.

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