Traverse the Maze

Due 04/05/2018

The Problem

The programming problem in this project is to find a path from the entry cell (upper left corner) to the exit cell (lower right corner) of a maze. In our model the maze is represented by a rectangular grid of cells. Each cell is bordered by 4 walls, and some of these walls are passable to the neighboring cell(s). The outside wall of the whole maze is not passable. There are however (at least) two very different interpretations of a passable wall. In a directed maze the passage from a cell A to one of its neighbors B allows but does not imply that the wall is passable in the reversed direction from B to A, as well. On the other hand, in an undirected maze each passage provides a two-way access. In this project your program shall exercise both options of building a maze, moreover in the directed maze every passage will be selected by a given probability, while the undirected maze will be built upon a pattern of predetermined passable walls. Your completed program builds a maze based upon input wall pattern read from a file builds a maze with a random selection of all relevant directional passage finds a path through a maze if such a path exists displays the maze solution on the console showing the length of the path and the locations of the cells along the path from the entry cell to the exit cell failure of the search is reported in an output message

A representation of the maze and the solution on a graphical grid (console or GUI) is optional and does not earn bonus points. In the attached Figures.doc file there are illustrations for some of the requirements specified below in this project description.

Analysis and requirements

1. Searching for a path Searching or traversing a maze, or a graph data structure in general, applies one of the two well-known algorithms called breadth-first and depth-first. Breadth-first usually relies upon a queue data structure to control the search, while depth-first applies a stack for the same purpose. In this project the depth-first algorithm shall be implemented. The stack shall be a linked list. The purpose of the stack is to store a sequence of cells from the entrance to the current top such that the sequence is potentially extendible to form a path connecting entrance to exit. The logic of the search is quite simple: The process starts with an empty stack and entrance is pushed on the stack. Each cell pushed on the stack is marked as visited. If the search finds a visited cell, the cell will be ignored. If a neighbor cell is found accessible from the current top, the cell will pushed on the stack. If none of the accessible neighbors is unvisited the stack is popped. The process ends if exit is visited or the stack is emptied. Accordingly, the pseudo-code runs as follows push entrance on the stack and mark it visited while stack is not empty and path was not found peek the stack if top is exit mark that path found an break the iteration if top has no more neighbor to check pop the stack otherwise while there is a neighbor to check check the next neighbor if a neighbor is accessible and not visited, push the neighbor cell on the stack and mark it as visited break the neighbor check loop repeat until exit found or stack empty

2. Input Dimensions of the rectangular grid of cells stored in a 2-dimensional array (Figures 2, 3) A listing of passable cell connections (Figures.doc) A value of passage probability in case of a random model (Figure 1)

3. Output In case of successful search display the number of cells in the path and the array indices of the cells of the path listed from entrance to exit (see Figures 5, 6, 7) Otherwise display a message reporting the unsuccessful search (see Figure 4)

Design

1. Classes covering responsibilities for this project are Maze. This class is the focus of our project, it contains a 2-dimensional array of cell elements that represents the maze itself. The class is responsible for the search and for displaying the result Cell. Cell objects are the elements in the maze array. When the maze is built, each cell knows which ones of the four neighbors (two or three along the border of the maze) are accessible from it, and the cell also knows its coordinates in the maze (row and column index). Stack. A Stack object also contained by Maze is the main tool of the search process. The class must be implemented as a generic linked stack. The class is standard except for one added method display( ). This method prints the data stored in the stack from bottom up to top in the console, that is the toString( ) return value (the coordinates) of the cells. Since the linked stack does not maintain a tail reference, you must implement display( ) as a recursive method Node. Only a minimum of a Node class is needed for the sake of supporting Stack. The data in a Node object will be a Cell object. Node must also be implemented as a generic class MazeBuilder. A service class containing two static methods that build the maze, that is establish passage for the cells. Applications. The class of the main method.

Partial specification of the required classes supplied below.

2. Cell FIELDS You may apply package access on the fields. If you make them private define getters and setters as needed row : int to store the row and column index of the cell when it is added to the maze array column : int

visited : boolean changed to true when the cell has been visited in the search process

neighbor: Cell[ ] An array of length 4 to store the accessible neighbors of this cell. The north, east, south and west neighbors are stored at index 0, 1, 2, 3 in order. neighbor[k] is null if that neighbor does not exists or there is no passage from this cell to neighbor[k]

lastOut: int recommended to store information on the last neighbor checked for passage in the search process; for instance if neighbor[1] has been checked but neighbor[2] not yet, then lastOut stores value 1

Note that a cell object is a kind of super node that contains four links rather than one

METHODS Cell (row: int, col: int) constructor; initializes the fields row and colum

toString() : String returns a String containing the coordinates row and column

3. Maze FIELDS You may apply package access on the fields. If you make them private, define getters and setters as needed entrance: Cell exit: Cell

grid: Cell[ ][ ] A 2-dimensional array of cells to represent the maze

rows : int to store the dimensions of the grid array columns : int

pathFound : boolean changed to true when the search reached exit

path: Stack Instantiated at declaration as a Cell type stack of the generic Stack class

METHODS Maze ( grid: Cell[ ][ ] ) constructor; initializes the grid array assigns grid dimensions assigns entrance and exit

findPath() : void implements the search (see the pseudo-code); depending on pathFound creates output messages; displays the output using JOptionPane message dialogs and the console, see the output templates below

