CS171 (Spring 2012)
Assignment 3: Finding a Path through a
Maze
Assigned: Wednesday, February 22
Due: Thursday, March 1, 11:59pm
Extended: Monday, March 5, 11:59pm
Requirement
You are to implement two versions
of an algorithm for finding a path through a square maze; one version will use
a stack, and the other will use a queue to store path information
as the search algorithm proceeds. A maze is 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 find a path through a
given maze starting from the entrance and finishing at the exit that
does not go through any walls (a path must go around walls).
Your
program will take from the command line argument the filename for
the maze description (size, walls). Your program next prints the maze to stdout, then it tries to find a
path through the maze. If a path is found, the positions in the path are
printed to stdout with a success message,
otherwise, an error message is printed to the screen. Your program will print
the paths that result from executing both implementations of the path finding
algorithm.
The maze will be represented as
an NxN array of ones and zeros; 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 will start at maze[0][0] and find a
path to maze[N-1][ N-1]. 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) in a path, the next position in the path can only be
the position to the right, left, up, or down from positions (i,j); a path cannot move diagonally from one
position to another. For example, the following is the array representation
of a 10x10 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 |
The following is
a possible path through this 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 |
Program Operation
Your program will perform the
following actions:
The Path Finding Algorithm
You should implement the
following algorithm for finding a path (some of the details are left for you to
fill in):
Create a search list for
positions yet to explore, add the entrance position, (0,0),
to the search 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
else mark
the position as visited, add all valid up, down, left, or right neighbor positions to the search list
If the list is empty and the
method has not returned, there is no path
In one version of this algorithm,
you will use a queue of Position objects to enqueue
neighbor elements and to dequeue
the next element at each step. The other version will 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 search
code to a new method and replacing the data structure used and the calls to enqueue/dequeue with push/pop.
Hints:
1. Think carefully about when a
neighbor is "valid", and how you can ensure that your implementation terminates
2.
To
construct the path, you need to keep track of the previous position (predecessor)
of each position on the explored paths.
One way is to store the predecessor for each position in a separate 2-dimensional
array. When you add all the valid
neighbors to the search list, you know the predecessor of these neighbors is
the current position and you can update the 2-dimensional array with this
information. Another way is to include
the predecessor as part of the Position object when adding a neighbor position to
the search list.
Data
Structures
You can use java.util.ArrayDeque
class for storing the search list. See the lecture notes (2/20) and the Java
API for examples of usage and documentation.
You should use a java
2-dimensional array of char to store the current maze values. You can see how
to declare, initialize, and use 2-dimensional arrays in the provided method readMaze.
Getting started:
1.
Download
the starter code PathFinder.java and understand it. It has the following methods that are already
implemented:
·
char
[][] readMaze (String filename): reads maze from file, returns
2-dimensional array with each entry containing a 0 (space) or 1 (wall)
·
printMaze (char [][] maze): prints the values 2-d maze array
nicely to stdout
·
main(): reads and prints a maze, find a path using stackSearch and queueSearch,
prints the path and the maze for each version of the algorithm. You do not need to change the main methods.
2.
Fill
in your implementation in the stackSearch, queueSearch, and printPath methods, test your program with the provided
mazes (maze1.txt, maze2.txt, maze3.txt, maze4.txt).
3.
Think
about the following questions (you do not need to submit the answers)
·
Why
do both versions of the algorithm work and why they sometimes output different
paths for some of the mazes?
Honor code
The
assignment is governed by the College Honor Code and Departmental Policy. Please
remember to have the following comment included at the top of the file.
/*
THIS CODE IS MY OWN WORK, IT WAS WRITTEN
WITHOUT CONSULTING
CODE WRITTEN BY OTHER
STUDENTS. _Your_Name_Here_
*/
Submission:
Your completed PathFinder.java should be placed
in your ~/cs171/hw3 directory which will be collected for grading.
Grading:
·
Program
does not compile: 0
·
Correct
usage of ArrayDeque to implement the stackSearch algorithm: 25 points
·
Correct
usage of ArrayDeque to implement the queueSearch algorithm: 25 points
·
stackSearch alg. correctly finds the path or returns null if no
path exists: 15 points
·
queueSearch alg. correctly finds the path or returns null if no
path exists: 15 points
·
The
path to exit (if any) is correctly marked in maze and printed: 20 points