- The maze will be represented by a 2-D array, type
int[ ][ ]that has exactly 20 rows and 70 columns. It will be initialized by reading lines from a text file. Each character in the file is either a * for a free cell or a blank space for a wall cell. - The maze has at most one entry point on the left edge and at most one exit point on the right edge.
- The cells around the border of the maze (top row, bottom row, left edge, right edge) are all "wall" cells except for the entry and exit if they exist. That is, the path will not run along the edges of the maze.
- The maze does not contain any cycles. The consequences of this will be discussed in class.
- The state of an array cell, once processed (see below), will be
one of FREE, WALL, or USELESS defined as constants:
private final int FREE = 0; private final int WALL = 1; private final int USELESS = 2;
Maze file format:
- The filename will be of the form
*.datand will be a standard text file. - Each line in the file corresponds to a row in the matrix.
- An asterisk in the line represents a FREE space (potentially on a path) and a space represents a WALL.
- The length of a line is the number of characters to the last asterisk. So the first and last lines of the file will have length 0. Thus before reading the file you should initialize all cells of the maze array to WALL to facilitate loading the array from the file. The maze array will not have any USELESS cells until it has been preprocessed (see below).
- An example maze file is displayed below:
Displaying the maze:
- Display a WALL cell as a '|' character
- Display a USELESS cell as a '?' character
- Display a FREE cell as a ' ' character.
The algorithm:
- Initialize the maze.
- Read the maze file one line at a time and set the next row of the maze accordingly.
- Preprocess the maze as follows -
- Examine each FREE cell of the maze array. If 3 of its 4 neighbors are WALL or USELESS make the cell USELESS.
- Repeat the above step until you make a pass that results in no cells being marked USELESS.
- At this point you either have a path, indicated by the FREE cells, or you have no path. To determine if you have a path, traverse it by finding the entry point on the left edge, following the FREE cells through the array, and successfully (or not) reaching a free cell on the right hand side. This kind of technique (making an optimal decision at each step) is referred to as a greedy algorithm.
The maze project:
- The project should consist of three classes – Driver, Maze, and Infile.
- Driver (client) – Creates instances of Infile and Maze and invokes appropriate methods from each.
- Maze (server/client) – Initializes the maze array, loads the maze array from the input file, preprocesses the array, determines if there is a path through the maze, displays the maze accordingly.
- Infile (server) – This class will be given to you in the maze project.
- The project can be copied from
I:\csc122\public\maze - Implement the project using the test driven implementation strategy: first build a test system and stubbed implementation of each class.
- Test on the mazes stored in the project file,
Maze1.DatandMaze2.Dat.
Standards:
Your project should be well-written, neatly-formatted, modular, and well-documented.
Grading:
- Getting filename and opening file (15 pts)
- Reading the maze (20 points)
- Preprocessing correctly (20 points)
- Handling the greedy step correctly (traversing the maze after preprocessing) (20 points)
- Detecting maze with no solution (10 points)
- Documentation and style (15 points)
