PolyMaze! Solver. Dan Rollins.

POLYMAZE! SOLVER

Programming a computer to generate and solve a maze is more than a fascinating pastime. Maze generation encompasses some of the most basic and important concepts of computer programming. Lists, pointers, two-dimensional arrays, stack structures, binary numbering and logic, simple trigonometry, and the concept of an algorithm are all integral parts of maze programs. In this article I will discuss these subjects and introduce a novel display format and a surprisingly simple method of solving mazes.

A maze aficionado before computers became affordable, I have always enjoyed the challenge of solving mazes. After buying my first computer I found a bigger challenge--programming the computer to create randomly and solve a maze. I have written a maze generator for a pocket computer ("Pocket Computer Fun,' Creative Computing, December 1982), hexagonal cell mazes, ("Bee Amazed,' Creative Computing, June 1981), and a fast Z80 machine language maze generator (Kwikmaze,' 80 Micro, November 1982). The common thread through all of these programs is a simple maze-generation algorithm and a bit-oriented method of representing the maze during its creation.

This article presents two programs that demonstrate the maze generation algorithm. The first, written in standard Microsoft Basic, works on many different types of computers. The other listing creates and solves a maze shaped as a polygon. It is written for the IBM PC and makes use of its advanced graphics features.

Maze Generation

I like to think of a maze as a one-floor building with an unusual design. The architect was a bit lazy and decided to make the rooms exactly square and all the same size. After drawing all the rooms, he realized that he had neglected to include any hallways. He quickly inked in a wide door on each of the four sides of every room and went off for a three-martini lunch.

After the building had been constructed, the new owners forced the architect into early retirement, then went about making the best of the situation. They selected certain rooms as offices and sealed three of the doors in those rooms. Certain vice-presidents thought that they should have larger offices, so the doors of some of the rooms were removed to create spacious suites. They then removed the doors of other rooms to create a network of hallways connecting the offices.

It is easiest to think of maze creation as the process of "opening the doors' to connect various rooms. There is no such thing as a "hall--only rooms in which two or more doors have been opened to create a passage between more distant rooms.

To generate the maze you simply walk randomly through the building, leaving open the doors by which you enter and leave a room and sealing off the doors you didn't open. You are likely eventually to reach a position in which all of the possible exits to a room have been sealed off from the other side. To continue, you must return and unseal some doors to find another block of unvisited rooms. You keep track of the number of rooms that you visit and when this total matches the total number of rooms in the building, you know you are finished. This system makes sure that your path doesn't cross itself, thereby ensuring that there is only one direct path between any two rooms. Consequently there is only one solution to the maze, regardless of where you decide to place the entrance and exit.

You can represent the unemployed architect's floor plan as a two-dimensional array. In your random walk through the building, you must keep track of which room you are currently visiting. Your position is represented by a pair of coordinate values, i.e., an X Y pointer into the array. You move from room to room by adjusting one of these ordinates by either -1 or 1 and leaving the other the same. Use the Y-pointer as a north/south ordinate. Decreasing it by one moves it north. Increasing the Y-pointer moves it toward the south. Increasing and decreasing the X-pointer indicates motion east and west, respectively.

Each array element contains a value that indicates which of its doors are open and which are closed. The array starts with each element being 0, so consider this value to be a room with all the doors closed. As you move through the array, you place values into the elements to indicate which doors you used to enter and leave the room.

One possible method of recording your walk would be to say that if you left the north door open, you set the element to 1. To leave the east door open, add 10. Add 100 for a south door and add 1000 for a west door. Then you need only check the decimal positions to know exactly which of the doors were used. For example, if an array element held a value of 1001, you could see that there must be doors open to the west and to the north.

The decimal method has a major drawback. To test for a particular open door, a time-consuming series of calculations must be performed. Fortunately Basic includes the Boolean logic operator AND which allows quick testing of binary bit positions within an integer value. The AND operator compares the bit-patterns of two operands and returns a value whichhas bits set that are on in both operands. If you use binary values to indicate the state of the doors of a room, the test for any particular door may be performed quickly and efficiently. When:

north = 0001 binary = 1 decimal

east = 0010 binary = 2 decimal

