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
In this last iteration of the Maze Solver system, you will be required to use
templates and exceptions to enhance your application to handle a variety of
Maze formats and to more elegantly handle errors.
Functional Description
Basically, the functional requirements are the same as in previous projects.
Maze guarantees from Project 4 still hold. Functional requirements from
Project 4 also still hold, with the addition of a command-line variable.
Command-line Variables UPDATED!
Your application will accept one of the following parameters: STARS or BARS.
We will run your application with one of the following lines:
<![CDATA[
Proj5 STARS
Proj5 BARS
]]>
The STARS command-line variable indicates that you will use the star-based
Maze. The BARS command-line variable indicates that you will use the bar-based
Maze.
If the user enters something that you have not implemented on the command line,
simply alert the user and exit the program. For example, if you have not
implemented the extra credit, and the user attempts to use 'MAZE' on the
command line, simply alert the user and exit.
STARS Maze
The stars maze is the format you are already familiar with, where the '*'
character represents the walls and the 'S' and 'E' represent the start and end.
The following is an example of a STARS maze:
<![CDATA[
11 11
* * * * * * * * * * *
* S * * E *
* * * * * *
* * * * * * *
* * * * *
* * * * * * *
* * * *
* * * * * * * * *
* * *
* * * * *
* * * * * * * * * * *
]]>
BARS Maze UPDATED!
This maze is formatted almost identically to the STARS maze except that each
wall can either be one of any of these characters: '-', '_', '\', '|', '/'.
The start can be either 's' or 'S' and the end is represented
by a 'q' or 'Q'. The following is an example of a possible maze:
<![CDATA[
11 11
/ - - - - - - - - - \
| | | q |
| | | - - |
| - - - / | |
| S | - - |
| - - - - / |
| / - |
| - - - - - \ | |
| | |
| | | | |
\ - - - - - - - - - /
]]>
Notice that in the BARS maze, you cannot make assumptions about the
organization or placement of any of the wall characters.
Design and Implementation Requirements
You are not required to use dynamic memory for this assignment or polymorphism.
However, the functionality requirements of the previous project (including
the use of the three basic crawlers) must remain, but you need not retain the
polymorphism if you didn't get it working.
Templates
You must use templates to support the solving of stars and bars mazes. You
must create a new MazeCell class to support the new BARS mazes. Your Maze
and MazeCrawler classes must be templated on these two mazecell classes. Let
us pretend that you have named your MazeCell classes StarCell and BarCell. You
must create Maze and MazeCrawler objects as follows (obviously with whatever
variable names you would like to use, and wherever in your code they are
appropriate):
<![CDATA[
Maze<StarCell> maze;
Maze<StarCell>* maze;
Maze<BarCell> maze;
Maze<BarCell>* maze;
MazeCrawler<StarCell> crawler;
MazeCrawler<StarCell>* crawler;
MazeCrawler<BarCell> crawler;
MazeCrawler<BarCell>* crawler;
]]>
Exceptions
You must convert all of your application code to support the throwing of
Exceptions instead of your existing method of indicating errors. So whenever
you have a function or method that returns an error condition or discovers a
precondition that has not been met, it must throw an exception to be handled
either by the calling code or some other function/method in the stack. You
may handle the errors wherever appropriate, either in classes or in main or
both.
You must also support a hierarchical organization of Exception classes, you
must create at least three (3) exception classes. These can be as complicated
or as simple as you require, but they should have names that reflect the
error that occured. You may choose to inherit from the STL 'exception' class
or simply define your own base-class.
Your Exception classes can be declared and implemented in a single pair of
files named 'Exception.cpp' and 'Exception.h' (or any other names you like).
Extra Credit
You can implement neither, one or both of the extra credit components, but they
will be graded "all or nothing".
Parameterized MazeCell Class (10 pts)
In addition to supporting the above templated types, you must create a
completely parameterized MazeCell class that uses a collection of parameters
to specify what characters are used for walls, the start and the end. You
should use templates with multiple parameters to specify the following three
key components of any MazeCell:
- Wall character
- Start character
- End character
You must implement this as a separate class from the StarCell and BarCell
classes - so if you decide to implement this you will have three different
MazeCell-based classes. Hint: look at the non-type template parameters.
You will accept a few command-line parameters in order to demonstrate the
extra credit. The first is the keyword 'MAZE', followed by the wall character,
the start character and the end character. Here are some examples:
<![CDATA[
Proj5 MAZE * S E
Proj5 MAZE - Q W
Proj5 MAZE | m H
]]>
Best-First Search (10 pts)
Add a 6th option for a Crawler, where the Crawler determines which direction
to choose at each intersection by choosing the path that is "closest" to the
end square. Distance from the neighboring cell to the end cell should be
computed using the standard distance formula:
<![CDATA[
distance = square_root((x2 - x1)^2 + (y2 - y1)^2)
]]>
The Crawler should choose the neighboring cell that is both unvisited and
closest to the End. If the Crawler reaches a dead-end, it should backtrack.
This is a modified algorithm based on the Depth-first search strategy of the
previous project. The essential idea is that when attempting to choose a
neighboring direction, we believe that cells closer to the end are more likely
to lead us to a solution - this is called a "heuristic" and is often used in
Artifical Intelligence applications to make "wise" decisions. Heuristics are
actually a class of estimation algorithms that justify a choice based on some
numerical computation representing the likelihood that the choice is better
than all others.
This Crawler should be selected with number '6' on your main programming
menu. Its output should be like the Depth-First Crawler's output, 'x' or 'X'
on the path found, 'b' or 'B' on the backtracked paths, and the number of
squares visited (including start and end).
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 Proj5 files.
- Every time you add a class - modify the makefile to include a rule to
build and compile that class appropriately.
- Determine which exception classes you will need.
- Introduce the base-class of the exception hierarchy, converting every
error into a thrown exception.
- Compile and Test.
- Add additional levels to the Exception hierarchy and modify the
exceptions so that specific exceptions are thrown
- Compile and Test.
- Catch exceptions in appropriate places
- Compile and Test.
- Add the second MazeCell class (without adding templates, yet) and make
sure it will run on some new test mazes (that you create).
- Compile and Test.
- Convert the Maze and MazeCrawler classes to have templates based on
just your simple MazeCell class (the regular one).
- Compile and Test.
- Add the code necessary to use the BarCell class.
- Compile and Test.
- Once everything else is done, then try the extra credit. Best-first is
probably easier to start with, then the multi-parameter templates.
- 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/p5.
- 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
Your project design document for this project must be named p5design.txt.
Be sure to read the
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 Proj5
at the Linux prompt.
This will compile all necessary .cpp files and create the
executable named Proj5.
The make utility can also be used for compiling a single file without
linking. For example, to compile Proj5.cpp, type make Proj5.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, Proj5
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
This list may not be comprehensive, but everything on this list will be
verified by the graders.
- 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 used templates to support the new MazeCell classes.
- You have notified calling code of all errors by using Exceptions.
- You have created a hierarchy of Exception classes.
- All project requirements are met.
15% - Coding Standards
Your code adheres to the
