C++ Maze ( I provided what I have so far for an answer at the bottom. ) ***** PL

Question

C++ Maze ( I provided what I have so far for an answer at the bottom. )

***** PLEASE DO NOT JUST COPY AND PASTE MY QUESTION AS THE ANSWER, I NEED HELP WITH THIS ASSIGNMENT ******

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:

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 specic 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 nd 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.

Step1. First check whether you are at the exit. If you are, you’re done (a very simple maze); if you are not, go to step 2.

Step2. Try to move to the square directly to the north by calling the function goNorth (step 3).

Step3. If goNorth was successful, you are done. If it was unsuccessful, try to move to the square directly to the west by calling the function goWest (step 4).

Step4. If goWest was successful, you are done. If it was unsuccessful, try to move to the square directly to the south by calling the function goSouth (step 5).

Step5. If goSouth was successful, you are done. If it was unsuccessful, try to move to the square directly to the east by calling the function goEast (step 6).

Step6. If goEast was successful, you are done. If it was unsuccessful, you are still done, because no path exists from the entrance to the exit.

The function goNorth will examine all the paths that start at the square to the north of the present square as follows. If the square directly to the north is clear, is inside the maze, and has not been visited before, move into this square and mark it as part of the path. (Note that you are moving from the south.) Check whether you are at the exit. If you are, you’re done. Otherwise, try to nd a path to the exit from here by try-ing all paths leaving this square except the one going south (going south would put you back in the square from which you just came) as follows. Call goNorth; if it is not successful, call goWest and, if it is not suc-cessful, call goEast. If goEast is not successful, mark this square as visited, move back into the square to the south, and return.

The following pseudocode describes the goNorth algorithm:

goNorth(maze, creature)

if (the square to the north is clear, inside the maze, and unvisited)

{

Move to the north

Mark the square as part of the path

if (at exit)

success = true

else

{

success = goNorth(maze, creature)

if (!success)

{

success = goWest(maze, creature)

if (!success)

{

success = goEast(maze, creature)

if (!success)

{

Mark square visited

Backtrack south

}

}

}

}

}

else

success = false

return success

The goWest function will examine all the paths that start at the square to the west of the present square as follows. If the square directly to the west is clear, is inside the maze, and has not been visited before, move into this square and mark it as part of the path. (Note that you are moving from the east.) Check whether you are at the exit. If you are, you’re done. Otherwise, try to nd a path to the exit from here by trying all paths leaving this square except the one going east (this would put you back in the square from which you just came) as follows. Call goNorth; if it is not successful, call goWest; and if it is not successful, call goSouth. If goSouth is not suc-cessful, mark this square as visited, move back into the square to the east, and return. The functions goEast and goSouth are analogous to goWest and goNorth. The input data to represent a maze is simple. For example, the previously given maze is represented by the following lines of input, which can be in a text le:

20 7 <- width and height of the maze in squares

0 18 <- row and column coordinate of maze exit

6 12 <- row and column coordinate of maze entrance

After the rst three lines of numeric data in the le, each of the next lines corresponds to a row in the maze, and each character in a line corresponds to a column in the maze. An x indicates a blocked square (part of the wall), and a blank indicates a clear square. This notation is convenient, because you can see what the maze looks like as you design it.

WORK SO FAR

Maze.cpp~

