CSCE 2014 - Homework 3
Due Date - Part 1 03/06/2012 at 11:59 PM
Due Date - Part 2 03/13/2012 at 11:59 PM

1. Problem Statement:

The goal of this programming assignment is to implement a "mouse in a maze" simulation using recursion. You will be given a number of mazes stored in ascii files, and your program must calculate and output the path a mouse must take to go from a starting point S to the ending point E without going through any walls in the maze.

This is a TWO PART programming assignment. For the first part, you must create and test a Maze class that will enable you to store and access information describing a maze. The first part is due ONE week after the project is assigned. For the second part, you must write a recursive program that simulates a mouse searching for a path through the maze from a specified starting point to a specified ending point. The first part is due TWO weeks after the project is assigned.

2. Design:

Part 1: Creating and testing a Maze class. To start with you need some way to represent the maze and an interface for your program to check to see if a position P is the start point S, the end point E, a wall, or open space. To keep things simple, assume that your maze file has the following format:

int int
int int
int int
cccccccccccccccccccc
cccccccccccccccccccc
cccccccccccccccccccc
cccccccccccccccccccc
cccccccccccccccccccc
cccccccccccccccccccc
where the first two integers are the num_rows and num_cols of the maze, the second two integers are the (row,col) location of the starting point, and the third two integers are the (row,col) location of the ending point. After the integers there are height lines of width characters with 'x' for wall, and ' ' for open space. For example, here is a simple maze:
7 20
6 12    
0 18    
xxxxxxxxxxxxxxxxxx x
x             xxxx x
x xxxxx xxxx    xx x
x xxxxx xxxxxxx xx x
x xx         xx xx x
xxxxxxxxxxxx xx    x
xxxxxxxxxxxx xxxxxxx

You must create and test a Maze class that stores the information above in private variables and implements the following methods:

ReadMaze(filename) - Read an ascii maze file into private variables
WriteMaze(filename) - Write private variables into an ascii file
PrintMaze() - Print private variables showing the maze onto screen
getMaze(row,col,value) - get value of maze[row][col] 
setMaze(row,col,value) - set value of maze[row][col]
getStart(row,col) - get (row,col) coordinates of start point
setStart(row,col) - set (row,col) coordinates of start point
getEnd(row,col) - get (row,col) coordinates of end point
setEnd(row,col) - set (row,col) coordinates of end point

Part 2: Recursively searching a Maze. Your next task is to write a program that simulates the movements of an untrained mouse searching for a path through a maze from a starting point S to an ending point E. To do this, you must define a recursive function that calls itself to move N,S,E,W through open space starting at S and ending at E. For example, if the mouse is at location (row,col) and there is a wall at (row+1,col) and the mouse has already visited (row-1,col) then you must recursively search (row,col+1) and (row,col-1) to see if they eventually lead to the ending point E.

If you manually search the maze above, you should see that the there are times when the mouse will reach a dead end and they must "backtrack" to find the correct path. In order for your program to support this you must store and update information about which (row,col) Maze positions have been visited by the mouse and which positions are part of the final path from S to E.

Finally, when your program solves the maze, you need to output/display this information in some way. One option would be to print a sequence of (row,col) coordinates taken by the mouse. Another option would be to display the correct path on the maze itself with another character. This output/display may also be of help when debugging your recursive maze search function.

3. Implementation:

You can implement this program using either a bottom-up approach or a top-down approach. If you go for a bottom-up approach, start by creating basic methods and classes, and test theses methods using a simple main program that calls each method. When this is working, you can create the main program that uses these methods to solve the problem above.

If you go for a top-down approach, start by creating your main program that reads user input, and calls empty methods to pretend to solve the problem. Then add in the code for these methods one at a time. This way, you will get an idea of how the whole program will work before you dive into the details of implementing each method and class.

Regardless of which technique you choose to use, you should develop your code incrementally adding code, compiling, debugging, a little bit at a time. This way, you always have a program that "does something" even if it is not complete.

When you think you are about 1/2 way through the program, upload a copy of your source code and your program output at that point. Be sure to hand in something that compiles even if it does not do much when it runs.

4. Testing:

Test your program to check that it operates correctly for all of the requirements listed above. Also check for the error handling capabilities of the code. Try your program on 2-3 input documents, and save your testing output in text files for submission on the program due date.

5. Documentation:

When you have completed your C++ program, write a short report (less than one page long) describing what the objectives were, what you did, and the status of the program. Does it work properly for all test cases? Are there any known problems? Save this report in a separate text file to be submitted electronically.

6. Project Submission:

In this class, we will be using electronic project submission to make sure that all students hand their programming projects and labs on time, and to perform automatic analysis of all programs that are submitted. When you have completed the tasks above go to the class web site to "submit" your documentation, C++ program, and testing files.

The dates on your electronic submission will be used to verify that you met the due date above. All late projects will receive reduced credit (50% off if less than 24 hours late, no credit if more than 24 hours late), so hand in your best effort on the due date.

You should also PRINT a copy of these files and hand them into your teaching assistant in your next lab. Include a title page which has your name and uaid, and attach your hand written design notes from above.