Maze Solver 2

Goals: Understanding recursion, solving mazes, working with multiple ADTs

For this assignment, you will write a program that can solve a maze. The problem description is taken from Carrano Chapter 5 Problem 9 (Carrano Chapter 5, Problem 4 in 6th edition) which is linked to this assignment.

The maze is provided by a text file in the following format:

20 7
0 18

XXXXXXXXXXXXXXXXXX X
X     X       XXXX X
X XXXXX   XXXXX XX X
X XXXXX XXXXXXX XX X
X X          XX XX X
X XXXXXXXXXX XX    X
XXXXXXXXXXXXOXXXXXXX

The first 2 numbers are: width-of-maze height-of-maze

The next 2 numbers are: row-exit column-exit

x represents wall
space represents movable space

Unlike the textbook version, the entrance to the Maze is not specified as part of the maze.txt file but will be provided by Creature's location

When maze is printed, you should also add

* part of the path to exit
+ visited square not part of the path to exit

The following public functions need to be implemented:

// follows the format provided above printing the maze
ostream &operator<<(ostream &out, const Maze &maze);

// prints current location of creature, for example C(7,3)
ostream &operator<<(ostream &out, const Creature &creature);

bool Maze::IsClear(int row, int column) const;
bool Maze::IsWall(int row, int column) const;
bool Maze::IsPath(int row, int column) const;
bool Maze::IsVisited(int row, int column) const;

// mark the maze with *
void Maze::MarkAsPath(int row, int column);

// mark the maze with +
void Maze::MarkAsVisited(int row, int column);

// Maze constructor requiring a valid file name
explicit Maze::Maze(string mazeFile);

// returns a string in the form of NNEEN
// (where N means North, E means East, etc)
// that will let the creature get to the exit
// if creature cannot get to the exit, returns "X"
string Creature::Solve(Maze &maze);

// Creature constructor takes starting position
Creature(int row, int col);

You may choose to have additional public or private functions as needed. For example, you can pass the path-so-far by reference to a function like Creature::goNorth or you can return a path from that

You can assume that mazes will have less than 100 rows and 100 columns.

Textbook Problem

Do you know how to find your way through a maze? After you write this program, you will never be lost again! Assume that a maze is a rectangular array of squares, some of which are blocked to represent walls. The maze has one entrance and one exit. For example, if x's represent the walls, a maze could appear as follows:

XXXXXXXXXXXXXXXXXX X
X     X       XXXX X
X XXXXX   XXXXX XX X
X XXXXX XXXXXXX XX X
X X          XX XX X
X XXXXXXXXXX XX    X
XXXXXXXXXXXXOXXXXXXX

A creature, indicated in the previous diagram by o, sits just inside the maze at the entrance (bottom row). Assume that the creature can move in only four directions: north, south, east, and west. In the diagram, north is up, south is down, east is to the right, and west is to the left. The problem is to move the creature through the maze from the entrance to the exit (top row), if possible. As the creature moves, it should mark its path. At the conclusion of the trip through the maze, you should see both the correct path and incorrect attempts. Write a program to solve this problem.

Squares in the maze have one of several states: CLEAR (the square is clear), WALL (the square is blocked and represents part of the wall), PATH (the square lies on the path to the exit), and VISITED (the square was visited, but going that way led to an impasse).

This problem uses two ADTs that must interact. The ADT creature represents the creature's current position and contains operations that move the creature. The creature should be able to move north, south, east, and west one square at a time. It should also be able to report its position and mark its trail.

The ADT maze represents the maze itself, which is a two-dimensional rectangular arrangement of squares. You could number the rows of squares from the top beginning with zero, and number the columns of squares from the left beginning with zero. You could then use a row number and a column number to uniquely identify any square within the maze. The ADT clearly needs a data structure to represent the maze. It also needs such data as the height and width of the maze given in numbers of squares; the length of a side of a square, and the row and column coordinates of both the entrance to and the exit from the maze.

The ADT maze should also contain, for example, operations that create a specific maze given descriptive data that we will detail to display a maze, determine whether a particular square is part of the wall, determine whether a particular square is part of the path, and so on.

The search algorithm and its supporting functions are outside both of the ADTs creature and maze. Thus, the maze and the creature will be arguments that you must pass to these functions. If you are at the maze's entrance, you can systematically find your way out of the maze by using the following search algorithm. This involves backtracking - that is, retracing your steps when you reach an impasse.