Maze Solver

Goals: Understanding recursion

Design and implement an algorithm for solving a maze. Produce ASCII output indicating path.

The problem description is taken from Carrano Chapter 5 Problem 9 (Carrano Chapter 5, Problem 4 in 6th edition)

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 S        xx xx x
x xxxxxxxxxx	   x  
xxxxxxxxxxxxxxxxxxxx

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

When the solved maze is printed, you should get (without color)

Path: EEENNNEEEEEESEESSSEEENNNNN
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
xxxxxxxxxxxxxxxxxxxx

Above maze has "red *" to indicate path, "green star" to indicate starting location and "+" to indicate explored areas that are not part of the final path to exit.

The ASCII representation of the maze is important for debugging, but does not have to be exactly as above. The Path string has to exactly match the solution.

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

Implement the following class functions in Creature class:

Creature(int Row, int Col);
// returns a string in the form of NNEEN
// (where N means North, E means East, etc)
string solve(Maze &Maze);
bool atExit(const Maze &Maze) const;
Go in a specific direction -- these 4 functions will be similar
string goNorth(Maze &Maze);
string goSouth(Maze &Maze);
string goEast(Maze &Maze);
string goWest(Maze &Maze);
// prints current location of creature, for example C(7,3)
ostream &operator<<(ostream &out, const Creature &creature);

You may choose to have additional public or private functions as needed.

All functions in the .h file and in the .cpp files MUST have at least one line of documentation.

Starter Code

creature.h

#ifndef ASS3_CREATURE_H
#define ASS3_CREATURE_H

#include "maze.h"
#include < ostream >

class Creature {
public:
friend ostream &operator<<(ostream &Out, const Creature &Creature);

private:
int Row;
int Col;

public:
Creature(int Row, int Col);
string solve(Maze &Maze);
bool atExit(const Maze &Maze) const;
string goNorth(Maze &Maze);
string goSouth(Maze &Maze);
string goEast(Maze &Maze);
string goWest(Maze &Maze);
};

#endif

creature.cpp

#include "creature.h"

std::ostream &operator<<(std::ostream &Out, const Creature &Creature) {
return Out;
}

Creature::Creature(int Row, int Col) : Row(Row), Col(Col) {}

bool Creature::atExit(const Maze &Maze) const {
return true;
}

string Creature::solve(Maze &Maze) {
string Path;
return Path;
}

string Creature::goNorth(Maze &Maze) {
return "X";
}

string Creature::goWest(Maze &Maze) {
return "X";
}

string Creature::goEast(Maze &Maze) {
return "X";
}

string Creature::goSouth(Maze &Maze) {
return "X";
}

maze.h

#ifndef ASS3_MAZE_H
#define ASS3_MAZE_H

#include < ostream >

using namespace std;

enum CELL { CLEAR, WALL, PATH, VISITED };

class Maze {
friend ostream &operator<<(ostream &Out, const Maze &Maze);
private:
const static int MAX_SIZE = 100;
char Field[MAX_SIZE][MAX_SIZE];
int Width, Height;
int ExitRow, ExitColumn;
public:
explicit Maze(const string &FileName);
bool isClear(int Row, int Col) const;
void markAsPath(int Row, int Col);
void markAsVisited(int Row, int Col);
int getExitRow() const;
int getExitColumn() const;

};

#endif

maze.cpp

#include < fstream >
#include < iostream >
#include "maze.h"
#include < string >

using namespace std;

ostream &operator<<(ostream &Out, const Maze &Maze) {
for (int Row = 0; Row < Maze.Height; ++Row) {
for (int Col = 0; Col < Maze.Width; ++Col) {
Out << Maze.Field[Row][Col];
}
Out << endl;
}
Out << endl;
return Out;
}

// For Clion, need the following line in CMakeLists.txt so maze.txt is found
// at the same location as the cpp files
// # need to load data files from current directory as cpp files
// set(CMAKE_RUNTIME_OUTPUT_DIRECTORY ${CMAKE_CURRENT_SOURCE_DIR})
Maze::Maze(const string &FileName) {
ifstream InFile;
InFile.open(FileName);
if (!InFile) {
cout << "Unable to open file";
exit(1); // terminate with error
}
InFile >> Width >> Height;
InFile >> ExitRow >> ExitColumn;
string Str;
getline(InFile, Str);
for (int Row = 0; Row < Height; ++Row) {
for (int Col = 0; Col < Width; ++Col) {
InFile.get(Field[Row][Col]);
// cout << Row << ", " << col << ": " << field[Row][col] << endl;
}
getline(InFile, Str);
}

}

int Maze::getExitRow() const {
return ExitRow;
}

int Maze::getExitColumn() const {
return ExitColumn;
}

bool Maze::isClear(int Row, int Col) const {
return Field[Row][Col] == ' ';
}

void Maze::markAsPath(int Row, int Col) {
Field[Row][Col] = '*';
}

void Maze::markAsVisited(int Row, int Col) {
Field[Row][Col] = '+';
}

main.cpp

#include < iostream >

#include "creature.h"
#include "maze.h"

void test() {
Maze M("maze.txt");
// cout << m << endl;
Creature C(4, 4);
cout << "Path: " << C.solve(M) << endl;
cout << M << endl;
}
int main() {
test();
cout << "Done!" << std::endl;
return 0;
}