Two A-maze-ing Programs
December 17, 2008 Ted Holt
My family and I are preparing to celebrate Christmas. I’m enjoying the lights, the carols, and the decorations. I feel festive. I feel like doing something just for fun. Thus, the two programs I wrote for today’s Four Hundred Guru are of no practical value of which I’m aware, but goodness, did I have fun writing them!
Consider the following text file, the contents of which is a maze.
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII IB I I I I I IIIIIIIIIIIIII I IIIIIII I I II IIIIII II I I I I I I I II IIIIIIIIIIIII I IIIIIII I I IIIIIIIII I I I I I I I I I IIIIIIIII III I IIIII I IIIIIIIII I I I I I I I I I IIIII IIIIIIII I IIIIIII IIIIIIIIIIIII I I I I I I IIIIIIIIIIIIIIIIIIIIII I IIIIIII I III I I IIII I I I I I I I I III I I I IIIIIIII I I IIIII I I I I I I I I I I I I I I I I I IIIIIII IIII IIIIIIIIIII I IIIIIIIIIII I IE I I IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
The beginning and ending points are cleverly indicated by the letters “B” and “E”, respectively. How does one go about writing a computer program that finds a path from point B to point E?
A Recursive Method
One way to tackle this problem is to use recursion. Starting at point B, try to move up. If that way is blocked or turns out to be a dead end, try to move left. If that way is blocked or turns out to be a dead end, try to move right. If that way is blocked or turns out to be a dead end, try to move down.
All of this logic is implemented in a short routine, which in my program is called “Try”. Try takes three parameters–a row number, a column number, and whether or not a solution has been found.
P Try b D pi D Row 5i 0 value D Col 5i 0 value D Solved n D*** locals D CurrentChar s 1a /free CurrentChar = %subst(Maze: Offset(Row:Col):1); select; when CurrentChar = 'E'; Solved = *on; PrintMaze(); return; when CurrentChar = *blank or CurrentChar = 'B'; Mark(Row: Col); Try (Row: Col: Solved); if not Solved; Try (Row-1: Col: Solved); // look up endif; if not Solved; Try (Row: Col-1: Solved); // look left endif; if not Solved; Try (Row: Col+1: Solved); // look right endif; if not Solved; Try (Row+1: Col: Solved); // look down endif; UnMark(Row: Col); endsl; /end-free P e
How can something so short and so simple solve such a complicated problem?
Notice that Try calls itself. In this example, the call to Try (2, 2) calls Try (2, 3), which calls Try (2, 4) and so on. Whenever an invocation of Try runs into a dead end, it backtracks and tries the next direction. Eventually it finds the E and prints the maze.
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII I**************I*********I I I I IIIIIIIIIIIIII*I*IIIIIII*I I***II IIIIII II*************I*I*******I I*I*I I II*IIIIIIIIIIIII*I*IIIIIII I*I*IIIIIIIII I**I*************I*I*******I*I*********I I*I**IIIIIIIII III*I*IIIII*I*IIIIIIIII*I I***I I I***I*****I*** I*I IIIII IIIIIIII I*IIIIIII*IIIIIIIIIIIII*I I I*********I*************I I IIIIIIIIIIIIIIIIIIIIII I*IIIIIII I III I I IIII I I*I I I I I I III I I I IIIIIIII I*I IIIII I I I I I I I I I I I I*I I I I I IIIIIII IIII IIIIIIIIIII*I IIIIIIIIIII I IE**************I I IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
Notice that the path to the end is marked with asterisks.
An Iterative Method
Several years ago, I learned an iterative way to solve mazes from a Dr. Dobbs Journal article. I wish I could find the article in order to give proper credit to the author, but I can’t, and my Google search only turned up references to Basem A. Nayfeh’s cellular automata method, which I’m quite sure is not the article I read.
Anyway, here’s the idea. Beginning at point B, examine each square, row by row, column by column. If a blank square is surrounded on three sides by wall or dead end, mark the square as a dead end. An iteration ends when you reach the end of the maze. Continue until an iteration finds no dead ends.
Consider the following portion of a maze. The last blank in the second row is surrounded by three squares of wall, which means that it’s a dead end.
IIIIIIIIII I I I IIIIIIII
After the first iteration, that square has been marked with an X as a dead end.
IIIIIIIIII I XI I IIIIIIII
The square before the new dead end, which is now the last blank square on the second line, is surrounded by two walls and a dead end. The second iteration flags this square as a dead end, and the maze looks like this.
IIIIIIIIII I XXI I IIIIIIII
And so it goes. Here is the final state of the maze. Follow the blank squares to find the path to the end.
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII IB I IXIXIXXXXXXXXXI IIIIIIIIIIIIII I IIIIIII IXI IIXIIIIII II I I IXI I IXXXXXXXI II IIIIIIIIIIIII I IIIIIIIXI I IIIIIIIII I I I I I I I I I IIIIIIIIIXIII I IIIII I IIIIIIIII I I IXXXXXXXXIXI I I XXXXXXXXI I IIIIIXIIIIIIIIXI IIIIIII IIIIIIIIIIIII I IXXXXXXXXXXXXXXI I I IXIIIIIIIIIIIIIIIIIIIIIIXI IIIIIIIXIXIII IXXXXXXXIXXXIIIIXXXXXXXIXI IXXXXXXXIXIXI IXIXIIIXIXIXIXIIIIIIIIXXXI IXIIIIIXIXIXI IXIXIXXXIXIXIXXIXXXXXXXIXI IXIXXXXXIXXXI IXIIIIIIIXIIIIXIIIIIIIIIII IXIIIIIIIIIII IXXXXXXXXXXIE IXXXXXXXXXXXI IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
My code is available for download . I quickly threw it together, so it is not elegant, and I’m sure you can improve on it, because I know I could.
There are two RPG programs, MAZERECUR and MAZELOOP, which implement the recursive and iterative methods. You will also find a file containing the maze I used in the examples.
Before you call the programs, you’ll have to create a maze in a source physical file member. You can use SEU or WDSC to enter the maze. The rows can’t contain more than eighty characters. You can have as many rows as you like, as long as the number of rows times the number of columns does not exceed 32K.
After you compile the programs, call a program with the qualified name of the file containing the maze in the first parameter and the name of the member containing the maze in the second parameter. For instance, if you put the maze in member MYMAZE in source physical file MYLIB/QRPGLESRC, these are the calls you can use.
CALL MAZERECUR ('MYLIB/QRPGLESRC' MYMAZE) CALL MAZELOOP ('MYLIB/QRPGLESRC' MYMAZE)
Have fun! Merry Christmas!