south = 0100 binary = 4 decimal

west = 1000 binary = 8 decimal

You can open a western door with:

MAZE(X, Y) = MAZE(X, Y) OR 8 'set the West bit = 1 and you can test for a southern door with:

IF MAZE(X, Y) AND 4 THEN . . . 'true when South bit = 1 You end up with each room (array element) as a switch box that holds the YES/NO switches for each of the possible directions.

Given this system of coding the elements of the maze array, you need only create the algorithm to perform the walk-through. The major steps are:

1. Initialize X and Y randomly and set the room count to 0.

2. Check to see if all the rooms have been visited. If so, you are done.

3. Check the rooms to the north, west, south, and east and keep a list of the directions to those rooms that haven't been visited.

4. If there are no adjacent rooms that haven't been visited, scan until a room is found that adjoins an unvisited room (repeat step 3).

5. Choose randomly from among the list of possible directions.

6. Place a value in the current array element to indicate an open door in this direction.

7. Adjust the X, Y pointer to point to the new room.

8. Indicate that the door has been opened in this room also. (If it was entered by moving south, then the north door is now open.)

9. Indicate that another room has been visited (increment the room counter).

10. Go to step 2.

This algorithm is fast and efficient. It yields an array of binary values that represent a maze with only one direct route between any two rooms. Because the binary values are easy to decode, there is much flexibility in the possible methods of displaying and solving the maze.

Listing 1 illustrates this algorithm and shows an example of a simple display subroutine. Some Basics (notably Appesoft) don't support the bit-logic AND operator. This listing actually uses the bit-setting scheme we have discussed, but avoids using AND for testing the state of the doors. I suggest that you enter and try modifying this listing. This bare bones maze generator is the founation of the loftier concepts we are about to discuss. Figure 1 shows the output for Listing 1.

Polymaze

I have always toyed with the idea of creating mazes with unusual shapes. But it wasn't until I got my IBM PC with its wonderful graphics capabilities that I could make the concept a reality.

The idea behind Polymaze is that "rooms' of a mace need not all be identical in shape or size. As long as I could keep a list of the four corners of each room, I could draw lines to connect the corners that made up a wall. Originally, I thought about displaying the

maze as a series of concentric circles.   Because a circle is simply

a polygon with many sides, I came to realize that the idea could be extended to include mazes with any number of sides.

Although the mazes created by Polymaze come in a variety of shapes and complexities, they are all based on the simple maze we have been discussing. Each room has exactly four sides (walls or doors), but the length of the sides varies according to fixed rules.

Figures 2a to 2e illustrate the idea of "stretching' a simple maze into a polygonal maze. Notice that each figure has the same number of vertices and lines and the pattern of the maze is the same for each. The only difference is that the X, Y coordinates for each vertex (the corners of each room) have been recalculated for each figure.

When discussing a square maze, I have referred to the directions of motion as north, east, south, and west. After stretching the maze into a polygon, you can see that these directions are no longer valid (the southern door, for example, may actually face in any direction). Therefore, I will hereafter refer to the directions as inward (IN), clockwise (CW), outward (OUT), and counterclockwise (CCW).

Displaying Polymaze

Without going into advanced trigonometry, I will explain the system that Polymaze uses to calculate the corners of each room. Let's start with the twelve points around a clock face that indicate the hour marks. Each mark can be expressed as an X, Y coordinate pair. To find the X (norizontal) ordinate for any hour point, you need to use the SIN function of Basic.

X = SIN(N) expects N to be a value between - and . It returns a floating point value for X that would be found somewhere on the perimeter of a circle that has a radius of 1. Given this X, you can multiply it by R, a radius factor, to yield an X ordinate of a circle with radius R.

Because you are trying to locate 12 points around the circle, you need only step N from - to in increments of (2* )/12 to find the X ordinates of each of the 12 hourly positions. Half of the ordinates will be less than 0, so to center the clock in the middle of the screen, you must add an offset to each X ordinate.

The COS function has a corresponding effect except that it returns a Y (vertical) ordinate. For every X ordinate that is calculated, a matching Y ordinate must also be formed.

You can plot the 12 positions around a radius 50 clock by using the sequence in Listing 2.

