★ APPLICATIONS ★ CREATION GRAPHIQUE ★ MAZE DRAW (YOUR COMPUTER) ★ |
| Maze Draw (Your Computer) | Applications Creation Graphique |
So far we've covered the basic techniques of graphics and some simple Cad procedures, now let Miroslav Kostecki and Paul Vermeer a-maze you . . . WHAT COMES to mind when you think of a maze? Confusion? Tunnels and passages everywhere? Too hard to understand? In fact, we also associate mazes with intelligence It is generally accepted that the greater the intelligence, the faster a path will be found through a maze. Scientists create many mazes for animals of various types to test their reactions and intelligence.
For example, there have been many robot mice specifically designed and produced to find their way to a point in a maze, to advance the mechanical side as well as the intelligence side of robotics Competitions are held every year or so to determine the fastest robot mouse to find its way through a maze The fact is, mazes don't need to be confusing. When you understand what they are, and how to construct them, they become very interesting. To start with, let's examine closely what a maze is. We know it is a complex network of paths or passages designed to puzzle those working through it. A similar system can be represented as a pattern of lines They may range from round to square and include many shapes and sizes. One aspect common to almost all mazes is a connecting path which must be found between the beginning of the maze and the finish. The perfect maze would be a compact, but easy to follow system of paths It would have only one possible path from any point within the system to any other point, but with a path existing for every point. This type of maze may appear impossibly complex to be able to create in reality, but there is a simple technique which produces it. Branching First lets look at a system which already exists and has the above 'one path through' characteristic For this we would just have to look at any tree Notice that from any branch on the tree, to any other branch, there is really only one path. You simply move along the branch to the trunk and from there to the other branch. Look at a tree and try it for yourself, but make sure no one is watching you! This type of branching can now easily be transformed into a simple procedure To demonstrate this concept, simply draw a line on a piece of paper. From this line you then branch off in any direction. If you keep adding branches just anywhere and do not cross them over, you will have produced precisely the same kind of branching as on a tree Notice that these branches are all the same width, the width of the pen, so that it is much harder to find your way from one branch to the next. In replacement of pencil and paper, it is a simple matter to convert this procedure to computer - see Figure I Previously we have used straight lines, since the branches on a tree are usually fairly straight. However, if we use crooked lines instead, our lines will form more of a maze. It then becomes an arduous task to find the correct passage through. Of course, the lines still must not cross or touch other branches. Each branch still touches another only once. On a computer, a maze is usually constructed by first drawing a grid of small boxes over the screen An array is set up to store the state of every edge on the grid Now as the edges are taken away, a passage is constructed along the boxes. Branching is made by forming new passages off the old ones. The computer can check if a passage exists by checking the array which is changed as the passages are constructed. Amazing improvements A major consideration in the construction of mazes is where the beginning of the first branching is going to occur This point would be picked randomly, but far away from the start and end points. The beginning and end should be as far from each other as possible to increase the length and difficulty level of the path. Notice, too, that while a very large maze takes much longer to construct than a small one. it will be much more difficult to traverse The size of the maze is normally limited by the screen resolution and memory capacity, as well as the speed of the computer Instead of using an array, the computer can simply check the state of the screen using a screen test command. This eliminates the need for arrays. Using the screen to test the maze also means that very large, complex mazes can be constructed on a high resolution graphics screen and little memory is being used. Array storage can be very heavy on memory when large, complex mazes are constructed Another big improvement is to do away with the grid system all together and simply construct the maze 'freestyle' This enables a more complex maze to be made in a smaller space. A different checking system though, is obviously needed to scan the screen for other passages already constructed However, with greater complexity comes a problem: the computer will have to work harder to find suitable branching places No need to worry though, this is overcome with the next, most important improvement Many maze generating programs simply sample random spots in the maze to find a branching point which is suitable. This causes huge delays, especially when the maze has nearly filled its allotted space and there are few branching points left. There have been many methods to overcome this and the following one seems as good as any other As the paths are constructed, block by block, the computer stores every point of every path Then when the current branch stops, the programs simply picks a branching point out of the array and either starts from there, if it is legitimate, or eliminates the point out of the array and reduces the number of stored points. When the array runs out, then there are no more possible branches and the computer has completely filled the space. It seems that with this branch/storage method an extremely large array of points will be needed, but in reality an array of about 2000 points is usually enough When the 2000th point is stored, then the current branch stops and many of the old, useless positions are thrown out before another branch begins. The program given in Listing I, Maze Draw, uses all of the improvements described so far It uses the Test command to test points on the screen and a branching point array of 2000 points. A larger array may enable the program to proceed faster. Carefully type the program into your computer and observe how the array is constructed A delay between lines 310 and 320 may be inserted so that you can see the process more clearly. Three dimensions Once a maze has been created, it can be used in various ways A simple two dimensional representation on the screen is the most common Sometimes the screen only displays a small section of the maze with most of the maze being off the screen This is more difficult to program, but it is possible to have a much larger overall maze. Another way to extend the perception of the maze is to give a three dimensional scene of what it would look like if we were actually in the maze itself, looking down a corridor for instance, with side passages branching off. A maze or any passage or array, can be transferred into a three dimensional view by projecting the picture as if you were standing inside the passage, room or maze Side passages are easy to build on just by making lines horizontal instead of diagonal. Now, look at Figure 2, which shows both a maze in two dimensional form, and a three dimensional view from within the same maze In the view, all vertical lines stay the same, in precalculated perspective, until the other end of the passage is reached The side walls follow this line of perspective unless a side passage exists, in which case a horizontal line is drawn as the corner of the passage, both above and below Listing 2 is an extension of Listing t It will take the newly constructed maze and position you randomly within it Then a view is constructed of the inside of the maze in three dimensions By pressing four keys you may step either forward, backward or turn to the left or right The display will then quickly redraw the new view The directions. North, South, East and West are given with the top of the maze taken as being North Probably many uses for mazes and particularly the three dimensional passage section have already come to mind Programs such as adventure games are virtually half done with the above system. The 'passages' program may even be expanded to duplicate the movements through a building design to find. In conclusion, note the use of random numbers in the maze drawing process Computer graphics are relying more and more on random and semi-random constructions Random numbers are going to play an increasing role in computing as programs become more complex In fact, these random functions are extending into every avenue of computing.
|
