With those thoughts aside, it's time to take a peek at the end product to see what that shows us.
Looking at some details
Let's first 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? A millimeter wide path is pretty small, but let's start out with that 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 QBASIC doesn't support making INTEGER arrays anywhere near that size (and we'd need at least three of those 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. It's easy to see why you might want to go to the trouble to use a single bit instead of an entire INTEGER, eh?
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 still 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 in programming. 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 so. It sure seems like it. But that's (.323 / 25.4) * 300 = 3.8 dots wide: let's call it 4 HP Laserjet resolvable 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!
From the above calculations, though, you can see that very decent mazes are possible without having to go to great extremes. You can use whole INTEGER values without having to make serious sacrifices in the quality of your mazes.
Last updated: Sunday, July 31, 2005 02:05