The points are plotted starting at 12 o'clock and working clockwise around the circle. The same logic would work if you stepped N from 0 to 2* , except that the points would be calculated starting at the 3 o'clock position.

If you entered and ran the short program in Listing 2, you noticed that the circle was not particularly circular. This is because the IBM screen is wider than it is long. To offset this, you can further modify the X ordinate by scaling it by a screen-correction value. Adding line:

45 X = X + X* 100/320

corrects each point so that the circle appears exactly circular. A screen-correction factor can be used to scale the circle smaller or larger along either axis. In Polymaze, I chose to stretch the circle along the X-axis so that it fills the screen more completely. I also included a scaling factor that enlarges small mazes to fill the entire screen.

Since you can plot 12 dots around a circle of radius 50, it is easy to see that it is possible to plot any number of dots around a circle of any radius--just by changing the number of divisions around the circle and the radius factor. Finally, you need not simply plot the dots. You can save each coordinate pair in an array then later use them as endpoints for the lines that will make up the walls of the rooms of the maze.

Polymaze calculates the X, Y pairs that make up a polygon for each of the concentric levels of the maze. A room is defined by four endpoints. These are the endpoints of the two lines defined by a polygon edge at one level and the corresponding edge one level inward. Given a vertex and level pointer, (X and Y for simplicity), the points that define a room are:

(X, Y) = outer counterclockwise corner

(X + 1, y) = inner counterclockwise corner

(X, Y + 1) = outer clockwise corner

(X + 1, Y + 1) = inner clockwise corner

The exception to the rule is when your are referencing the highest numbered vertex of any level. It connects with the points of vertex 0.

If you connect these points, you have a trapezium with the inner line shorter than the outer line--an upside down lamp shade.

By examining your previously generated maze, you can determine which of the corners need to be connected, i.e., if the maze arrow, indicates that there is an open door, don't draw the line. Therefore, displaying the maze is a simple matter of looping through each of the levels and each of the vertices and drawing the lines indicated by the bit patterns in the maze array.

Given a maze generated by the algorithm we discussed, displaying it as a polygonal figure is simply a matter of determining the endpoints and drawing the necessary lines. The work is all in the display part of the program. However, there is one minor difference in the maze generation algorithm for polygonal mazes. Rooms that are on the easternmost side of a normal square maze have been stretched around until they are directly adjacent to the rooms on the westernmost side. The algorithm must be modified to allow doors to be created that connect these two extremes.

If you compare lines 1000-1220 of Listings 1 and 3, you will note that the only major difference is the inclusion of lines 1070 and 1080 in the Polymaze listing. These do a check to see if the "wrap-around' is possible and add the direction to the list if so. Also line 1130 makes the wrap-around adjustment when the move crosses this boundary.

Before a discussion of the maze solution routine, I would like to present a challenge to skilled programmers. Remembering that the rooms of a maze don't need to be the same size or shape, can you design an algorithm that displays a maze so that its rooms are trapezia with sides of random lengths? The only constraints are that lines (walls) of an individual room don't cross each other and that every wall or door is wide enough to clearly delineate an edge of the room; i.e., never to have two endpoints so close together that they appear as one. This seems to be the ultimate in randomized mazes.

Solving The Maze

Lines 4000-4320 of Listing 3 allow you to work your way manually through the polymaze by pressing the cursor control keys. The only trick is to remember that the arrow keys are redefined from "move up, right, down, or left' to mean "move outward, clockwise, inward, and counterclockwise.' To indicate your current position, the program uses the dramatic PAINT command. This is seen again in the "razzle-dazzle' routine starting at line 6000. The effect of the paint sweeping through the mace is startling and delightful. It also gave me the clue to an unusually simple algorithm that solves mazes.

If you use the Ctrl-NumLock sequence to pause the progress of the PAINT command, you can see that PAINT is actually solving the maze! Starting the paint at the exit to the maze, it works its way eventually to the entrance. It may take detours into culde-sacs (dead ends), but it very quickly finds its way to the outer top vertex.

