If you've never tried it before, generating a maze can seem
easy enough in concept yet quite hard to grapple with, once
you try to work out the details of it.
It turns out that it really isn't all the difficult, once
you've done it and made it work.
I'm not going to write this for novice programmers, though.
I think you should be fairly comfortable with programming in
QB, before tackling this project.
But you don't have to be some expert, either.
It's just a good idea that you understand most of the syntax
and semantics of QB, because I'm going to focus on the maze
application here and not on the language we're using.
I'd recommend that you consider yourself a moderate programmer
or, at least, a self-learner.
Building a Maze
How do you build a maze?
Well, if you'll excuse the text-only sample, let's start out by
taking a look at one:
+ +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | |
+ + + + +--+--+ + + +--+ + + +--+--+--+ + +--+ +
| | | | | | | | | | | | |
+--+ + +--+ + +--+--+ + +--+--+--+ + +--+--+--+--+ +
| | | | | | | | |
+ + +--+--+--+--+--+--+--+ +--+--+--+--+--+ + + +--+--+
| | | | | | | |
+ +--+--+--+ +--+--+--+ +--+--+ + +--+ +--+ + +--+ +
| | | | | | | | |
+--+--+ + +--+--+--+ +--+--+--+--+--+ + + +--+--+ +--+
| | | | | | | |
+ +--+--+ + + + +--+--+ + +--+--+--+ +--+--+--+--+ +
| | | | | | | | | | |
+--+--+ +--+ +--+--+--+ + +--+ + + +--+--+ + +--+ +
| | | | | | | | |
+ +--+--+ +--+ +--+--+ +--+--+--+--+ +--+--+--+--+--+ +
| | | | | | | | | |
+ + + +--+ +--+--+ + +--+ +--+ +--+ + +--+ +--+ +
| | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +
Next, you might notice that it's really kind of like a grid.
If you count them, you'll see that this maze has 20 columns
and 10 rows.
What about the solutions to the maze?
Is there one?
More than one?
Of course, I'm sure we hope there is exactly one and no more.
In this case, I think you'll agree that the maze meets this
essential requirement.
where to start
How do we draw 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 basic 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 ways and no one right one.
But the one I like better starts out with a grid, like this one:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
getting started
We start out by dropping into any grid location, at random if
we want to.
It doesn't really matter.
Then we simply break down any one of the walls, except that
we don't break down walls that lead to rooms we've already
been to.
When we start out, this means any wall can be broken.
Once we break down one of the walls, we simply walk into the
newly opened room.
Then choose any one of the remaining walls to break down, once
again being aware not to break down a wall that leads to a room
we've been in.
Here's an example of how the original maze may have started:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | |x--> |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
getting there is part of the fun
This process continues until we cannot break down any more
walls, because we are surrounded by rooms we've already
visited and we are now trapped.
Here's how it might have looked in the original maze, at the
moment we first trapped ourselves:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +--+ +
| | | | | | | | | | | | | | | | | | y| |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +
| | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +--+--+
| | | | | | | | | | | | | | | | |x |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +--+ + +--+ +
| | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +--+--+--+ +--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
a new lease on life
So now what?
Well, we just pick any place along any path we've already been
to and start from there, once again.
Just pick anywhere we've been to, already.
Here's the results of this strategy, after we get stuck again:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +--+ +
| | | | | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +
| | | | | | | | | | | | | | | | | |
+ + +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ +--+--+
| | | | | | | | | | <--a | | |
+ +--+--+--+ +--+--+--+--+--+--+--+ +--+ +--+ + +--+ +
| | | | | | | | | | | |
+--+--+--+ +--+--+--+ +--+--+--+--+--+ + +--+--+--+ +--+
| | | | | | | | | | | |
+--+--+--+ + + + +--+--+--+ +--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+ +--+ +--+--+--+--+--+--+ + + +--+--+--+--+--+--+
| | | | | | | | | | | | | |
+ +--+--+ +--+ +--+--+ +--+--+--+--+ +--+--+--+--+--+--+
| | | | | | | | | | | | | |
+ + + +--+ +--+--+ + +--+ +--+ +--+ +--+--+--+--+--+
| | -->b| | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Heck, it's already starting to look a bit like a maze!
finishing the job
Well, to make a long story short, this process continues
until we've been in each and every room in the grid.
Once we've achieved that, the maze is nearly done.
The only thing remaining to do is to open an entrance and
an exit.
It turns out, that's easy.
Just pick any two exterior walls and break them down.
It always works and you will always have exactly one path
between them, if yoy've followed these rules carefully.
How's that for simple to do?
It doesn't get much simpler.
guaranteed right
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 place to place.
Also, 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 unconnected.
And it is always possible to get from anywhere on one branch
to anywhere on another branch.
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.
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.
Programming a Maze
the basics
Take a close look at the original grid.
If we set up four walls for each room, we'd have duplicate walls
everywhere.
That's because the north wall of the south room and the south
wall of the north room would both be for the same intervening
wall between them.
That duplication is a pain.
The solution is to set up each room with, say, a west wall and a
south wall (or a left wall and a bottom wall, if you prefer.)
That's it.
That way, the south wall of the north room is the only wall
sitting between the north room and the room just south of it.
The only problem with that scheme is that we don't have walls for
the north-most and the east-most walls of the maze, because there
aren't any rooms out there to provide these walls.
Of course, we could always make the grid one size larger in each
direction to put rooms out there.
We'll be returning to this last question in a bit.
It turns out that there are some considerations, one way or another.
Either way we do it, we're going to need an array of west walls,
an array of south walls, and if you haven't noticed, an array of
markers indicating whether or not we've been to the room.
(Kind of like leaving bread crumbs along out path, eh?)
We only need one bit per wall or marker, since we only need to
know YES/NO information about each.
It would be somewhat easier, if we just used an entire INTEGER
for the purpose.
But after some calculations, you'll see why we should go to the
trouble.
how much is enough?
Let's take a crack at just how many rooms in our grid is enough.
Let's assume we are going to draw mazes on an HP LaserJet printer.
These printers provide a printable area of about 8" by 10.5",
leaving a quarter inch or so at all the margins of the 8.5"
by 11" page.
With 300 dots per inch of resolution, we should be able to make
fairly nice, fine lines for our mazes.
But how detailed would we like to go?
Would one millimeter spacing be small enough?
Would it be too small?
Let's start out with the millimeter spacing specification and see
where that takes us.
Once we see where we land, we can make a somewhat better judgement
about where next to go.
To compute the worst case number of rooms we have to handle, we'll
assume that a single maze will cover the entire printed page and
that it will use one millimeter wide paths, roughly.
Given that, our calculation simply involves dividing the total
printable area on the printer page by the area of one room.
That will tell us the number of rooms we must handle.
(8" * 10.5") / (1 mm * 1 mm) = (8 * 25.4) * (10.5 * 25.4) = 54193.44
So we'd need to handle over 54,000 rooms.
That's a lot, if we remember that we need to provide information on
west and south walls and whether or not they've been visited.
Since BASIC doesn't support making INTEGER arrays anywhere near that
size (and we'd need at least three arrays), we can either reduce our
requirements to the about 32500 or so that we can count on and see
where that leaves us or else we can think about what it means to just
use a single bit, rather than an entire INTEGER for each array.
Frankly, I'm going to go for the gusto on this one.
But let's look at reducing the requirements, first.
Assume we can only create an INTEGER array of say 32,500 elements.
We'll plan on using an entire INTEGER for each of thing we need to
keep track of, as well, such as the west and south walls and our
visitation status -- for a total of three such arrays.
32500 = (8" * 10.5") / (X mm * X mm)
thus, X = SQRT(54193.44 / 32500) = (about) 1.29 mm
Well, that's not too bad at all!
We can generate mazes with about 19 or so rooms per inch, which is
fairly good resolution.
So if this is fine for you, we could easily proceed along those
lines and feel quite happy with the results.
Those mazes would be very complex, being better than a grid of
150 by 200 per printed page.
But let's see where we could go, with a little more effort.
If we can pack 16 bits per INTEGER value, that would provide 16
times as many rooms wouldn't it?
16 * 32500 = (8" * 10.5") / (X mm * X mm)
or, X = SQRT(54193.44 / (32500 * 16)) = (about) 1.29 mm / 4 = .323 mm
Now, we are talking about mazes that are better than 600 by 800, in
size.
That's serious stuff!
Is a third of a millimeter crazy?
Perhaps.
But that's (.323 / 25.4) * 300 = 3.8 dots wide:
let's call it 4 dots.
We can plot one dot for a wall and leave 3 more for an opening.
A human should be able to see that -- we hope!
Maybe pressing the limits isn't your style.
But it's where we are going.
So sit back and enjoy it.
summary
We're going to support grids on the HP LaserJet printer, with room
sizes such that they only span 4 printer dots in any direction.
Let's calculate backwards, assuming we can pack 16 bits per INTEGER
in BASIC, and see what the size of our arrays should be.
We take the total dot area of the printer and divide it by the
dot area of our minimum sized room.
Then divide again by the number of bits we can pack into an INTEGER
array.
That should get us the number of array elements, worst case, that
we will need available to handle our west walls.
A similar requirement, then, for the south walls and the visitation
status.
29532 >= (300 * 8) * (300 * 10.5) / (4 * 4) / 16
So, a rounded 30,000 INTEGER elements would more than cover our needs
for a bit array.
Using three of these, one for west, one for south, and one for the
visitation status, means a total of three 30,000 element arrays
would cover the entire printer page with almost a half-million rooms!
That's one killer maze, eh?
Maze Algorithm
I hope I've conviced you this is a no-holds-barred maze generation
program.
Now, it's time to work out the details of an algorithm for the maze.
Something I neglected to tell you about, thus far, is that we'll need
some way to restart the maze generation, after reaching a dead end.
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 pick up at that point.
But what if not?
If not, we have to pick another place, at random.
Early in the maze generation, our odds of picking a location we've
already been to isn't good.
But if we do find one, the odds that we can forge a new path from
there is pretty good.
Later in the maze generation, our odds of picking a location we've
been to is pretty good.
But the odds of being able to forge a new path from there gets
to be really bad.
Either way you look at it, there's a problem.
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,
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.)
So, here's the algorithm, in my form of pidgeon BASIC:
Empty the path list.
Set up the west walls.
Set up the south walls.
Set up the visitation status.
Set up a count of rooms that remain to be visited.
Pick a starting location in the maze, at random.
DO WHILE (more rooms to visit),
Decrement the count of rooms to visit.
Mark the current room as visited.
Count the number of valid exits from this room.
DO WHILE (no exits from this room),
Pick an entry from the path list, at random.
Remove that entry from the path list.
Count the number of valid exits from this new room.
LOOP
IF (count of exits > 1) THEN
Add this room to the path list.
END IF
Select one of the available exits, at random.
Break the intervening wall in that selected direction.
Move into the new room in that direction.
LOOP
Doesn't look that bad, does it?
Once this is done, all we need to do is print out the maze.
You can take your own crack at writing this kind of program,
if you want.
Or you can download my versions and look at them, instead.
But they conform to this general approach.
Some General Issues
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.