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 Programs 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!
|