******************************************************
#include "Maze.h"
#include
using namespace std;
// Constructor
// Build a maze as given by the file filename
// Precondition: the file must be correctly formated
Maze::Maze(string filename)
{
// open the file
ifstream input(filename.c_str());
// the file must be open
assert(input);
// Dimensions of the maze
input >> col >> row;
// row and col must be positive
assert(row>0 && col>0);
// Dump the rest of the line
while(input.get()!=' ');
// Maze exit
input >> exit.r >> exit.c;
// exit.r and exit.c must be between row and col
assert(exit.r>=0 && exit.r assert(exit.c>=0 && exit.c // Dump the rest of the line
while(input.get()!=' ');
// Maze entry
input >> entrance.r >> entrance.c;
// entrance.r and entrance.c must be between row and col
assert(entrance.r>=0 && entrance.r assert(entrance.c>=0 && entrance.c // Dump the rest of the line
while(input.get()!=' ');
// Maze structure
// Create the maze on the heap: 2D array of row*col ints
maze = new int*[row];
for(int i=0; i maze[i] = new int[col];
// Read the maze line by line
string mazeLine;
for(int r=0; r {
// eof must not have been reached
assert(!input.eof());
getline(input,mazeLine);
for(int c=0; c {
// mazeline must be made of 'X' and ' ' only
assert(mazeLine.at(c)==' ' || mazeLine.at(c)=='X');
maze[r][c] = ((mazeLine.at(c)==' ')?CLEAR:WALL);
}
}
// The entrance and exit must not be blocked
assert(maze[entrance.r][entrance.c]!=WALL &&
maze[exit.r][exit.c]!=WALL);
// The creature is at the entrance
creature = entrance;
}
// Move the creature
// return true if the creature can move, false otherwise
bool Maze::goNorth()
{
// Location north of the creature
Location north=creature;
north.r--;
// if north is inside of the maze and the square
// at north is not a wall, we can move the creature
if (insideMaze(north) && square(north)!=WALL)
{
creature=north;
return true;
}
else
return false;
}
bool Maze::goSouth()
{
// Location south of the creature
Location south=creature;
south.r++;
// if south is inside of the maze and the square
// at south is not a wall, we can move the creature
if (insideMaze(south) && square(south)!=WALL)
{
creature=south;
return true;
}
else
return false;
}
bool Maze::goWest()
{
// Location west of the creature
Location west=creature;
west.c--;
// if west is inside of the maze and the square
// at west is not a wall, we can move the creature
if (insideMaze(west) && square(west)!=WALL)
{
creature=west;
return true;
}
else
return false;
}
bool Maze::goEast()
{
// Location east of the creature
Location east=creature;
east.c++;
// if east is inside of the maze and the square
// at east is not a wall, we can move the creature
if (insideMaze(east) && square(east)!=WALL)
{
creature=east;
return true;
}
else
return false;
}
// = Is the creature out?
bool Maze::isOut() const
{
return (creature==exit);
}
// Display a solution path from the current creature position
// to the exit of the maze
void Maze::showPath(ostream& out)
{
// =there is a path
bool success=false;
// Look for the path recursively
findPath(creature,success);
// print the path (if we found one0
if (success)
out << *this;
else
out << "There is no solution path";
// Remove the VISITED and PATH marks
// (set such squares to CLEAR)
for(int i=0; i for(int j=0; j if (maze[i][j]==PATH || maze[i][j]==VISITED)
maze[i][j]=CLEAR;
}
// Display the maze
ostream& operator<<(ostream& out,const Maze& m)
{
// X: wall
// C: creature
// : empty square
// .: path leading to the exit
// character on the square
char l;
for(int r=0; r {
for(int c=0; c {
switch(m.maze[r][c])
{
case CLEAR:
case VISITED:
l = ' ';
break;
case WALL:
l = 'X';
break;
case PATH:
l = '.';
break;
}
// Check for the creature
if (r==m.creature.r && c==m.creature.c)
l = 'C';
out << l;
}
out << endl;
}
return out;
}

// Private auxiliary functions
// ---------------------------
// Mark the square in row r and column c as visited
// Precondition: l must be inside of the maze
// there is no wall as l
void Maze::markSquareAsVisited(const Location& l)
{
assert(0<=l.r && l.r assert(maze[l.r][l.c]!=WALL);
maze[l.r][l.c] = VISITED;
}
// Mark the square in row r and column c as PATH
// Precondition: l must be inside of the maze
// there is no wall as l
void Maze::markSquareAsPath(const Location& l)
{
assert(0<=l.r && l.r assert(maze[l.r][l.c]!=WALL);
maze[l.r][l.c] = PATH;
}
// What is on square in row r and column c
// Precondition: l must be inside of the maze
int Maze::square(const Location& l) const
{
assert(0<=l.r && l.r return maze[l.r][l.c];
}
// Is this location inside of the maze?
bool Maze::insideMaze(const Location& l) const
{
return (l.c>=0 && l.c=0 && l.r }

// Recursively mark a path from l that leads to the exit (if any)
// Set success to true is there is such a path
void Maze::findPath(Location l, bool& success)
{
// This square is being visited
// Mark it as such
markSquareAsVisited(l);
// If it is the exit square, we are done
// Mark the square as part of the path
// set success to true
if (l==exit)
{
success=true;
markSquareAsPath(l);
return;
}
// try all possible moves from this square
// north, south, east and west
Location north=l; north.r--;
Location south=l; south.r++;
Location east=l; east.c++;
Location west=l; west.c--;
// If we haven't found the winning path yet and we can go north
// and we haven't been there already, look for the winning path
// starting from north
if (!success && insideMaze(north) && square(north)!=WALL &&
square(north)!=VISITED)
findPath(north,success);
// If we haven't found the winning path yet and we can go south
// and we haven't been there already, look for the winning path
// starting from south
if(!success && insideMaze(south) && square(south)!=WALL &&
square(south)!=VISITED)
findPath(south,success);
// If we haven't found the winning path yet and we can go east
// and we haven't been there already, look for the winning path
// starting from east
if(!success && insideMaze(east) && square(east)!=WALL &&
square(east)!=VISITED)
findPath(east,success);
// If we haven't found the winning path yet and we can go west
// and we haven't been there already, look for the winning path
// starting from west
if(!success && insideMaze(west) && square(west)!=WALL &&
square(west)!=VISITED)
findPath(west,success);
// If success is true, this location is part of a
// solution path. Mark the square as part of the path.
if (success)
markSquareAsPath(l);
}

Maze.h

******************************************************

// Maze ADT

#ifndef MAZE_H

#define MAZE_H

#include

#include

#include

#include "Location.h"

// A maze is made of row*col squares

// the state of a square can be

// CLEAR: the creature can move to the square

// WALL: the square is blocked (part of a wall)

// VISITED: the creature has already been on that square

// PATH: this square is part of a path that leads to the exit

//

const int CLEAR=0;

const int WALL=1;

const int VISITED=2;

const int PATH=3;

class Maze{

public:

// Constructor

// -----------

// Read the maze from the file filename

// The creature is at the entrance

Maze(std::string filename);

// Other public member functions

// -----------------------------

// Move the creature

// return true if the creature can be moved

bool goNorth();

bool goSouth();

bool goEast();

bool goWest();

// Is the creature out

bool isOut() const;

// Display a solution path from the current creature position

void Maze::showPath(std::ostream& out);

// friend function

// ---------------

// Display the maze

friend std::ostream& operator<<(std::ostream& out,const Maze& m);

private:

// Dimensions of the maze

int row;

int col;

// 2D array to represent the maze (on the heap)

int** maze;

// entrance and exit points of the maze

Location entrance;

Location exit;

// Location of the creature

Location creature;

// auxiliary functions

// -------------------

// find a winning path from l

// if found set success to true

void Maze::findPath(Location l, bool& success);

// Mark the square in row r and column c as VISITED

// Precondition: l must be inside of the maze

// there is no wall as l

void markSquareAsVisited(const Location& l);

// Mark the square in Location l as PATH

// Precondition: l must be inside of the maze

// there is no wall as l

void markSquareAsPath(const Location& l);

// What is on square in Location l?

// Precondition: l must be inside of the maze

int square(const Location& l) const;

// Is this location part of the maze?

bool insideMaze(const Location& l) const;

};

#endif

Location.h

******************************************************

// ADT location

#ifndef LOCATION_H

#define LOCATION_H

// simple struct to store a location in the maze

// r and c are the row and column of the location in the maze

struct Location{

int r;

int c;

// Comparison of 2 locations

bool operator==(const Location& l) const

{

return (r==l.r && c==l.c);

}

bool operator!=(const Location& l) const

{

return (r!=l.r || c!=l.c);

}

};

#endif

x xxxxx XxxxXxx XX X x xxx00xx xx x xxxooocxxoxxx

Explanation / Answer

#include<stdio.h>

#include<iostream>

#include <cstdlib>

#include<ctime>

#define FALSE 0

#define TRUE 1

using namespace std;

const int SIZE=12;

class Maze {

private:

char M[SIZE][SIZE]; // array of random numbers

int size; // size of the array

public:

Maze(); // constructor

void read_maze();

int maze_traverse(int row, int col);

void display_maze();

};

int main() {

int i, j;

Maze M;

M.display_maze();

M.maze_traverse(2,0);

M.display_maze();

}

// constructor

Maze::Maze() {

read_maze();

}

// constructor

void Maze::read_maze() {

int i, j;

FILE* ifp;

ifp=fopen("maze.txt", "r");

for(i=0; i< SIZE; i++)

for(j=0; j< SIZE; j++)

fscanf(ifp, " %c ", &M[i][j]);

}

int Maze::maze_traverse(int row, int col) {

// return TRUE if at the end of the maze

if (M[row][col] == 'E') return TRUE;

// return FALSE if not at the end of the maze

if (M[row][col] > SIZE-1 || M[row][col] == 'S') return FALSE;

// mark + for part of the path

M[row][col] = '+';

// return TRUE if the path goes to the North

if (M[row-1][col] == TRUE) return TRUE;

// return TRUE if the path goes to the South

if (M[row+1][col] == TRUE) return TRUE;

// return TRUE if the path goes to the East

if (M[row][col+1] == TRUE) return TRUE;

// return TRUE if the path goes to the West

if (M[row][col-1] == TRUE) return TRUE;

// mark x for the wrong path

M[row][col] = 'x';

return FALSE;

}

void Maze::display_maze(){

int i, j;

for(i=0; i<SIZE; i++) {

for(j=0; j< SIZE; j++)

printf("%c ", M[i][j]);

cout << endl;

}

cout << endl;

}

/*

// Pause the console so it doesn't close (when running in Windows)

cout << endl << endl << endl << endl << endl;

system("pause");

*/

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.