Your exact design is your business, of course.  But it's nice to think ahead a little before settling down to write some code.

Some considerations

displaying the maze

I haven't covered the methods for drawing the maze, here. And I'm not going to. If you want to see how that's done and cannot work it out for yourself, feel free to download the sample code and see how I did it.

output device

We might want to output the maze to an HP Laserjet printer, the PC screen in text mode, the PC screen in graphics mode, a BMP file, etc. In the worked examples, I generate two different outputs: one in the text-mode format because it's a quick and easy way to verify that the rest of the program is working, and one for the HP Laserjet to show how to deal with slightly more complex requirements.

output statements

To display the maze, we need to know if should be displayed on the screen, printed, or written to a file. In QB, except for displaying the maze in graphics mode on the screen, this is easily handled by just using the file I/O style of PRINT. The user can specify the filename of SCRN: for the screen, LPT1: for the first printer, or a regular file name, too. That much flexibility should be plenty.

displaying the maze on a laserjet

HP Laserjets are really pretty nice to use, but they do add a slight complexity to our program if we really want to make the application nice to use.

You've got two general approaches to use here. The first is to simply stretch a maze to always fit the entire page of paper. Doing this means exactly one maze per page. They will look very nice and professional, but for relatively simply mazes your pathways in the maze will be oversized. The second is to allow several mazes to be generated and placed onto the page before ejecting it. This complicates the user interface somewhat. But it has its advantages.

the path list

For really large mazes, the path list can get pretty darned big before it gets small again. This is because the maze algorithm just spins away for a while, blasting through walls and adding these rooms to the path list. It's not uncommon for the number of entries in that list to get close to the total number of rooms in the maze, itself. And for a really big maze, this means a really big list.

For the versions of this program that actually support very big mazes (up to say a half-million rooms), this path list is almost impossibly big. We just can't get BASIC to give us that much room in a single array. So we need to figure out another strategy.

The idea I've tried is to use yet another one of those bit-packed arrays, just like the wall and visitation status arrays, to hold a bit which indicates whether or not a particular room is worth checking. In this case, I randomly select a place to start searching, and then search this array 16 rooms at a time until I find a block of 16 that contains at least one room to try. Then I try it. If it fails, it gets removed from this array and I pick another starting point at random. The time it takes isn't predictable, but it works and saves a lot of space.

dividing and conquering

It's not uncommon that you find you can divide up a larger problem into smaller ones to solve, solve those and then to aggregate those solutions to solve the larger one. Generating a large maze can be solved this way, as well. Can you think of how?

We already know that there is one guaranteed path between any two exterior openings in any maze we complete. What if we took a large maze grid and simply solved only one corner of it? We could then pick any two exits from that corner area, internal to the larger maze area, and we'd know there was only one path to connect them.

So, what we could do is first imagine that the larger maze is sub-divided into a coarser grid of much fewer rooms, solve that maze first, then treat each room of that coarser grid as a sub-section of the larger maze to solve. Solve each of those individually and follow the guiding influence of the coarser maze to tell us how to connect up the sections.

A disadvantage of this technique is that the resulting maze will have obvious, hard regions in it that a player will recognize and take advantage of, in solving it. But how might one fix this problem? Think about it.

does it have to be a rectangle?

What about different basic shapes?

Consider making the original grid in the form of concentric circles, instead of rectilinear, and using radii to divide it all up into rooms. Perhaps, you'd need to leave an inner chamber to keep the rooms from getting too small as you neared the middle. But wouldn't the same logic at generating a maze apply here?

What kinds of other shapes do you think might work, too?

some further considerations

Do we want to make this a kind of batch program, accepting specifications from a file for example? Do we want to require user interaction, one maze at a time?

In QB, we have access to the COMMAND$ value. This allows us to examine what was typed on the command line and change the way we do things, depending on what we see there. Perhaps we could look at COMMAND$ and see if a filename was given. If so, we'd read the file and perform the operations that were saved there during a different session with the program. If not, we'd let the user operate the program from the keyboard and screen and create a new session log of what was done.

Last updated: Wednesday, July 06, 2005 21:05