Project 1 -- EECS380 -- Winter 2001

Maze solver -- ``The quest for cheese''

Originally Due Monday Feb 19th at 6pm.
Due date extended to Friday Feb 23rd at noon.

Overview

For this project you will write a C++ program which routes a mouse (actually Oliver the Mouse) through a maze to find the cheese. You will develop a number of algorithms for solving the maze and will be graded on correctness, programming style, and speed of execution.

The Maze

The Maze consists of open areas (indicated by blank spaces), walls (indicated by `X'), where Oliver starts (indicated by `O') and where the cheese is (indicated by `C'). Oliver, being a fairly simple mouse, can only travel north, south, east or west. He may not travel along the diagonals of the maze. Your task will be to indicate the route from Oliver to the cheese by drawing the route using the `*' symbol. So a sample maze might look like this: 
XXXXXXX
XXC   X
X   XXX
X     X
XXXXX X
XO    X
XXXX XX
While the output might look like: 
XXXXXXX
XXC   X
X * XXX
X ****X
XXXXX*X
XO****X
XXXX XX
The maze will be a square of fixed size (N by N) and Oliver is not allowed to leave the bounds of the maze.

Sample mazes have been posted as handouts.

Routing schemes

You are to develop three routing schemes for Oliver. In the queue-based routing scheme you are to have a queue of maze locations. Place the location that Oliver starts at in the queue. And then do the following:
  1. Dequeue the next location.
  2. Enqueue all locations next to the location you just dequeued which are empty spaces (blanks) that have never before been enqueued. Remember that Oliver can only travel north, south, east or west, so diagonal spaces are not considered next to each other. As you enqueue these spaces, check to see if any of them hold the cheese. If none of them do, go back to step 1.
  3. Clearly you have found a route from Oliver to the cheese, but exactly what that route may not be clear to poor Oliver (or yourself!) So you need to figure out what route Oliver should take. Your route should not backtrack onto itself. That is, it should not require Oliver visiting the same square twice.
For the stack-based routing scheme, do the same thing, but push and pop the locations rather than enqueueing and dequeueing them. Clearly you will need to expand on the above algorithms, but you must follow the basic algorithm outlined above for the queue and the stack-based routing algorithms.

For the optimal routing scheme, you are free to use any routing algorithm you wish to run. But you must get Oliver to the cheese in as few steps as possible AND you will be graded on how long it takes you to find Oliver's route. The first goal is getting an optimal route. Finding a non-optimal or illegal route (going through walls, outside of the Maze, etc.) quickly is worth nothing, even if it is fast...

Input and Output formats

Your program should be able to deal with two different input and output formats. The first is a coordinate scheme where Oliver, the Cheese, and each wall are listed by their XY-coordinates. Any unspecified location is assumed to be empty. The second is a map where the XY coordinates are implicit by their ordering. In both cases the size of the maze is specified on the first line as a single integer ``N'' representing an N by N maze. For example the following is a legal map-formated Maze: 
4
XXXX
O XC
X   
   X
While that same Maze could be specified in the coordinate scheme as: 
4
X 0 0
X 0 1
X 0 2
X 0 3
X 3 3
O 1 0
X 2 0
X 1 2
C 1 3
The output file formats are very similar. For the map format simply add the ``*'' as needed to specify the path in addition to reprinting the rest of the map. For the coordinate solution specify only where to place ``*''s. So for the above Maze one might get: 
4
XXXX
O*XC
X***
   X
as the map format and that same solution could be represented using the coordinate output as: 
* 1 1
* 2 1
* 2 2
* 2 3
In the event of the coordinate solution the path should specify each step taken starting next to Oliver and ending next to the cheese.

In either case, if no route exists your program should print an informative message to standard error, exit(1), and leave the output file blank.

Timing

When you are asked to time your program, you should measure the time it takes for your search algorithm to run. Do not include the time it takes to read the input or write the output. HOWEVER you must include the time for the entire search algorithm including figuring the exact path taken. Don't try to bend the rules here (by starting the search while reading in the data), doing so will result in 0 points for the timing part of the grade (see below).

Timing information reported should be printed to standard output in the following format: 

@@@ runtime=X
where X is some base-10 number. You should do this by using the following command:
cout << endl << "@@@ runtime=" << X << endl;
Where X is a double.

Stacks, Queues and the STL

You are to write the program using your own stack and queue classes. Those classes should have the same interface as the stack and queue classes in the STL. Further, you will also be expected to use the STL rather than your own stack and queue implementation. You only need to write the member functions for queue and stack that you actually use!

To be able to experiment with different implementations of the same interface, (stack and queue) you need to do the following:

  1. Have the alternative container classes available (each class must have a different name).
    Example:
      Proj1MyContainer, Proj1STLContainer

    Note, you need not use the same names as above (e.g. Proj1STLContainer).

  2. Implement your code that uses containers in terms of an alias Example: Container (in other words, Container will be the class name assumed by your code, even though no such class was defined yet).

  3. Use the typedef command to make the alias point to one of the actual classes
    Example:
      typedef Proj1MyContainer Container;
    This command should go after your #include the headers of your container implementations.

  4. In order to change how the code is compiled, depending on the container implementation you need, use 
    #ifdef  STLon
  typedef Proj1STLContainer Container;
#else  
  typedef Proj1MyContainer  Container;
#endif
    (The # should be in the first column of your code and not indented.)

  5. STLon is a "macro" or a "symbol" that, when defined, will make your code use an STL-based container. Otherwise, your own container will be used (but the code implemented in terms of "Container" will be unchanged !)

  6. To define STLon, modify Makefile and add -DSTLon after g++. This has the same effect as adding #define STLon 1 to your code (before #ifdef), except that your code is not modified.
When you submit your project, you need to have -DSTLon set in the Makefile. The autograder will run your code that way to test how it uses STL, then remove -DSTLon from the Makefile and run the code to test how your containers work. The code should work identically (constant-factor differences in speed are allowed). None of your code should ever perform a #define STLon. If you want to better understand what all of this is doing, read the man pages for cpp and the -D flag for the g++ compiler.

Additional suggestions can be found in the stackVSqueue.cxx handout.

Command line arguments

Your program should take the following command line arguments: (when we say a switch is "set" that means it appears on the command line.) Legal command line arguments must include exactly one of -Stack -Opt or -Queue. If none are specified or more than one is specified the program should print an informative message to standard error and exit(1).

Sample inputs and outputs

Using the stack based algorithm put with the map format for input and output: 

4
XOXX
X  X
XX X
XXCX
should result in: 
4
XOXX
X**X
XX*X
XXCX
And using the queue algorithm with the coordinate input and output: 

10
O 3 7
X 4 5
X 4 6
X 4 7
X 4 8
X 6 6
X 6 8
X 6 9
C 8 7
Should result in: 
* 3 8
* 3 9
* 4 9
* 5 9
* 5 8
* 5 7
* 6 7
* 7 7

Errors to check for

In all these cases, print an informative error message to standard error and exit(1).

What you don't need to check for

How to turn things in

First of all, be 100% certain that your code works on a SUN workstation running Solaris.

That said, do all of your work, with all needed files, in some directory other than your home directory. Before you turn in your code be sure that:

You should receive some feedback indicating that the program was received and that things seem to be in working order. If you do not get that feedback within 30 minutes, please contact Prof. Brehob at brehob@umich.edu.

You will not receive a grade from the autograder. Once the due date has passed we will grade your code (both with an autograder and by hand). The last thing you turn in is what we will grade.

So why are we doing things this way? There are many reasons. We clearly need to have an autograder of some type, there is no way we can grade so many student's projects for correctness by hand. This frees us up to look at coding style and algorithm issues. At the same time, giving the students complete autograder feedback makes the debugging process unrealistic. It will be very rare indeed when you have some way to validate that your code is 100% perfect (or at least as perfect as it needs to be). As such we are providing just enough functionality to insure that you are getting the basics right (compiles, runs, gets some trivial cases correct, etc.) but not so much as to take away the need to carefully test your own code.

The program submit380 should be available starting Feb 6th. (changed)

Coding style

Use a reasonable organization for your overall program.
Find a fairly reasonable class structure. Don't stick everything into one class. Make reasonable use of constructors. Where needed be sure to supply a custom destructor. If the way you design your code feels sloppy to you, it probably is. Utilize multiple files in a way that is consistant with the general use in C++. Our text does a good job describing this.

Use reasonable comments.
Explain what each class does and what each data member is used for. A one or two line description of most member functions is also desirable. Where you use non-standard coding techniques, document them. List your name and the date last modified for each file.

Remember that a useless comment is worse than no comment at all.
int temp; // declare temp. variable
would be an example of a useless comment which just makes code harder to read!

Use reasonable formatting.
It should be obvious where a given code block ends due to indentation. Use reasonable and informative variable names. On systems where the program "cb" (C beautify) is available, consider using an indentation style similar to what it generates. Avoid lines that wrap in an 80 column display wherever possible.

Variable names
Using things like "i" and "j" as variables can be reasonable, but you should not use such variables to store meaningful long-term data. Other than LCV (loop control variables) you should use descriptive names for your variables, functions, classes, structures, etc.

Code resuse
If you find yourself rewriting basically the same algorithm many times, stop and try to see if you can somehow reuse the code.

Grading

Further, poor coding style will result in potentially significant deductions. Follow the above rules as closely as possible.

Hints and advice

Sample files

Sample files.