The IBM PC Basic manual states that you might need to CLEAR extra stack-space memory if you use the PAINT command on complex shapes (I found that a compiled version of Polymaze required this). The clue is that PAINT is a stack-oriented command. It apparently paints left and right until it reaches a border color. When there is a choice of moving either up or down, it saves its current position on the stack and continues painting left and right going down. When it can't continue, it POPS its most recent decision point off the stack and continues up from there. When it meets a dead-end and finds that there is no decision point to POP, it has completed its function.

That PAINT was solving my maze was interesting. I let is smolder at the back of my mind for a while as I wrote the cursor control routines. At one point I was moving through a very complex maze (60 vertices by 18 levels), and I found fingerprints all over my monitor screen. I had been placing my finger at decision points so that I could trace around the maze and return if my choice had been a false lead. It occurred to me that I could give the player a useful tool to aid in manually solving the maze. It has been included in Listing 3 as the save and retrieve command.

While you manually solve the maze, you canpress S to save the current position. Pressing R restores the values that were most recently saved, putting the cursor in the room where you most recently pressed S. You can save your position more than once--the program remembers the position of each of the rooms where you pressed S. These positions are all available, but they may only be accessed sequentially backward from the most recently saved room.

Thus, saved rooms are placed in a stack, but just like a stack of books, you can only reach the book that is on the top of the pile. A after taking the top book off, there is a new book on the top so it becomes available.

There it was again--a stack-oriented procedure. The two clues came together, and I sat down and formulated the algorithm for solving a maze. The goal is to end up with a list of all the rooms that must be traversed to go from the entrance to the exit of the maze. This I call the solution list. I needed a stack structure to hold not only the coordinates of a room but the direction of entry and the count of the number of rooms in the resolution list.

Here is the maze solving procedure I camp up with:

1. Initialize an empty stack structure to hold room coordinates, direction, and the solution list pointer.

2. Initialize an X, Y pointer to the entrance and a direction value.

3. Enter a room in the current direction. Save this position in the solution list.

4. If the position is the exit, then the solution is complete.

5. For each door in a room, save the coordinates of the room it connects with, the direction by which it would be entered, and a count of the number of rooms that are in the solution list. In other words, PUSH the relevant data on the stack.

6. Retrieve the data from the top of the stack. This moves the X, Y pointer into a new room and updates the direction and the solution list count. This step POPs data from the stack.

7. Go to step 3.

The beauty of this algorithm is that no special work needs to be done for special situations. Regardless of the number of open doors in a room, the program does the same thing.

The most common situation is that a room has only two doors. Since we entered by one, the data for the other door (the only exit) are the only values PUSHed. They are immediately POPped in the next step.

When there are three or more doors (two or three possible exits), a decision point has been reached. We simply PUSH both (or all three) sets of data onto the stack and immediately POP one back off.

When a room has only one open door (a cul-de-sca), no data are PUSHed onto the stack. So the next POP returns the data from the route that was not taken at the most recent decision point. Since the solution list counter is part of the data on the stack, it is restored with the POP. This means that all of the rooms that were saved in the solution list between the last decision point and the POP are abandoned. They obviously didn't lead to the exit of the maze so they shouldn't be included in the solution list.

Figure 3 and its caption illustrate this algorithm for a simple maze. The same logis is used to solve a polymaze.

As you see in Listing 3 (lines 5000-5140), the maze solving routine is vert short and simple. The subroutines starting at lines 5500 and 5600 handle the PUSH and POP functions. The subroutine at line 5700 is called whenever a new room is entered. It displays the current position to give you a graphic demonstration of the solution algorithm.

There is one tricky bit of coding that might deem peculiar. When a new room is entered, the program must "look' in three directions to see which doors are open. The four directional values are the same as used in the maze generation routines, i.e., 0 = OUT, 1 = CW, 2 = IN, 3 = CCW. These numbers correspond to the power of 2 that defines an open door in the same direction. So to check if there is a door in direction 3, the program could AND the room value with 2 3, i.e., 8. But this would force the computer to do a time-consuming transcendental function--exponentiation. So I have defined a four-element list to hold these values. The computer needs only to look up the value in the list.

