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. 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
For the first phase of the project, your boss requires that you implement
the following components of functionality:
- Do
- Prompt for and accept a maze filename from the user
- Read the maze from the file
- Print the maze
- Determine if the maze is solvable, print a message describing if it is
solvable or not. ("Unsolvable" or "Maze Solved")
- Print the maze with the path taken to solve it (as 'x's)
- While the user answers 'y' or 'Y' to whether there is another maze
Maze File
The file that stores the maze is formatted as follows:
<![CDATA[<Nbr of Rows> <Nbr of Columns>
<Maze row 1>
<Maze row 2>
...
<Maze row n>
]]>
- Nbr of Rows - the number of rows in the maze.
- Nbr of Columns - the number of columns in the maze.
- Maze - the exact representation of the maze, walls of the maze are
indicated by the '*' (asterisk) character, paths are the ' '
(space) character, the start is indicated by 'S', and end is indicated
by 'E'. Note that extra columns of ONLY spaces have been inserted
into each maze file to separate each column of the maze. These columns are NOT
part of the maze and are there for aesthetic purposes only (making a 21x21
maze look more "square").
The following guarantees can be assumed about the maze files we will
use to test your application:
- The maze file will be properly formatted
- The number of rows will be an integer. This number will be greater
than or equal to 3 (NbrOfRows >= 3). There is no maximum.
- The number of columns will be an integer. This number will be
greater than or equal to 3 (NbrOfCols >= 3). There is no maximum. This number
ignores the contribution of the spacing columns. For example, if the NbrOfCols
is 21, there are 21 maze columns and 20 spacing columns between the maze
columns.
- The number of rows and columns will be on the same line, with nothing
else
- The actual number of rows and columns in the maze will match the numbers
supplied
- There may be white space at the end of individual lines of the maze,
your program should ignore these spaces.
- There may be blank lines at the end of the maze file itself, your
program should ignore these lines
- There will be no blank lines between rows of the maze.
- There will be exactly ONE start position in the maze, indicated by
'S'
- The start will always be surrounded by 3 walls
- There may or may not be an end position in the maze, indicated by
'E'
- The end may or may not be surrounded by 3 walls
- Not all mazes will be solvable
- "Spacing" columns have been inserted into the file for aesthetic value
- All mazes have an odd number of rows and columns
- All mazes are rectangular or square in shape
User Interaction
The system is required to request the filename from the user. After processing
the file, the system is required to ask the user if there is another maze to
check. The user should reply with 'y' or 'Y' if there is, and anything else if
there is not. If the user would like to continue, then the system should
request another filename and repeat the above. This must be the only
input requested from the user. There are no guarantee made about the
existence of this file or whether there is anything at all in the file.
However, if there is anything in the file, it will be guaranteed to be
formatted as above.
If the user supplies a non-existant file or empty file, the system should
continue to reprompt for another filename until the user supplies an existing
file that has a maze in it. The system should NOT prompt the user for a 'y'
or 'Y' to process another maze at this point.
Solving a Maze
There is a relatively simple algorithm that can be used to guarantee finding
a solution to any maze that has a solution. The basic strategy is called the
"right-hand rule" - if you were walking the maze, you simply keep your right
hand in contact with a wall at all times. It requires some retracing of your
steps as you continue through the maze, but it guarantees that you will find
the End of the maze if it exists and is accessible from the Start position.
There are a variety of methods and algorithms for implementing this
strategy, but one algorithm that you may use is:
<![CDATA[
Until you find the end square or return to the start square
In the current square, facing in the direction you were previously heading,
If you can go right, do so
otherwise, if you can go forward, do so
otherwise, if you can go left, do so
otherwise, turn around and go back one square
]]>
The algorithm above is described with respect to the direction you are
currently heading. So, let us say that North is "up" in the maze, if you are
currently heading North, then when deciding which square to travel to next
you will first try to head East, then North, then West, then South in a
counter-clockwise motion. If you were originally heading South, then you would
attempt to go West first, then South, then East, then North. You should notice
that because of the guarantee that the start position will be unique and
surrounded by exactly 3 walls, it will not matter which direction you choose
initially.
There are many different ways to represent the data in this algorithm, use one
that makes sense to you. Enumerated types (C++ Primer lesson) might provide
a handy notation for determining which direction you're heading and which one
you want to go next.
You must implement the right-hand rule for solving these mazes.
Design and Implementation Requirements
Functions
This project is designed to give you ample opportunity to explore, experience,
and use functions with a variety of different styles of parameters. You MUST
use functions in this project whenever possible. If your main function is
longer than 25-50 lines or so - it is probably too long - you need to break
it apart. However, if your functions are all less than 5 lines, or several
look very similar, you may need to rethink/combine them.
- The proper use and implementation of functions is an important
part of this project (and your grade for this project). In particular,
- Your program must make adequate use of functions in keeping with
top-down design principles.
- The names of the functions are left to you, but poor naming
will lead to losing points, use descriptive names.
- Parameters must be passed to functions using the appropriate
technique (by value or by reference).
- The proper use of const and default values with
parameters are also necessary.
- Values must be returned from functions appropriately.
-
All functions called from main() or any other function, must be implemented in
a separate file named Proj1Aux.cpp. The prototypes for these
functions must be found in a file named Proj1Aux.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.
Example Input and Output
Examples have been provided in Ms. Wortman's public directory for this project
(location listed below).
Example Program Execution
<![CDATA[linux2[18]% Proj1
Please enter the name of the maze file
maze21x21.txt
* * * * * * * * * * * * * * * * * * * * *
* S * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * *
* * * * * * * * * * * * * * * *
* * * E *
* * * * * * * * * * * * * * * * * * * * *
Maze Solved!
* * * * * * * * * * * * * * * * * * * * *
* S * x x x * * *
* x * x * x * * * * * * * * * * *
* x * x * x * * * * *
* x * x * x * * * * * * * * * * *
* x x x * x * * * * * *
* * * * * x * * * * * * * *
* x * x x x * * * * * *
* x * x * * * * * * * * * * * * * * *
* x * x * x x x x x x x * * *
* x * x * x * * * * * x * * * * * *
* x * x x x * x x x * x * * * *
* x * * * * * x * x * x * * * * * *
* x x x * x x x * x * x * * * *
* x * x * x * * * * * x * * * * * *
* x * x x x * x x x * x * * * *
* x * * * x * x * x * x * * * * * * *
* x x x * x * x * x * x x x x x x x * *
* * * x * x * x * x * * * * * * * x * * *
* x x x * x x x * x x x x x x x x x x E *
* * * * * * * * * * * * * * * * * * * * *
Would you like to solve another maze?
Y
Please enter the name of the maze file
maze5x5.txt
* * * * *
* S * E *
* * *
* *
* * * * *
Maze Solved!
* * * * *
* S * E *
* x * x *
* x x x *
* * * * *
Would you like to solve another maze?
y
Please enter the name of the maze file
maze_noSol.txt
* * * * * * * * * * * * * * * * * * * * *
* S * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * *
* * * * * * * * * * * * * * * *
* * * * E *
* * * * * * * * * * * * * * * * * * * * *
Unsolvable!
* * * * * * * * * * * * * * * * * * * * *
* S * x x x * x x x * x x x x x x x x x *
* x * x * x * x * x * x * * * * * * * x *
* x * x * x * x * x * x * x x x x x x x *
* x * x * x * x * * * x * x * * * * * x *
* x x x * x * x x x * x * x * x x x * x *
* * * * * x * x * x * x * x * x * x * x *
* x * x x x * x * x x x * x x x * x * x *
* x * x * * * * * * * * * * * * * x * x *
* x * x * x x x x x x x x x * x x x * x *
* x * x * x * * * * * x * x * x * * * x *
* x * x x x * x x x * x * x * x * x x x *
* x * * * * * x * x * x * x * x * x * * *
* x x x * x x x * x * x * x * x * x x x *
* x * x * x * * * * * x * x * x * * * x *
* x * x x x * x x x * x * x * x * x x x *
* x * * * x * x * x * x * * * x * * * x *
* x x x * x * x * x * x x x x x x x * x *
* * * x * x * x * x * * * * * * * x * * *
* x x x * x x x * x x x x x x x x x * E *
* * * * * * * * * * * * * * * * * * * * *
Would you like to solve another maze?
N
]]>
Example Maze Files
<![CDATA[21 21
* * * * * * * * * * * * * * * * * * * * *
* S * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * *
* * * * * * * * * * * * * * * *
* * * E *
* * * * * * * * * * * * * * * * * * * * *
5 5
* * * * *
* S * E *
* * *
* *
* * * * *
21 21
* * * * * * * * * * * * * * * * * * * * *
* S * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * *
* * * * * * *
* * * * * * * * * * * * * * * *
* * * * E *
* * * * * * * * * * * * * * * * * * * * *
]]>
Data Structures
- Your program must use vectors instead of arrays, since you do not know
how large the maze may be.
- Your program must use cin/cout/getline instead of the C-style input and
output.
- Your program must use C++ strings instead of C-style strings (if you use
strings at all).
- Your program must use const variables rather than "magic numbers"
or "magic strings". Do not use #defines, use const variables instead. For
this project, examples of magic strings would be determining which square in
the maze has the 'S' - you should have a constant variable representing 'S'
and not use 'S' directly in your boolean expression.
<![CDATA[if (currentSquare == 'S')
]]>
is unacceptable, use:
<![CDATA[if (currentSquare == START)
]]>
where START is defined elsewhere.
- Although not required, you may find the use of one or more
structs helpful in organizing your data. You may use classes if you already
understand them, but their use is not required or recommended as you may be
required to rewrite them completely for Project 2.
- Because the maze file has strings that may contain spaces, the
use of the ignore( ) function may be necessary. See the class notes
on strings.
- Your program must provide adequate error checking of user input.
- Your program will be tested with a variety of good and BAD inputs.
- Get your project working with good input first. Then go back and put
in the error checking and error handling.
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/p1.
- 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
Your project design document for project 1 must be named p1design.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 Proj1
at the Linux prompt.
This will compile all necessary .cpp files and create the
executable named Proj1.
The make utility can also be used for compiling a single file without
linking. For example, to compile Proj1.cpp, type make Proj1.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, Proj1
executable and backup files created by the editor. More information about
these commands can be found at the bottom of the makefile.
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 variables are used wherever appropriate.
- All unmet function pre-conditions are handled.
- Use of efficient method for formatting hyphenated numbers.
- All project requirements are met.
15% - Coding Standards
Your code adheres to the
