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 NNNN 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 10101010 maze:

ENTER --> 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 --> EXIT 

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:

Path: ([0][0], [1][0], [1][1], [1][2], [2][2], [3][2], [3][3], [4][3], [5][3], [6][3], [6][4], [6][5], [5][5], [4][5], [3][5], [2][5], [2][6], [1][6], [0][6], [0][7], [0][8], [1][8], [2][8], [3][8], [4][8], [5][8], [5][7], [6][7], [7][7], [8][7], [8][8], [8][9], [9][9]) ENTER --> x 1 1 1 0 0 x---x---x 0 | | | x---x---x 1 0 0 x 1 x 0 | | | 0 1 x 1 1 x---x 1 x 0 | | | 0 1 x---x 1 x 1 1 x 0 | | | 0 1 0 x 1 x 1 1 x 0 | | | 1 1 1 x 1 x 1 x---x 0 | | | 0 0 1 x---x---x 1 x 1 1 | 0 0 1 0 0 0 1 x 1 1 | 0 1 1 0 1 0 1 x---x---x | 0 0 0 0 1 0 1 1 0 x --> EXIT 

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

Create a search list for positions yet to explore, add the entrance (0,0), to this list While the list is not empty Remove the next position from the search list If it is the exit position, [n-1, n-1], then a path is found, construct the path and return the path. Otherwise, mark the position as visited, add all valid up, right, down, or left neighbor positions to the search list (in that order) If the list is empty and the method has not returned, there is no path 

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

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

maze4.txt ----------- 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

public static char [][] readMaze(String filename) throws IOException{ char [][] maze; Scanner scanner; try{ scanner = new Scanner(new FileInputStream(filename)); } catch(IOException ex){ System.err.println("*** Invalid filename: " + filename); return null; } int N = scanner.nextInt(); scanner.nextLine(); maze = new char[N][N]; int i=0; while(i < N && scanner.hasNext()){ String line = scanner.nextLine(); String [] tokens = line.split("\\s+"); int j = 0; for (; j < tokens.length; j++){ maze[i][j] = tokens[j].charAt(0); } if(j!=N){ System.err.println("*** Invalid line: " + i + " has wrong # columns: " + j); return null; } i++; } if(i!=N){ System.err.println("*** Invalid file: has wrong number of rows: " + i); return null; } return maze; } 

class Position{ public int i; //row public int j; //column public char val; //1, 0, or 'X' // reference to the prev position (parent) that leads to this position on a path Position parent; Position(int x, int y, char v){ i=x; j = y; val=v; } Position(int x, int y, char v, Position p){ i=x; j = y; val=v; parent=p; } } 

Sample Run

$ java PathFinder maze4.txt 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 stackSearch Solution: Path: ([0][0], [1][0], [1][1], [1][2], [2][2], [3][2], [3][3], [4][3], [5][3], [6][3], [6][4], [6][5], [7][5], [8][5], [8][6], [8][7], [8][8], [8][9], [9][9]) X 1 1 1 0 0 0 0 0 0 | X---X---X 1 0 0 1 1 0 0 | 0 1 X 1 1 0 0 0 0 0 | 0 1 X---X 1 0 1 1 0 0 | 0 1 O X 1 0 1 1 0 0 | 1 1 1 X 1 0 1 0 0 0 | O O 1 X---X---X 1 0 1 1 | O O 1 O O X 1 0 1 1 | O 1 1 O 1 X---X---X---X---X | O O O O 1 0 1 1 1 X queueSearch Solution: Path: ([0][0], [1][0], [1][1], [1][2], [2][2], [3][2], [4][2], [4][3], [5][3], [6][3], [7][3], [7][4], [7][5], [8][5], [8][6], [8][7], [8][8], [8][9], [9][9]) X 1 1 1 0 0 0 0 0 0 | X---X---X 1 0 0 1 1 0 0 | 0 1 X 1 1 0 0 0 0 0 | 0 1 X 0 1 0 1 1 0 0 | 0 1 X---X 1 0 1 1 0 0 | 1 1 1 X 1 0 1 0 0 0 | 0 0 1 X 0 0 1 0 1 1 | 0 0 1 X---X---X 1 0 1 1 | 0 1 1 0 1 X---X---X---X---X | 0 0 0 0 1 0 1 1 1 X