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. 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

Functional Description

Modified Maze Guarantees

• Start cells will touch one or more walls (not guaranteed to be 3).
• End cells will touch one or more walls.
• There may be more than one path from start to end in the maze.
• There may be "loops" or "cycles" in the maze.
• Paths will be exactly 1-row and 1-column wide (ignoring the aesthetic spacing columns).
• Not all mazes will be solvable with all algorithms.
• Mazes will continue to have aesthetic spacing columns in the original maze file. Your project should continue to display these in all printed mazes.

Functional Modifications

• Request a mazefile from the user
  • If the mazefile doesn't exist - reprompt the user
  • If the mazefile is empty - reprompt the user
• Request one of 5 Maze Crawlers to use to solve the maze (1-5)
  • If the user selects 1, use the Right-Hand Crawler
  • If the user selects 2, use the Left-Hand Crawler
  • If the user selects 3, use the Random Crawler
  • If the user selects 4, use the Depth-First Crawler [extra credit]
  • If the user selects 5, use the Breadth-First Crawler [extra credit]
  • If the user selects something you have not implemented, alert them that they have chosen an invalid crawler and do not attempt to solve the maze, or print any results. You can assume that we will only use a single character for input, but it may be any character.
• Once the maze is solved,
  • Was the maze solved or unsolvable (by the chosen Crawler)?
  • Display the number of Cells traversed through or visited (including the Start and End cells, if found).
  • Display the solution path [each crawler has its own style]
• Request a 'Y' or 'y' response if the user would like to submit another maze to solve. A response of anything else should exit the program.

Design and Implementation Requirements

Inheritance

For the Right-Hand, Left-Hand, and Random Crawlers, when the crawler returns to the start, you can assume that the maze is unsolvable. For the extra credit crawlers, the algorithm will exhaustively search until an end is found.

The new Maze Crawlers are defined as such:

• Right-Hand Crawler - Continues to use the right-hand rule to solve mazes, this class will have the same functionality as your previous three projects. For the solution path, this Crawler prints the entire path traversed.
• Left-Hand Crawler - Uses the left-hand rule to solve mazes. At each intersection, the crawler "sticks to the left-hand wall", choosing to take a left as the first choice at every position in the maze. Remember - this algorithm (like the right-hand rule) is relative to the direction the crawler is currently headed in. For the solution path, this Crawler prints the entire path traversed.
• Random Crawler - This Crawler chooses a random direction at each intersection and does not follow any predictable pattern for solving the maze. Imagine that this Crawler is a rat, attempting to find cheese in a maze, it does not use any form of "intelligence" in determining which direction to choose. It is acceptable that this Crawler be unable to solve mazes that are actually solvable by SOME algorithm. For the solution path, this Crawler prints the entire path traversed. If run on the same maze several times in a row, the solution paths should look different for each attempt. You will have to do a little research to figure out how to use the appropriate functions. There are some examples in the text and online, search for the rand() function and you are sure to find many examples. You should "seed" your randomizer with a different value every time the application is run, look for the time() function, it will provide you a good seed.
• Depth-First Crawler [Extra Credit] - This Crawler uses a depth-first algorithm to determine if the maze is solvable. You will have to do research either online or in text books to find a good depth-first algorithm that you can adapt for this project. The general idea is to always try a new option at each intersection, follow that option until you reach the end or a dead-end, then backtrack to your last decision, and try another option. The algorithm pursues each decision as far as possible, avoiding paths that have already been examined until it finally reaches the End. This crawler should print the single solution path from Start to End as 'x' or 'X', and should print all squares that were backtracked through as 'b' or 'B'. The path found will not necessarily be the shortest path to the End.
• Breadth-First Crawler [Extra Credit] - This Crawler uses a breadth-first algorithm to determine if the maze is solvable. You will have to do research either online or in text books to find a good depth-first algorithm that you can adapt for this project. The general idea is to travel down all possible paths, without following any of them to the end of its path. This algorithm allows us to find the shortest path from Start to End since the first time the algorithm sees the End is the shortest path. This crawler should print the single shortest solution path as 'x' or 'X', and should print all other visited/considered squares as 'b' or 'B' (even though they weren't really backtracked-through).

Polymorphism

You will not receive full-credit for your polymorphism implementation if your classes do not group common actions at the base-class level and limit derived-class specific implementation to the derived-class level. Make intelligent decisions about where to include functionality. We will be looking to see that all common methods are implemented at the base-class level while derived-specific methods are implemented at the derived-class level.

You MUST use polymorphism to dynamically call the maze solving algorithm on a Crawler object (hint: use a base-class pointer to a derived-class object).

Obviously, there are many design-issues that we have left to you to decide what is the best way to implement this collection of classes. Remember to take advantage of code you have already written, "Great software developers reuse" [paraphrased from the Cathedral and the Bazaar]. We will be looking to see that you have reused code appropriately and limited the amount of code that you must rewrite throughout your inheritance hierarchy.

Short-hand requirements:

• You must implement at least one virtual method.
• You must implement at least one pure virtual method.
• You must polymorphically call the maze-solving algorithm on a Crawler object.
• You must reuse code.
• You must demonstrate the power of polymorphism.
• You must dynamically allocate Crawler objects.

Extra Credit

Breadth-First Crawler (10 pts)

Depth-First Crawler (10 pts)

General Tips

• 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):
  • Modify the makefile to work for your Proj4 files.
  • Every time you add a class - modify the makefile to include a rule to build and compile that class appropriately.
  • Create a single derived class - the Right Hand Crawler. Move methods that are right-hand specific to this new class, leave general functions in the base class. Get this single class working with the previous project test cases. Thoroughly test and debug it.
  • Add the Left-Hand Crawler. Get this class working with the previous project test cases. Thoroughly test and debug it.
  • Write a simple randomizing testing program - something that will allow you to experiment with the randomizing functions.
  • Add the Random Crawler. Get this class working with the previous project test cases. Thoroughly test and debug it.
  • Add the new functionality (deciding which Crawler to use to solve the maze). Thoroughly test and debug it.
  • Once everything else is done, then try the extra credit. Depth-first is probably easier to start with, then breadth-first.
• 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.
• 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 200 - 300 lines of code... don't procrastinate.
• Ms Wortman's public directory for this project is /afs/umbc.edu/users/d/a/dana3/pub/CMSC202/p4.
• 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 Proj4 at the Linux prompt. This will compile all necessary .cpp files and create the executable named Proj4.

The make utility can also be used for compiling a single file without linking. For example, to compile Proj4.cpp, type make Proj4.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, Proj4 executable and backup files created by the editor. More information about these commands can be found at the bottom of the 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++. Also, you MUST be sure to use the same compiler for compiling ALL of your files - different compilers make different .o files and they will NOT play well together.

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.
• You have implemented at least one virtual method.
• You have implemented at least one pure virtual method.
• You have polymorphically called the maze-solving algorithm on a Crawler object.
• You have reused code.
• You have demonstrated the power of polymorphism.
• You have dynamically allocated Crawler objects.
• All project requirements are met.

15% - Coding Standards