Project 5: Find Your Way Out! Solution

Assignment ID: proj5




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 (non-red 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


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






























































X




*




*




*




O




X




X




X




O




X










































downward, and column numbers increase to the right.






























































X




X




X




O




O




O




O




O




O




X


 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


X




O




O




O




X




X




X




O




E




X












































































































all sides – This is the player’s starting point.


X




O




X




O




O




O




O




O




X




X










































 X marks non-traversable cells






























































X




O




O




O




O




O




X




X




X




X


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


X




X




O




X




O




O




O




O




O




X


























































































They mark the boundary of the maze, and are represented as not
































































X




X




O




X




O




X




O




X




O




X












































traversable. The maze will always have two more columns and
































































X




O




O




X




O




O




O




X




O




X




two more rows than the play area read from the file (the maze at


X




X




X




X




X




X




X




X




X




X


left has an 8x8 play area and is shown in a 10x10 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.







N




W ⌂ E




S

* (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:




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:



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.

You should implement the interface file in a .cpp implementation file



All data members must be of the type and size specified in the header file



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 (2x1) or two columns(1x2) up to the maximum 8x8. 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)?



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.
Sample output:



This output show possible program executions with the player starting at cell 1,1 – The Exit case is from the 4x4 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







Test your program - Use different maze configurations, with and without exits.



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.



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