Navigating a Maze Using C++, Stacks Write a class named PathFinder to work with

ID: 3860937 • Letter: N

Question

Navigating a Maze Using C++, Stacks

Write a class named PathFinder to work with the class Position given below, that implements two versions of a path finding algorithm for finding a path through a square maze. One version should use a stack, and the other should use a queue to store list of positions to explore as the search algorithm proceeds.

The maze will be a square space with an entrance at the upper left-hand corner, an exit at the lower right-hand corner, and some internal walls.

Your algorithm will need to find a path through a given maze starting from the entrance and finishing at the exit that does not go through any walls.

Your program should take one command line argument, the filename (e.g. maze1.txt) for the maze description. Then, your program should print the maze to stdout, and try to find a path through the maze. If a path is found, the positions that make up the path should be printed to stdout, otherwise, an error message should be printed to the screen. The two versions of the path finding algorithm used may produce different results, so your program should print the paths that result from executing both implementations of the path finding algorithm.

The maze will be represented as an N×NN×N array of 11's and 00's; if maze[i][j] = ‘1’ then there is an internal wall in that position of the maze, otherwise there is no wall. The search algorithm should start at maze[0][0] and then find a path to maze[N-1][N-1].

The following is the array representation of a 10×1010×10 maze:

A path is represented by a sequence of [i][j] position coordinates starting with [0][0] and ending with [N-1][ N-1]. From a position (i,j)(i,j) in a path, the next position in the path can only be the position to the right, left, up, or down from position (i,j)(i,j); a path cannot move diagonally from one position to another.

Here is a possible path through the above maze:

Summary of Program Operation

Your program should perform the following actions:

Take the name of the maze file from command line.

Use the provided method readMaze to read the maze into the array representation and print the maze to stdout

Next, your program will search for a path from the maze entrance point to the exit point using both versions of the path searching algorithm: stackSearch and queueSearch.

For both of the search algorithms your program will either print an error message (if there is no path through the maze) or will print:

The path as a list of (i,j)(i,j) positions starting at the entrance point and ending at the maze exit point

The maze with the path coordinates indicated by 'X' characters and appropriate "lines" joining these 'X's.

The Path Finding Algorithm

In one version of this algorithm, use a queue of Position objects to enqueue neighbor elements and to dequeue the next element at each step. In the other version use a stack to push neighbor elements and to pop the next element at each step. Once you implement one version of the algorithm, you can implement the second version by simply copying the code to a new method and replacing the data structure used and the calls to enqueue/dequeue with push/pop.

To construct the path, you will need to keep track of the previous position (parent) that leads to each position on the explored paths. You can build linked lists to keep track of the explored paths. The Position class has been defined for you in the starter code below. It contains the position information and a reference to its previous (parent) Position on a path. This is similar to the Node class in a linked list which contains a data item and a reference to its next Node. When adding a neighbor position of the current position to the search list, you need to create a new Position object for the neighbor position to be added with a reference to its parent - note that the current position is in fact the parent of the neighbor position. When a path is found, you can traverse the linked list to construct the path.

Think carefully about when a neighbor is "valid", and how you can ensure that your implementation terminates.

Data Structures

Use C++

The maze is stored as a 2-dimensional array of char values defined as char[][]. You can see how to declare, initialize, and use 2-dimensional arrays in the provided method readMaze().

Files and Methods to Get Started

5
0 1 0 1 0
0 0 0 1 0
0 1 0 0 0
0 1 0 1 1
0 1 0 0 0

7
0 0 1 0 0 0 0
0 0 0 0 1 1 0
0 1 1 0 0 1 0
0 1 1 1 0 1 1
0 1 0 0 0 0 0
1 1 0 1 1 1 1
0 0 0 0 0 0 0

