This lecture, and the lab that follows, will take you through the solution of a moderately complex problem. The problem is to find a path through a maze.
The maze will be loaded from a text file that has the following format.
9 13 ############# eoo#o#ooo#oo# ##o#o##o##o## #oooo#oo#ooox ###o##o##o### #ooooooooooo# #####o###o### #ooooooooooo# #############
The first line in the text file gives the dimensions of the maze - how many rows and columns make up the maze. The remaining lines give the structure of the maze itself. A # represents a wall, an o an open space, e the entrance, and x the exit.
A typical maze has features such as blind alleys and cycles. Any algorithm that solves the maze has to be able to cope with those features and still find a path from entrance to exit.
The first step in constructing an object-oriented program to solve a complex problem is to identitfy the class or classes that will play a role in the solution. For this problem, three classes immediately suggest themselves:
Below is the complete source code for a class that can be used to represent individual cells in a maze application.
package maze;
/** A class to represent cells in a maze. Cells can be blocked,
* open, or visited. In addition, entrances and exits in a maze
* are represented by a special cell type.
*/
public class Cell {
/* Class variables */
private static final char OPEN = 'o';
private static final char VISITED = 'v';
private static final char CLOSED = '#';
private static final char ENTRANCE = 'e';
private static final char EXIT = 'x';
/* Member variables. */
private int row;
private int column;
private char state;
/* Constructor */
public Cell(int row,int column,char code) {
this.row = row;
this.column = column;
state = code;
}
/* Accessor methods */
public boolean isOpen() { return state == OPEN || state == ENTRANCE || state == EXIT; }
public boolean isEntrance() { return state == ENTRANCE; }
public boolean isExit() { return state == EXIT; }
public int getRow() { return row; }
public int getColumn() { return column; }
public char toChar() {
return state;
}
public String toString() {
return "(" + row + "," + column + ":" + toChar() + ")";
}
/* Mutator methods */
public void markVisited() {
if(state == OPEN)
state = VISITED;
}
public void clearVisited() {
if(state == VISITED)
state = OPEN;
}
/* Test program to test the Cell class. */
public static void main(String[] args) {
Cell firstCell = new Cell(1,1,'o');
System.out.println("Before visit the cell is: " + firstCell.toString());
firstCell.markVisited();
System.out.println("After visit the cell is: " + firstCell.toString());
System.out.println();
Cell secondCell = new Cell(3,1,'#');
System.out.println("Before visit the cell is: " + secondCell.toString());
firstCell.markVisited();
System.out.println("After visit the cell is: " + secondCell.toString());
}
}
This class uses a special feature, the static member variable. Like other member variables, these variables are declared in the class, but not inside any of the methods. The variable declaration for these variables contain the keyword static, which marks these as static member variables. Unlike ordinary member variables, which appear as variables in every object of this class, static member variables appear just once in the class itself. That one instance of the member variable is shared by all of the objects in that class. One popular application for static member variables is defining class constants: these are fixed values that are used for a special purpose in the class. To make a variable in Java constant, you add the keyword final to the variable declaration. Also, final variables are initialized at the same time you declare them. Here is one of the static member variables:
private static final char OPEN = 'o';
This declaration allows us to use the word OPEN in place of the letter 'o' in all of our code. Since OPEN is a little more meaningful than 'o' this will make our code less error-prone.
Another stategy I have followed here is to organize the member variables and methods into groups. Whenever a class starts to have a lot of things in it, it starts to be helpful to organize things into logical groupings. I have organized the methods into several groups:
Finally, the last thing you will see in this class is a main method. The purpose of this main method is to allow us to write some simple test code that tests the operation of the class.
Here now is an outline of the Maze class that our application will use to represent mazes. In this outline I have left out the code for the methods to make it easier to get an overview of the structure of the class.
public class Maze {
/* Member variables */
private Cell[][] grid;
/* Construct a maze by reading it from a file. */
public Maze(String fileName){}
/* Accessor methods */
// Find and return an entrance cell
public Cell findEntrance() {}
// Find a neighbor of the given cell that is open
// and return a reference to that neighbor cell. If
// you can find no such neighbor, return null.
public Cell findOpenNeighbor(Cell fromCell) {}
// Print the contents of the Maze to System.out
public void print() {}
/* Mutator methods */
// Reset all visited cells to open
public void clearVisited() {}
// Test program to test the Maze class
public static void main(String args[]){}
}
This class is designed to provide just enough useful methods to facilitate solving the maze search problem. In particular, the class provides a method that finds and returns the entrance cell that we need to start the search process and a method that finds an unvisited neighbor for a given cell. As we shall see in the lab exercise this week, those two methods are sufficient to allow us to solve the maze searching problem.
The final class we will need to solve the maze search problem is a class that can represent a path through the maze. At the start of the maze search, the path will consist of just a single Cell, the entrance cell for the maze. As the search progresses we will systematically add Cells to the path. Occasionally, the path will run up into a blind alley. When that happens, we will not be able to find any unvisited neighbors for the cell at the end of the path and we will have to backtrack to a point where there are unvisited neighbors. To facilitate that, we have to be able to shed Cells from the end of the path.
Here is an outline of the Path class showing its methods and member variables.
public class Path {
/* Member variables */
private ArrayList<Cell> cells; // Holds the cells along the path
/* Construct an initially empty path. */
public Path() {}
/* Accessor methods */
// Return the last cell on the path, or null if the path is empty.
public Cell lastCell() {}
// Print every cell on the path
public void print() {}
/* Mutator methods */
// Add the given cell to the end of the path
public void addCell(Cell toAdd) {}
// Remove the last cell from the path
public void removeCell() {}
// Test program to test the Path class
public static void main(String args[]) {}
}
The Path class stores its Cells in an internal ArrayList. An ArrayList is the appropriate structure to use here, since we can start off with an empty ArrayList and use the add() and remove() methods as needed to add cells to the end of the path or remove them.
We now have all of the basic ingredients needed to solve the maze problem. In lab this week we will finish building the three classes I outlined above and use those classes to solve the maze problem.