CSC 245 - Laboratory 06 - Solving a Maze

In this laboratory exercise you will build a program that solves a simple maze.

Preparation

Problem Statement - Write a program that reads a textfile containing the description of a maze and writes a file containing a description of the solution to the maze.  The mazes will be based on a rectangular array of cells with the start and finish locations located at the outside edges of the array.  The input file is called maze.dat.

As shown above the data file first gives the number of rows nrow and number of columns ncol of the maze array. The next line gives the starting row and column followed by the ending (goal) row and column.  The remaining lines define each of the nrow x ncol cells of the maze.  From inside each cell the order is up, down, left and right wall.  A one (1) indicates that there is a wall in that direction while a zero (0) indicates that it is open in that direction.  For example the starting cell maze(1,1) is in the upper left-hand corner of the maze and has a cell value of (1,0,0,0).  The dead-end at location maze(3,5) has a cell value of (0,1,1,1).

Your ouput should be a list of moves (U=up, D=down, L=left, R=right) which would reach the finish (goal) location from the starting location.  The solution shown above would be written as

RDRDDR

Your program should write the output to a file and display it on screen.  This output file should be named maze.out.  As a goal you should try to generate an optimal (shortest possible) solution but this is not required.  Any string that is less than 255 characters, invokes only valid moves and solves the maze is acceptable.

Design - Your program design can be based on any maze solving algorithm.  Popular approaches include the wall hugging algorithm and the backtracking algorithm.  For example consider the left-wall-hugger algorithm below:

Define a value called dir that is the direction to  move from the current location. Repeat the following pseudocode until goal position is reached:

if open(left_of(dir)) then
dir:=left_of(dir)
move(dir)
else
if open(dir) then
move(dir)
else
dir:=right_of(dir)
end if
end if
In this example pseudocode the boolean function open( ) return true if there is no wall in the current direction from the current cell.  The current position (row,col) is implied here.  The function left_of(dir) returns a direction that is left of the input direction dir.  The type of the function's argument and its return value must match (you may choose to use character, integer or some enumerated type for dir). Notice that left_of( ) is also used to change the current direction.  The procedure move( ) changes the implied current position in the maze.  For example, if the current position were (3,4) and the dir=UP then move(dir)  would change the current position to (2,4). The function right_of(dir) returns a direction that is right of dir.

In the left wall hugger algorithm, why do we first try to turn left even when it is clear to move forward ?  The reason for this can be shown in the simple maze above.  Assume that sometime during the execution of the program we find ourselves at location (1,2) (i.e. first row second column) moving to the right (i.e. dir=RIGHT). Since the way ahead (back to the starting location) is clear we would miss the turn which leads to the finish location.  Instead, our algorithm first checks to see if left_of(dir) is clear and since it is, we turn left and move to location (2,2).

A right-wall hugging algorithm would work in a similar manner.

As an alternative to wall-hugging or backtracking you might consider a random-walk maze solver which moves randomly in any valid direction recording moves until the goal location is reached.  This approach works surprisingly well for small mazes.  As you might guess the length of the solution obtained from a random-walk can be large.

As an option you may consider improving your solutions by removing unnecessary segments of you output string.  A random-walk or a wall hugger will sometimes follows paths leading to dead-ends.  Look at the left-wall hugger solution to the simple maze above.

RRRDDUULLDRDDR

The segment shown in red is the traversal of the dead-end and can be removed.  But how can we easily recognize that this segment is not necessary?  One method of removing unnecessary segments from a maze solution is based on the fact that the pairs of moves UD, DU, RL and LR are unnecesary since they leave us in the same position we were in before the move pairs were executed.  If we scan the string removing these pairs we have shortened our solution by two moves for each pair we find.  Once unnecessary pairs have been removed other move are now adjacent that had been separated by these pairs.  We can apply the scan and remove again to detect new unnecessary pairs of moves.  This can be repeated until no new pairs are found.

RRRDDUULLDRDDR
RRRD  ULLDRDDR

RRRDULLDRDDR
RRR  LLDRDDR

RRRLLDRDDR
RR  LDRDDR

RRLDRDDR
R  DRDDR

RDRDDR

For your convenience you have been provided a copy of maze_demo.adb a program that reads maze data files and diplays a graphical representation of the maze.  You may modify this program to build your maze solver.  The data file you should use for to demonstate your program is maze.dat.

Implementation - To be completed in the Lab or at your own computer.

Encode - Enter your program source code

Debug - Correct your program source code

Analysis - Conduct sufficient analysis to ensure that your boolean function is operating correctly.

Verification -  The method of verication for this program should include a test to make sure that:
the program will eventually end,
the moves are valid (i.e. no walking though walls or outside the maze)
Validation - You should compare your program's solution to the maze to ensure that the solution is valid.

Appendix - Include the source code in an appendix of your report.

Course material is the property of  R. A. Pilgrim