cIn this illustration, lowercase letters indicate rooms where a decision is made. Starting at the entrance, the pointer proceeds to room a. Rooms D and B are pushed onto the stack, then room B is immediately POPped. The pointer advances to room C which is a cul-de-sca. No data are PUSHed, so the POP results in the advance of the pointer to room D. Note that the rooms between (and including) B and C are removed from the solution list when the data associated with room D are POPped--the solution list pointer points back to when they had not yet been saved.

At room e, rooms Q, O, and F are PUSHed and F is POPped. The stack keeps growing until room J is reached. At that time, K is POPped and the pointer proceeds to room L. This continues until after room Q is POPped and the stack is temporarily empty. The solution list now contains only the rooms that directly connect the entrance to room Q.

When the exit is finally reached, room S (and any other unresolved decisions) remain harmlessly on the stack, and the solution list contains a sequential record of each of the rooms that must be traversed to go from entrance to exit.

Now to "rotate' the direction so it points to each door in turn, I could say:

DIR = DIR+1:IF DIR=4 THEN LET DIR = 0

But a quad-state pointer can be very quickly rotated with:

DIR = (DIR+1) AND 3

This uses the arithmetic function form of the AND command. Try thinking in binary and cycling through that equation six times. You will see the desired pattern emerge. The same logic can be used to cycle the pointer in the opposite direction i.e., 3 2 1 0 3 2 . . . instead of 0 1 2 3 0 1 . . . Use:

DIR = (DIR-1) AND 3

Playing With Polymaze

The Polymaze program in Listing 3 requires an IBM PC with the color graphics card and Basic A. You can use a monochrome monitor like the NEC Character Display but not the IBM monochrome monitor. You will enjoy the program more with a color monitor.

Polymaze offers a menu with three options. The first option asks you for the size of the maze you want. It then generates and draws a maze and allows you to try to solve it. The maze is displayed in white lines. Your current position is displayed at each step by filling in the current room with blue and by blinking the walls of the room. Use the cursor control keypad to move. For complex mazes, you might want to use the S and R keys as an aid to finding the solution. When you reach the center (the maze exit), the program does a little razzle-dazzle then returns to the main menu.

The second option allows you to watch the solution algorithm in action. The maze is created and displayed, then the computer solves the maze and displays the most direct path. The program asks you to press any key and you are returned to the main menu.

The final option turns your computer screen into a fascinating display. It continually draws mazes of random sizes and displays them in random colors. Pressing any key returns you to the main menu.

The subroutines used in Polymaze are well defined and fully commented. It should be easy to expand this program to make it into a race game or the basis for a labyrinth adventure.

Summary

The programs and discussions presented here have covered much territory. The maze generating and solving subroutines are algorithms-step by step procedures to perform a desired task. We talked about one-dimensional lists and two-dimensional arrays and how to access the data in each of the array elements.

The maze data are in the form of binary numbers--each bit indicating the open or closed condition of one of four doors in a room. We talked about how to set the values to indicate the state of the doors and how to test the bits to determine that state.

The discussion on displaying a simple maze in the form of a polygon included some rudimentary trigonometry and topology. We had to use SIN and COS to calculate the four endpoints that would define the corners of each room, and we saw how the topology of a simple maze can be "stretched' into the shape of a polygon.

We talked about the concept of a stack and how it is used in this application to aid in the process of making decisions. By stacking the decision point data and retrieving that data upon discovering that the wrong decision was made, we found a way to make a very complex decision--the solution to a maze.

Table: Listing 2.

Table: Listing 1. SIMPMAZE.BAS.

Table: Listing 3. POLYMAZE.BAS.

Photo: Figure 1. Output of SIMPMAZE. BAS.

Photo: Figures 2a-2e. Five states of "stretching' a maze.

Photo: Figure 3. Illustration of maze-solving algorithm. This figure illustrates the Polymaze stack-oriented maze-solving algorithm. As a pointer is moved through the maze, the coordinates of the current room are saved in a solution list and data for each adjoining room are PUSHed onto the stack. The saved data consist of the coordinates of the room, the current value of a "solution list pointer' and the direction of the open door.

After the data for each adjoining room are PUSHed, one set of data is POPped. When there is only one adjoining room (aside from the room just vacate), the pointer always advances to that room.