Project One

Design due 27 May and Program Due 4 June

Intro:

The secret agent, Happy the Monkey, has been abducted by the evil Dr. Boron. Happy has been imprisoned in an evil maze like prison and needs your help to escape. Thankfully, he has his palm pilot with him, can run a program that you write to help him find his way out.

Details

When your program starts, it will ask the user for the name of a file that contains the maze's description. Your porgram will then read that file and construct its own representation of the prison. Your program will attempt to find a path through the various cell blocks from the start position to the end position. You will then ask the user for the name of a file to output that path, and its length. When I grade your programs, the program that outputs the shortest path on my test file will receive a special prize ( ie: extra credit, and maybe some tropical fruit!! ).

The prison is composed of several cell blocks. Each cell block is connected at most to 4 other cell blocks. Each cell block has an id from 0 to N-1 (where N is the number of nodes in the prison). The input file that describes a prison is laid out as follows:

• The first number in the file is N, the number of cell blocks.
• The next li class="list2"ne in the file contains the id of cell block 0 ( namely 0 )
• The next four li class="list2"nes in the file indicate the id's of the cell block's that 0 is connected to.
• The next li class="list2"ne after the four is the id of the cell block 1 ( namely 1 )
• The next four li class="list2"nes after that li class="list2"st the cell block's that cell block 1 is connected 2.
• The cell blocks appear in the file in order by their id ( 0, then 1, then 2, etc....)
• The cell block with the id 0 is always the start cell.
• The cell block with the id N-1 is always the end cell.
• If any cell block says that it is connected to a cell block with id -1 means that particular connection is unised ( so a cell block can be connected to less then 4 blocks ).

Example: I imagine a prison of four cell blocks, each of which is connected to each other. The input file would look like this . You can find some other sample mazes here , here , here , and here .

Notes

The simpliest strategy is the random walk. That is, if the monkey is at cell block B, then the monkey randomly chooses any of the blocks connected with B and goes there. For the purposes of grading, assume that there may be dead ends, but no infinite loops of the type shown in class. Thus, when the random path includes a dead end, you can back up to the previous cell block OR just start the random monkey over. There are more intelligent strategies out there. This style of maze is called a "Graph" in computer science theorey. The cell blocks are called vertices or nodes. There are several well known graph search algorithms out there. Heh heh heh.

The output files must only contain numbers and no text. Here, for example, are the output files for the sample mazes above: 4 cell and sameplemaze0 .

Tips

Design your objects. I suggest a cell block object and a prison object. Possibly an over all game object. The more functions that exist in your cell object, the easier it will be to write your program.

Additional requirements

You must design and use two different fully encapsulated objects. Your design document must match the style of the design document we did in class most recently. THERE WILL BE COMMENTS!!! NO FUNCTION SHOULD EVER BE LARGER THAN ONE SCREEN, AND EVEN THAT IS PUSHING IT! Keep your functions short and to the point. Think about 20 lines of actual code ( not including spaces ).

Extra Credit

More intelligent stratigies will receive extra credit. There is a provable optimal strategy out there, if you implement it, you will received lots of extra credit!!! LOTS!!!