10
0 1 1 1 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0
0 1 0 1 1 0 0 1 0 0
0 1 0 0 1 0 1 1 0 0
0 1 0 0 1 0 1 1 0 0
1 1 1 0 1 0 1 0 0 0
0 0 1 0 0 0 1 0 1 1
0 0 1 0 0 0 1 0 1 1
0 1 1 0 1 0 1 0 0 0
0 0 0 0 1 0 1 1 0 0

10
0 1 1 1 0 0 0 0 0 0
0 0 0 1 0 0 1 1 0 0
0 1 0 1 1 0 0 0 0 0
0 1 0 0 1 0 1 1 0 0
0 1 0 0 1 0 1 1 0 0
1 1 1 0 1 0 1 0 0 0
0 0 1 0 0 0 1 0 1 1
0 0 1 0 0 0 1 0 1 1
0 1 1 0 1 0 0 0 0 0
0 0 0 0 1 0 1 1 1 0

Sample Run

maze1.txt
-----------

5
0 1 0 1 0
0 0 0 1 0
0 1 0 0 0
0 1 0 1 1
0 1 0 0 0

maze2.txt
-----------

7
0 0 1 0 0 0 0
0 0 0 0 1 1 0
0 1 1 0 0 1 0
0 1 1 1 0 1 1
0 1 0 0 0 0 0
1 1 0 1 1 1 1
0 0 0 0 0 0 0

maze3.txt
-----------

maze4.txt
-----------

Explanation / Answer

#include <iostream.h>
#include <stdlib.h>
#include <time.h>

enum Direction { DOWN, RIGHT, UP, LEFT };
const int MAX_DOTS = 100; // maximum possible dots for maze

void mazeTraversal( char [][ 12 ], const int, const int, int, int, int );
void mazeGenerator( char [][ 12 ], int *, int * );
void printMaze( const char[][ 12 ] );
bool validMove( const char [][ 12 ], int, int );
bool coordsAreEdge( int, int );

int main()
{
char maze[ 12 ][ 12 ];
int xStart, yStart, x, y;

srand( time( 0 ) );

for ( int loop = 0; loop < 12; ++loop )
for ( int loop2 = 0; loop2 < 12; ++loop2 )
maze[ loop ][ loop2 ] = '#';

mazeGenerator( maze, &xStart, &yStart );

x = xStart; // starting row
y = yStart; // starting col

mazeTraversal( maze, xStart, yStart, x, y, RIGHT );
return 0;
}

// Assume that there is exactly 1 entrance and exactly 1 exit to the maze.
void mazeTraversal( char maze[][ 12 ], const int xCoord, const int yCoord,
int row, int col, int direction )
{
static bool flag = false; // starting position flag

maze[ row ][ col ] = 'x'; // insert X at current location
printMaze( maze );

if ( coordsAreEdge( row, col ) && row != xCoord && col != yCoord ) {
cout << "Maze successfully exited! ";
return; // maze is complete
}
else if ( row == xCoord && col == yCoord && flag ) {
cout << "Arrived back at the starting location. ";
return;
}
else {
flag = true;

for ( int move = direction, count = 0; count < 4;
++count, ++move, move %= 4 )

switch( move ) {
case DOWN:
if ( validMove( maze, row + 1, col ) ) { // move down
mazeTraversal( maze, xCoord, yCoord, row + 1, col, LEFT );
return;
}
break;
case RIGHT:
if ( validMove( maze, row, col + 1 ) ) { // move right
mazeTraversal( maze, xCoord, yCoord, row, col + 1, DOWN );
return;
}
break;
case UP:
if ( validMove( maze, row - 1, col ) ) { // move up
mazeTraversal( maze, xCoord, yCoord, row - 1, col, RIGHT );
return;
}
break;
case LEFT:
if ( validMove( maze, row, col - 1 ) ) { // move left
mazeTraversal( maze, xCoord, yCoord, row, col - 1, UP );
return;
}
break;
}
}
}

