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

Dynamic Memory

You must implement the Big Three (Destructor, Copy-Constructor and Assignment operator) for each of these classes.

You are also required to modify the MazeCell class to use pointers to its neighbors to determine which directions are open. You will also need to make modifications to the Maze and/or MazeCrawler classes to support this new connection between MazeCells.

Operator Overloading Updated!

You are also required to overload the extraction operator for the Maze class. Again, feel free to reuse any existing code. Do not duplicate code. You may choose to delete any existing methods that accomplish the same task. The stream passed into the extraction operator should be an open file.

All overloaded operators must operate on OBJECTS of each class, NOT on pointers to an object. You should remember to dereference pointers before attempting to use the overloaded operators on them.

Functional Description

Design and Implementation Requirements

Dynamic Memory

Each of these classes must have the Big Three implemented and used appropriately. All instances of dynamic memory in these classes should be properly allocated and deallocated in the Big Three. Even if your class does not allocate dynamic memory, you must overload the Big Three.

Dynamic Neighbor Links

The purpose of this optimization is to speed up the time it takes to compute which direction to travel. It also eliminates the need for row and column computations when finding a neighbor during each decision of next direction.

When attempting to determine which direction to move from the current cell, your MazeCrawler can examine each of the neighbors by accessing them via pointers. Then, once it makes a decision, it can simply follow that pointer to move to the neighboring cell. This moves our application one more step toward low-coupling, allowing our MazeCrawler to have absolutely NO knowledge of the internal representation of the Maze - all it needs is a pointer to the current cell!

Depending on your current implementation, you may or may not need to make changes to the Maze class as well as the MazeCrawler when modifying your MazeCell class to support these dynamic links. Ideally, after implementing dynamic links, your application could support Mazes of arbitrary shape and size.

Operator Overloading

You are also required to implement the extraction operator for the Maze class. The extraction operator should accept a stream, and read the maze from that stream. If the stream passed is a file stream, the file should already have been successfully opened.

General Tips Updated!

• There are several BIG changes that you will need to make, I would recommend starting small and then implementing the changes one by one. I would also recommend doing them in the following order (although, depending on your design you may want to reorder parts of this):
  • Add the overloaded insertion operators to MazeCell, Maze, and MazeCrawler, testing each one before moving onto the next.
  • Add the overloaded extraction operator to the Maze class.
  • Change the creation of the MazeCrawler to be dynamically allocated.
  • Add a constructor and the Big Three to the MazeCrawler class.
  • Add a constructor and the Big Three to the Maze class.
  • Modify the MazeCell class to have links to its neighbors.
  • Flesh out any other dynamic memory that needs to be completed.
  • Test your application between each change! Take it slow. Get everything else working before you try to implement the dynamic memory.
  • Submit a copy of your application BEFORE you start working on the dynamic memory.
  • Submit a copy of your application BEFORE adding the dynamic links (but after creating the Big Three for all three classes).
• 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/p3.
• 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.
• 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 Proj3 at the Linux prompt. This will compile all necessary .cpp files and create the executable named Proj3.

The make utility can also be used for compiling a single file without linking. For example, to compile Proj3.cpp, type make Proj3.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, Proj3 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 is 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 classes have the Big Three implemented.
• All dynamic memory is allocated and deallocated appropriately.
• All classes have an overloaded insertion operator.
• The Maze class has an overloaded extraction operator.
• All project requirements are met.

15% - Coding Standards