CS35 Lab4: Maze Solver

Due 11:59pm Wednesday, February 16th

A skeleton version of the programs will appear in your cs35/lab/04 directory when you run update35. The program handin35 will only submit files in this directory.

You may work with a partner on this lab. If you work with a partner, be sure that both of your names appear at the top of every file. In addition, only one of you will need to run handin35.

Dynamically resizing Arrays
Before we begin the main part of the lab, you need to improve the implementation of the ArrayStack and ArrayQueue classes, so they can grow when the array is full. The basic outline for doing this is 
Create a new, bigger array
Copy elements from old array to new array
update any necessary metadata (tos, ifront, irear, capacity, ...)
Remove old array 
point old array pointer to new array
Implement this algorithm as a void grow() method in the ArrayStack and ArrayQueue classes. Remember to modify both the .h and .inl files and TEST you work before proceeding. Should your new method be public or private? Add a comment in you code explaining your answer.
Introduction

For this lab you will implement two versions of an algorithm for finding a path through a maze. One version will use a stack to conduct a depth-first search, and the other will use a queue to conduct a breadth-first search.

Each maze will be a rectangular space with an entrance at the upper left-hand corner, an exit at the lower right-hand corner, and some internal walls. Your algorithm must find a path through a given maze starting from the entrance and finishing at the exit, without passing through any walls. The algorithm may move through the maze by going up, down, left, or right, but not diagonally.

For example, below is a depiction of one possible maze. The zeros represent open spaces, the ones represent walls, and the asterisks represent a path found from the start to the end of the maze. 

Start-->  *  *  *  O  O 
          1  1  *  1  1 
          O  *  *  O  O 
          O  *  1  1  1 
          O  *  *  *  *  <--End

Path:(0, 0) (0, 1) (0, 2) (1, 2) (2, 2) (2, 1) (3, 1) (4, 1) (4, 2) (4, 3) (4, 4)

Locations in the maze are indexed by row and column. In the example above, the maze is 5 by 5. Position (0,0) is the upper left-hand corner and serves as the starting location. Position (rows-1, cols-1), which in this case is (4, 4), is the lower right-hand corner and serves as the ending location.

Each run of the program will begin by asking the user to designate where the walls should be positioned within the maze. Next the program will attempt to find a path using both a stack and a queue, and report the results. Initially you should begin with smaller mazes, such as 5 by 5. Later you may want to try larger mazes, such as 10 by 10. Below are two sample runs to demonstrate how the program should operate.

Sample run with a successful search
This program will attempt to find a path through a maze.
The program will first ask you for the size of the maze.
Then the program will ask you for the location of the walls in
the maze. Finally it will show the path if found or indicate that
no path is possible.

Enter the number of rows in the maze: 5
Enter the number of columns in the maze: 5

Enter the location of the walls as a list of row column pairs.
Each pair should be on a single line, separated by a space.
After the last wall location, enter a -1 on a line by itself.

1 1
1 2
1 3
3 1
3 2
3 3
3 4
-1


Start-->  O  O  O  O  O 
          O  1  1  1  O 
          O  O  O  O  O 
          O  1  1  1  1 
          O  O  O  O  O  <--End

Searching with stack... found path:

Length: 17
(0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (1, 4) (2, 4) 
(2, 3) (2, 2) (2, 1) (2, 0) (3, 0) (4, 0) (4, 1)
(4, 2) (4, 3) (4, 4) 

Start-->  *  *  *  *  * 
          O  1  1  1  * 
          *  *  *  *  * 
          *  1  1  1  1 
          *  *  *  *  *  <--End

Searching with queue... found path:

Length: 9
(0, 0) (1, 0) (2, 0) (3, 0) (4, 0) (4, 1) (4, 2) (4, 3) (4, 4) 

Start-->  *  O  O  O  O 
          *  1  1  1  O 
          *  O  O  O  O 
          *  1  1  1  1 
          *  *  *  *  *  <--End
Sample run with a failed search
This program will attempt to find a path through a maze.
The program will first ask you for the size of the maze.
 Then program will ask you for the location of the walls in
the maze.  Then it will show the path if found or indicate that
no path is possible.

Enter the number of rows in the maze: 5
Enter the number of columns in the maze: 5


Enter the location of the walls as a list of row column pairs.
Each pair should be on a single line, separated by a space.
After the last wall location, enter a -1 on a line by itself.
3 0
2 1
1 2
0 3
-1

Start-->  O  O  O  1  O 
          O  O  1  O  O 
          O  1  O  O  O 
          1  O  O  O  O 
          O  O  O  O  O  <--End

Searching with stack, no path found.
Searching with queue, no path found.
Getting started
We will represent the maze as a two-dimensional array of Position objects. As we search through the maze we will store Position *'s on the stack or queue.
  1. Position class
    The Position class is used to store all of the relevant information associated with a location in the maze, such as the row and column, whether it contains a wall, and whether it is on the found path.
    • Use the position.h file as a guide to creating the implementation of this class in the file position.cpp. You may add more methods as you see fit.
    • Write a simple test program to try out all the of functionality of this class before moving on.
  2. Maze class
    The Maze class is used to store the maze itself.
    • Use the maze.h file as a guide to creating the implementation of this class in the file maze.cpp. Start by implementing the simpler methods that access data in the class and print. You can comment out the other method declarations at first. You may add more methods as you see fit.
    • Write a test program in the solveMaze.cpp file to try to print out the maze, which will initially have no walls.
    • Add the functionality to solveMaze.cpp to allow users to designate the locations of walls. Test this and print the updated maze.
    • Now you are ready to tackle the search related methods of the Maze class: adjPosition, findNext, and reportPath. Once you have added them to the maze.cpp file, test these methods directly before trying to use them to search.
  3. Search technique
    Once you are confident that the Position class and the Maze class are working properly, you can implement the search in the solveMaze.cpp file. Below is the pseudocode for the search algorithm you should use. Remember, you'll need to write one version of this to use with the stack and another version to use with the queue. 
    add start location to the data structure
make start location as visited 
while (data structure is not empty) 
   current = remove location from data structure
   if (current is goal location)
       report the path
       return
   for each valid adjacent location
       set previous to current
       mark location as visited
       add to the data structure
report that no path exists
    Note that valid locations are ones that:
    • are up, down, left, or right from the current location
    • are within the bounds of the array
    • do not contain walls
    • have not already been visited
Submit
Once you are satisfied with your code, hand it in by typing handin35. This will copy the code from your cs35/lab/04 to my grading directory. You may run handin35 as many times as you like, and only the most recent submission will be recorded.