bool validMove( const char maze[][ 12 ], int r, int c )
{
return ( r >= 0 && r <= 11 && c >= 0 && c <= 11 && maze[ r ][ c ] != '#' );
}

bool coordsAreEdge( int x, int y )
{
if ( ( x == 0 || x == 11 ) && ( y >= 0 && y <= 11 ) )
return true;
else if ( ( y == 0 || y == 11 ) && ( x >= 0 && x <= 11 ) )
return true;
else
return false;
}

void printMaze( const char maze[][ 12 ] )
{
for ( int x = 0; x < 12; ++x ) {

for ( int y = 0; y < 12; ++y )
cout << maze[ x ][ y ] << ' ';

cout << ' ';
}

cout << "Hit return to see next move";
cin.get();
}

void mazeGenerator(char maze[][ 12 ], int *xPtr, int *yPtr )
{
int a, x, y, entry, exit;

do {
entry = rand() % 4;
exit = rand() % 4;
} while ( entry == exit );

// Determine entry position

if ( entry == 0 ) {
*xPtr = 1 + rand() % 10; // avoid corners
*yPtr = 0;
maze[ *xPtr ][ 0 ] = '.';
}
else if ( entry == 1 ) {
*xPtr = 0;
*yPtr = 1 + rand() % 10;
maze[ 0 ][ *yPtr ] = '.';
}
else if ( entry == 2 ) {
*xPtr = 1 + rand() % 10;
*yPtr = 11;
maze[ *xPtr ][ 11 ] = '.';
}
else {
*xPtr = 11;
*yPtr = 1 + rand() % 10;
maze[ 11 ][ *yPtr ] = '.';
}

// Determine exit location

if ( exit == 0 ) {
a = 1 + rand() % 10;
maze[ a ][ 0 ] = '.';
}
else if ( exit == 1 ) {
a = 1 + rand() % 10;
maze[ 0 ][ a ] = '.';
}
else if ( exit == 2 ) {
a = 1 + rand() % 10;
maze[ a ][ 11 ] = '.';
}
else {
a = 1 + rand() % 10;
maze[ 11 ][ a ] = '.';
}

for ( int loop = 1; loop < MAX_DOTS; ++loop ) { // add dots randomly
x = 1 + rand() % 10;
y = 1 + rand() % 10;
maze[ x ][ y ] = '.';
}
}

//this code will generate a maze 30x15
#include <iostream.h>
#include <stdlib.h>
#include <time.h>

enum Direction { DOWN, RIGHT, UP, LEFT };
const int ROWS = 15, COLS = 30;

void mazeTraversal( char [][ COLS ], const int, const int, int, int, int );
void mazeGenerator( char [][ COLS ], int *, int * );
void printMaze( const char[][ COLS ] );
bool validMove( const char [][ COLS ], int, int );
bool coordsAreEdge( int, int );

int main()
{
char maze[ ROWS ][ COLS ];
int xStart, yStart, x, y;

srand( time( 0 ) );

for ( int loop = 0; loop < ROWS; ++loop )
for ( int loop2 = 0; loop2 < COLS; ++loop2 )
maze[ loop ][ loop2 ] = '#';

mazeGenerator( maze, &xStart, &yStart );

x = xStart; // starting row
y = yStart; // starting col

mazeTraversal( maze, xStart, yStart, x, y, RIGHT );
return 0;
}

