Description
File(s) to be submitted: proj5.cpp, maze.h, maze.cpp, makefile
Objectives: 1) Use recursion; 2) Understand and apply backtracking to solve a problem.
Project description:
Write a C++ program that, given a starting point, finds its way out of a maze, using recursion. The maze’s map will be
read from a file at the start of the program. Your code must work for all legal mazes. The maze is a rectangular grid
represented as a 2D standard C++ array, and the exit (if there is one) is on an outer row or column of the play area (nonred cells below).
The program should run until the exit to the maze is found or until it determines that there is no exit
(after exploring all traversable/navigable cells). Exploration of the maze is done by recursively invoking a function and
marking the cells visited with a special character (an electronic bread crumb to keep from reprocessing explored cells).
The legal moves are to cells adjacent to the current cell, but not diagonal to it. The order in which adjacent cells must be
explored is given below. The maze should be solved through recursive calls and backtracking, and not by looking ahead
(you do not have the ability to “look” into neighboring cells before moving – you simply move and rely on backtracking if
it’s a “bad” move).
If the specially marked exit cell is encountered the game should print a message that the exit was
found. Otherwise, after exploring the whole maze, a message is output stating that there is no exit.
X X X X X X X X X X
X * * * O X X X O X
X X X O O O O O O X
X O O O X X X O E X
X O X O O O O O X X
X O O O O O X X X X
X X O X O O O O O X
X X O X O X O X O X
X O O X O O O X O X
X X X X X X X X X X
N
W ⌂ E
S
At left is an instance of a maze. Note the attributes of a legal maze:
Cells are referred to as row #, column #. Row numbers increase
downward, and column numbers increase to the right.
The upper left cell of the “play area,” (cell 1,1) cannot be the exit, and
must always be a traversable cell and may not be “boxed in” by walls on
all sides – This is the player’s starting point.
X marks non-traversable cells
The cells in red are not part of the maze map read from the file,
but must be constructed around it and represented in the array.
They mark the boundary of the maze, and are represented as not
traversable. The maze will always have two more columns and
two more rows than the play area read from the file (the maze at
left has an 8×8 play area and is shown in a 10×10 array).
Blue squares are walls and are also non-traversable.
O cells (green) are traversable cells not yet visited. Traversable cells (and
the exit) must be reachable from any other traversable cell.
* (yellow) shows traversable cells that have been previously visited.
E marks the exit (outlined gray cell) – If there is one, it must be on one of
the outer rows or columns of the play area, and must be reachable from
any traversable cells in the maze (it can’t be contained within walls).
You must explore the maze in the following order: North, East, South, and
then West. Assuming you begin at the home plate cell (⌂) shown at left,
you must explore in this order: N, E, S, W.
Requirements:
1. Your program must be split into 3 files. There will be a class (with separate interface and implementation files), and a
driver file.
The requirements for these are specified below:
a) The Maze class – This class represents a maze
Files must be named maze.h and maze.cpp
Class must be named Maze
The interface (header file) is provided.
i. You should implement the interface file in a .cpp implementation file
ii. All data members must be of the type and size specified in the header file
iii. All member functions in the interface file must be implemented as declared – However you have
flexibility in how you choose to implement the body of functions, including choice of local variables.
The constructor will accept a file object argument and will read the file and construct the maze.
The file contains a rectangular maze no larger than 8 cells by 8 cells – your code must be able to
handle all mazes from those having a minimum of two rows (2×1) or two columns(1×2) up to the
maximum 8×8. The first line in the file has the dimensions of the maze (# of rows followed by #
of columns, separated by a space). An example maze file (4 rows by 4 columns) is shown below.
Note: There are no spaces between cell legend symbols in the input file.
4 4
OOOX
XOXX
XOOX
XXEO
The Print() function outputs the maze’s current state (using the legend above, including cells
visited thus far). It must only be output in unvisited traversable cells. See sample output.
The FindExit() function is a recursive function that explores the maze. It has two int parameters
indicating the player’s current row and column (in that order), and a bool reference variable that
represents whether or not the exit has been found.
The exploration of the maze will always
begin at row 1, column 1 (which must thus be a traversable grid cell). This function must rely on
recursion to explore the maze and to backtrack. It is a void function and you MAY NOT use a
return or break statement in it. Write the code so that it flows naturally.
You should consider
the 4 questions to ask when planning to use recursive algorithms, as you design your approach:
How are smaller instances of the problem defined?
How does each recursive call make the problem instance smaller?
What condition(s) can serve as the base case(s)?
Will the smaller instances of the problem reach the base case(s)?
b) A driver, or client, file
Must be named proj5.cpp
Must declare the file object containing the maze map. The maze is read from a file named maze.txt, which
is contained in the same folder as the source files.
Must instantiate maze
Must invoke the FindExit function, beginning at cell 1,1.
Outputs an appropriate message “Found exit!” or “No exit!”, based on the outcome of maze exploration.
2. Sample output:
a) This output show possible program executions with the player starting at cell 1,1 – The Exit case is from the 4×4
maze file shown above. The No Exit case results from converting the ‘E’ in the maze file to an ‘O’.
Case with Exit Case with No Exit
3. Test your program – Use different maze configurations, with and without exits.
4. Code comments – Add the following comments to your code:
A section at the top of the source file(s) with the following identifying information:
Your Name
CSCI 3110-00X (your section #)
Project #X
Due: mm/dd/yy
Below your name add comments in each file that give an overview of the program or class.
Place a one or two-line comment above each function that summarizes the workings of the function.
5. Rubric
Requirement Points Off
Maze Class
Class name -5
Include guards -3
Constructor – number, types, and order of parameters -5 (per item)
Constructor – file correctly read and maze correctly built (including outer boundary) -15
FindExit – correct function signature -5
FindExit – correctly handles wall cells -5
FindExit – correctly handles previously visited cells -5
FindExit – avoids look-ahead -5
FindExit – explores maze in specified order -10
FindExit – utilizes recursion and backtracking to solve the maze -15
FindExit – invokes Print function only in appropriate cells -5
FindExit – correctly terminates exploration (does not overexplore the maze) -10
FindExit – correctly sets/uses bool reference variable -5
Print – correct output -10
Driver/Client
main – input filename -5
main – correctly opens input file -5
main – correctly instantiates Maze object -10
main – correctly invokes the maze’s FindExit function -5
main – correctly outputs the outcome of exploring the maze -5
general – Does not compile (on ranger using Linux g++ compiler, and the provided makefile) -25
general – Runtime crash -35
general – Other TBD