4. Stack Implement the class with a generic parameter. Consult and follow the generic LinkedStack class in your reading book pp342-344. Modifications: default constructor needed only ignore the clone( ) method, not needed in this project modification of size( ) method is necessary since the supporting Node class in our project has no methods but the constructor. Rather than calling listLength( ) adopt the listLength( ) code with the necessary changes (see p195 for the nongeneric template) modify pop( ) such that it returns the data of the popped top implement the recursive display( ) method; hint: the base case is the empty stack when the method returns; otherwise pop the stack, save the popped value in a local variable, call display( ) , print the saved value

pp324-344 in the book

5. Node Implement with a generic parameter. Declare the two fields as usual and define the initializer constructor as usual. No other methods needed. Attach Node after the Stack class as a non-public class.

6. MazeBuilder This class is responsible for setting up the passage relations between cell neighbors. The class contains two static methods and no other members. Both methods create and return a 2-dimensional array of connected cells that is, a fully established maze. (i) loadMazeRandom( ): return type Cell[ ][ ], no parameter solicits and stores a probability input value p, see Figure 1 solicits and stores the intended array dimensions, see Figure 2 and 3 instantiates an array named grid to the input dimensions every grid entry is assigned a new Cell object with the corresponding array indices loads the neighbor[ ] array for every cell in the grid if the cell is not positioned along the boundary, each entry in its neighbor[] array may be the actual neighbor cell selected with probability p, otherwise the assigned value is null; use the ternary conditional operator to make the code of the nested for loop as concise as possible. For instance, if we select the south passage for the cell grid[2][5], the code would be grid[2][5].neighbor[2] = (Math.random( )

7. Applications This class contains main( ), tests and exercises all the maze applications. The main( ) calls the factory methods of the MazeBuilder class, using the returned grid instantiates a Maze object and calls the findPath( ) method.

Implementation and Testing Hints for implementation are included in the development phases above. Independent testing is recommended in cases of the maze factory methods, the display( ) method of the Stack class and of course the findPath( ) method of the Maze class. Testing a program that runs on random input is hard in general and it is particularly true in case of the random maze. Therefore the search algorithm must be tested first on a pre-determined undirected maze. You may use the supplied examples, but even better if you set up a small 4 x 4 grid for the maze ( you must construct the corresponding toEast and toSouth files, care for the precondition of the loadMazeFromFiles( ) method). With well tested findPath( ) you are in safer position to exercise the random maze.

Run the program for experiments Choose 0.5 for probability input, and run the search on a 5 x 5 maze 10 times. Count how many times should the search fail. Increase probability to 0.8 and repeat the experiment. Keep record of your counting results. Keep the probability 0.8 and increase the dimension up to 20 x 20 and detect at what size it becomes very unlikely to have a path. Write a report on your experience with the random maze and attach it as a word file to your submitted folder. (You may include loops in the Applications class that may save you the time to restart the program by hand; the saved time though may be shorter than the time required to do the additional coding.)

Figures:

342 Chapter 6 / Stacks st Version of the Generic Store FIGURE 6.7 Specification and Implementation for the Linked List Vers gas. Como e edu.colorado.collections (FIGUR pub7 Generic Class LinkedStack > public class LinkedStack from the package edu.colorad A Linkedstack is a stack of references to E objects. Limitations: Beyond Int.MAX_VALUE items, size is wrong. Specification Constructor for the LinkedStack public LinkedStack(O Initialize an empty stack. Postcondition: This stack is empty. clone public LinkedStack clone (O Generate a copy of this stack. Returns: The return value is a copy of this stack. Subsequent changes to the copy will not affects original, nor vice versa. Throws: OutOfMemoryError Indicates insufficient memory for creating the clone. isEmpty-peekpop-push-size public boolean isEmptyO public E peek (0) public E pop(0 public void push(E item) public int size() These are the standard stack specifications from Figure 6.1 on page 318. Implementation // File: LinkedStatck.java from the package edu.colorado.collections 77 Complete documentation is available above or from the LinkedStack link at 7/ http://www.cs.colorado.edu/~main/docs/, package edu.colorado.collections; import java.util. EmptyStackException: import edu.colorado.nodes. Node; 342 Chapter 6 / Stacks st Version of the Generic Store FIGURE 6.7 Specification and Implementation for the Linked List Vers gas. Como e edu.colorado.collections (FIGUR pub7 Generic Class LinkedStack > public class LinkedStack from the package edu.colorad A Linkedstack is a stack of references to E objects. Limitations: Beyond Int.MAX_VALUE items, size is wrong. Specification Constructor for the LinkedStack public LinkedStack(O Initialize an empty stack. Postcondition: This stack is empty. clone public LinkedStack clone (O Generate a copy of this stack. Returns: The return value is a copy of this stack. Subsequent changes to the copy will not affects original, nor vice versa. Throws: OutOfMemoryError Indicates insufficient memory for creating the clone. isEmpty-peekpop-push-size public boolean isEmptyO public E peek (0) public E pop(0 public void push(E item) public int size() These are the standard stack specifications from Figure 6.1 on page 318. Implementation // File: LinkedStatck.java from the package edu.colorado.collections 77 Complete documentation is available above or from the LinkedStack link at 7/ http://www.cs.colorado.edu/~main/docs/, package edu.colorado.collections; import java.util. EmptyStackException: import edu.colorado.nodes. Node