Homework #4

CS35 Fall 2000

Homework 4: Maze Path Searching
Due: Thursday, Feburary 28 before 2am

CONTENTS

You should work by yourself on this assignment.

PROBLEM DESCRIPTION

You are to implement two versions of an algorithm for finding a path through a rectangular maze; one version will use a stack, and the other will use a queue to store state information as the search algorithm proceeds.

A maze is 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 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 first prompt the user to enter the dimensions of the maze (M and N), then prompt the user to enter the set of (i,j) wall coordinates. 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.

You will represent a maze as a mxn array, 'maze', 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][m-1].

A path is represented by a sequence of maze[i][j] coordinates starting with maze[0][0] and ending with maze[n-1][m-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 one possible path through this maze: 
   Path: ( maze[0][0], maze[1][0], maze[1][1], maze[1][2], maze[2][2],
	   maze[3][2], maze[3][3], maze[4][3], maze[5][3], maze[6][3],
	   maze[6][4], maze[6][5], maze[5][5], maze[4][5], maze[3][5],
	   maze[2][5], maze[2][6], maze[1][6], maze[0][6], maze[0][7],
	   maze[0][8], maze[1][8], maze[2][8], maze[3][8], maze[4][8],
	   maze[5][8], maze[5][7], maze[6][7], maze[7][7], maze[8][7],
	   maze[8][8], maze[8][9], maze[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

GETTING STARTED

You should start by implementing the LinkedQueque class and testing that it works. Next, you will need to spend time developing an algorithm that solves this problem and designing your solution before you start coding it.

Your program will perform the following actions:

  1. First, it will prompt the user for the dimensions of the maze followed by a list of coordinates making up the internal walls of the maze.
  2. Next, you will print the maze to stdout, using '0' to indicated non-wall positions and '1' to indicate wall positions in the maze.
  3. Next, your program will search for a path from the maze entrance point to the exit point in the maze using one of the two versions of the path searching algorithm. The path searching algorithm will terminate either when it finds a path through the maze or when it determines that there is no path through the maze.
  4. Next, your program will either print an error message (if there is no path through the maze) or will print:
    1. The path as a list of (i,j) positions starting at the entrance point and ending at the maze exit point
    2. The length of the path
    3. The maze with the path coordinates indicated by 'X' characters.
  5. Finally, your program will search for a path from the maze entrance point to the exit point in the maze using the other of the two algorithms, and print the path or an error message indicating the results of the search as in step (4) above.

Here is some sample output from a program run.

The Path Finding Algorithm

You should implement the following algorithm for finding a path (the details are left for you to fill in): 
(0) Starting with the entrance position, (0,0), as the current 
    position in the maze, add the current position to the search list.
(1)  Try to remove the next element from the search list.
     (a) if the list is empty, then there is no path through the maze.
     (b) else, if it is the exit position, (m-1, n-1), then a path 
	 through the maze is found.
     (c) else, add all valid up, down, left, or right neighbor positions to 
	the search list and repeat step (1)

When implementing step (1c), think carefully about when a neighbor is "valid", and how you can ensure that your implementation of the algorithm terminates.

Implementation Details

In one version of this algorithm, you will use a queue of Position objects (designing the Position class is up to you) 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.

Data Structures

You will need to implement a LinkedQueque class that is a linked implementation of the Queue Interface from the book. You will use this in one version of your algorithm to add neighbor Positions and to remove the next position during the path search. We will give you a LinkedStack class that you can use as a guide for implementing LinkedQueue.

You will also need to design a Maze class that encapsulates all Maze state and operations. The maze class should have a data instance that is a 2-D array of int to represent the maze. An example, of some maze operations are the following (this is not a complete list):

Methods in your Maze class will use and/or return linked-list, queue, and stack data structures. For example, your path finding algorithms should return a linked list of Position objects representing the path through the maze.

In addition, we provide the following Java classes that you may use in your program (you are welcome to use all or none of these):