General Project Description

As an employee of Childrens' Games, Inc., you have been tasked with the responsibility of demonstrating that all of the mazes that have been generated for the new Maze & Puzzle book are indeed solvable. Fortunately, another developer has created an application that generates "perfect" mazes (perfect mazes have exactly one path from start to finish, thus having no loops). It is your responsibility to double-check each maze that the application generated so that children around the world will have brighter lives when they receive the Maze & Puzzle book as a gift.

Project Description

Class Description

• MazeCell - single cell of the maze
• Maze - entire maze
• MazeCrawler - maze solver

Functional Description

Design and Implementation Requirements

Classes

• MazeCell - this class stores a single cell for the maze. It may hold as much or as little information as your application requires. Some details that would make this class more useful might include:
  • knowledge of whether neighbors are walls,
  • knowledge of whether this cell has been backtracked through,
  • character representation of this current cell, and
  • is this the start cell or end cell.
• Maze - this class uses the MazeCell class and handles the tasks of reading in the maze from the file and printing the maze.
• MazeCrawler - this class is the "brain" for solving the maze, its task is to use the right-hand algorithm to maneuver through the maze, from start to finish, determining if the maze is solvable.

You may add any other classes that your application requires. It is up to you to determine what the best way for the above classes to interact, there are many acceptable solutions, no one is necessarily better than another.

However, your design may not have both the Maze know about a MazeCrawler and the MazeCrawler knowing about a Maze, there is no need for this dual connection between these two classes. Other than this restriction, you may decide whether the MazeCrawler should own a Maze or the Maze should own a MazeCrawler.

In designing your classes, adhere to the following guidelines:

• Support high cohesion - each class should have a responsibility and should handle it very well - this responsibility may have many components, but all operations within the class should be tightly connected to one another.
• Support low coupling - classes should not be dependent upon the internal representation of data from another class. For example, if one class uses a vector to store data, other classes should not know that a vector is being used - they should have some other method for accessing vector items.
• Demonstrate aggregation - classes should store instances of other classes as private data members.
• Functional cohesion - as with functions, each method of a class should have a single job, and do that job very well.
• Data storage - data should not be duplicated within a single class or between classes, store information in a single place and allow access to that data using appropriate mechanisms.
• Limit input/output in classes - it is acceptable to localize the use of cout/cin to Input and Output function (like Print()), however, it is more acceptable to pass an istream or ostream to the function (i.e. cin/cout) as a parameter. These parameters must be pass by reference.

Tips for Developing Classes

• You will need to add a target for each of your classes to your makefile. Begin by creating the .cpp and .h files for each of your classes, and performing a make.
• Develop your classes slowly. Begin development of the MazeCell class, start with just a simple .h file with no methods, save, compile.
• Implement "stub" methods that do not carry out their entire task, but return a valid response. These methods will gradually be fleshed out.
• Add precondition checking to each of your methods. Save, compile.
• Develop a simple main function that will act as a cell-tester. It should create a cell, and then run each method on the cell, verifying that each method correctly checks its preconditions.
• Add one method at a time. Modify the cell-tester to check for this newly implemented method. Save, compile, run, test.
• DO NOT try and implement an ENTIRE class at once - you will spend more time debugging and correcting your errors than if you develop testing applications and test each method as you develop it.
• Add about 5 lines of code in each iteration. Save, compile, run, test.
• Start with the MazeCell class, get the entire application working with just that class. Then implement the Maze class, again, getting the entire application working with that class. Finally add the MazeCrawler class, getting the entire application working with that class. This type of modular development will decrease your debugging time and will ALWAYS leave you with a compiling, executing application.

Functions

• Limit the use of these "helper" functions by your classes. No acces to these functions is the preferred design.
• All functions called from main() or any other function, must be implemented in a separate file named Proj2Aux.cpp. The prototypes for these functions must be found in a file named Proj2Aux.h.
• Be sure your function header comments list the pre- and post-conditions and handle each pre-condition that is not met.
• Review the class notes on the different methods of passing parameters. Each is best for a different situation.

General Tips

• TEST your program thoroughly - the makefile provided has a 'make test' target that you can use to ensure that your application will work with our test suite. HOWEVER, you need to test your application using other mazes that you create yourself. Be sure to examine the guarantees closely and be sure that your project handles all of the "bad" cases.
• Be sure to name your files as noted above, otherwise, you will have to modify the makefile we provide.
• Because your program will be tested using Unix redirection, DO NOT prompt for any input not specified in the project description.
• Use incremental development, develop one function at a time, write code that will thoroughly test it, run and test it, then move on to another function. Don't be afraid to write testing code that you will eventually get rid of.
• This project is approximately 150 - 250 lines of code... don't procrastinate.
• Ms Wortman's public directory for this project is /afs/umbc.edu/users/d/a/dana3/pub/CMSC202/p2.
• Do not cheat, you will be caught. Do not look at another student's code - it is very tempting to "borrow" an algorithm. Do not show your code to another student. Use the Tutors, TA's, and Instructors.
• Make sure you have completed Project 0.
• Check the discussion board before emailing a TA or Instructor - your question has probably already been answered.

Project Design Assignment

Project Makefile

The "make" utility is used to help control projects with large numbers of files. It consists of targets, rules, and dependencies. You will be learning about make files in lab. For this project, the makefile will be provided for you. You will be responsible for providing makefiles for all future projects. Copy the file makefile from Ms. Wortman's public directory to your directory.

When you want to compile and link your program, simply type the command make or make Proj2 at the Linux prompt. This will compile all necessary .cpp files and create the executable named Proj2.

The make utility can also be used for compiling a single file without linking. For example, to compile Proj2.cpp, type make Proj2.o.

In addition to compiling and linking your files, make can be used for maintaining your directory. Typing make clean will remove any extraneous files in your directory, such as .o files and core files. Typing make cleanest will remove all .o files, core files, Proj2 executable and backup files created by the editor. More information about these commands can be found at the bottom of the makefile.

Updated: If you are building your own makefile, you MUST use the /usr/local/bin/g++ compiler to compile and build each file. Do not depend on setting your default compiler to be this compiler, the grader may use a different compiler. There are two compilers on the GL systems, and you are required to use the one located at /usr/local/bin/g++.

Grading

The grade for this project will be broken down as follows. A more detailed breakdown will be provided in the grade form you receive with your project grade.

85% - Correctness

• Your project produces all required output.
• The output produced is correct.
• The output is in an acceptable format.
• Your program follows good top-down design principles.
• All function parameters are passed using the appropriate method.
• const variables are used wherever appropriate.
• All unmet function pre-conditions are handled.
• Classes demonstrate high cohesion.
• Classes demonstrate low coupling.
• Classes demonstrate appropriate distribution of tasks.
• All project requirements are met.

15% - Coding Standards