// Assume that there is exactly 1 entrance and exactly 1 exit to the maze.
void mazeTraversal( char maze[][ COLS ], const int xCoord, const int yCoord,
int row, int col, int direction )
{
static bool flag = false; // starting position flag

maze[ row ][ col ] = 'x'; // insert x at current location
printMaze( maze );

if ( coordsAreEdge( row, col ) && row != xCoord && col != yCoord ) {
cout << endl << "Maze successfully exited! ";
return; // maze is complete
}
else if ( row == xCoord && col == yCoord && flag ) {
cout << " Arrived back at the starting location. ";
return;
}
else {
flag = true;

for ( int move = direction, count = 0; count < 4;
++count, ++move, move %= 4 )
switch( move ) {
case DOWN:
if ( validMove( maze, row + 1, col ) ) { // move down
mazeTraversal( maze, xCoord, yCoord, row + 1, col, LEFT );
return;
}
break;
case RIGHT:
if ( validMove( maze, row, col + 1 ) ) { // move right
mazeTraversal( maze, xCoord, yCoord, row, col + 1, DOWN );
return;
}
break;
case UP:
if ( validMove( maze, row - 1, col ) ) { // move up
mazeTraversal( maze, xCoord, yCoord, row - 1, col, RIGHT );
return;
}
break;
case LEFT:
if ( validMove( maze, row, col - 1 ) ) { // move left
mazeTraversal( maze, xCoord, yCoord, row, col - 1, UP );
return;
}
break;
}
}
}

bool validMove( const char maze[][ COLS ], int r, int c )
{
return ( r >= 0 && r <= ROWS - 1 && c >= 0 && c <= COLS - 1 &&
maze[ r ][ c ] != '#' ); // a valid move
}

bool coordsAreEdge( int x, int y )
{
if ( ( x == 0 || x == ROWS - 1 ) && ( y >= 0 && y <= COLS - 1 ) )
return true;
else if ( ( y == 0 || y == COLS - 1 ) && ( x >= 0 && x <= ROWS - 1 ) )
return true;
else
return false;
}

void printMaze( const char maze[][ COLS ] )
{
for ( int x = 0; x < ROWS; ++x ) {

for ( int y = 0; y < COLS; ++y )
cout << maze[ x ][ y ] << ' ';

cout << ' ';
}

cout << " Hit return to see next move";
cin.get();
}

void mazeGenerator( char maze[][ COLS ], int *xPtr, int *yPtr )
{
int a, x, y, entry, exit;

do {
entry = rand() % 4;
exit = rand() % 4;
} while ( entry == exit );

// Determine entry position
if ( entry == 0 ) {
*xPtr = 1 + rand() % ( ROWS - 2 ); // avoid corners
*yPtr = 0;
maze[ *xPtr ][ *yPtr ] = '.';
}
else if ( entry == 1 ) {
*xPtr = 0;
*yPtr = 1 + rand() % ( COLS - 2 );
maze[ *xPtr ][ *yPtr ] = '.';
}
else if ( entry == 2 ) {
*xPtr = 1 + rand() % ( ROWS - 2 );
*yPtr = COLS - 1;
maze[ *xPtr ][ *yPtr ] = '.';
}
else {
*xPtr = ROWS - 1;
*yPtr = 1 + rand() % ( COLS - 2 );
maze[ *xPtr ][ *yPtr ] = '.';
}

// Determine exit location
if ( exit == 0 ) {
a = 1 + rand() % ( ROWS - 2 );
maze[ a ][ 0 ] = '.';
}
else if ( exit == 1 ) {
a = 1 + rand() % ( COLS - 2 );
maze[ 0 ][ a ] = '.';
}
else if ( exit == 2 ) {
a = 1 + rand() % ( ROWS - 2 );
maze[ a ][ COLS - 1 ] = '.';
}
else {
a = 1 + rand() % ( COLS - 2 );
maze[ ROWS - 1 ][ a ] = '.';
}

for ( int loop = 1; loop < ( ROWS - 2 ) * ( COLS - 2 ); ++loop ) {
x = 1 + rand() % ( ROWS - 2 ); // add dots to maze
y = 1 + rand() % ( COLS - 2 );
maze[ x ][ y ] = '.';
}
}

Navigate

Navigating Faith and Work : Event planning is often hard work. At times things g

Navigating college. HI, I need help with assignment below. Write down a 800-word

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

Navigating a Maze Using C++, Stacks Write a class named PathFinder to work with

Question

Explanation / Answer

Related Questions

Navigate