At the top of these notes you will see a button to download a NetBeans project containing my solution to the maze lab problem.
These notes will take you through some key aspects of that solution.
Here is the code for the method in the Maze class that finds an open neighbor of a given cell.
public Cell findOpenNeighbor(Cell fromCell)
{
int row = fromCell.getRow();
int col = fromCell.getColumn();
if(row - 1 >= 0 && grid[row-1][col].isOpen())
return grid[row-1][col];
if(col - 1 >= 0 && grid[row][col-1].isOpen())
return grid[row][col-1];
if(row + 1 < grid.length && grid[row+1][col].isOpen())
return grid[row+1][col];
if(col + 1 < grid[row].length && grid[row][col+1].isOpen())
return grid[row][col+1];
return null;
}
This code starts by asking the given Cell which row and column it sits in. The four immediate neighbors of this cell will be in the rows above and below and the columns to the left and right of this location.
An important special case we have to watch out for are Cells that sit at the edge of the maze. The entrance cell is once such example: that cell sits on the left edge of the maze. Cells on the edge of the maze will be missing one or more neighbors, so we have to add additional logic to test for those cases and not try to look in directions where a Cell may not have a neighbor. The generic name for these kinds of special cases in programming is edge cases. Thinking through all of the edge cases in any particular algorithm is an important part of the programming task.
The code above handles edge cases by adding an additional test to each of the four if statements. This additional test determines whether the direction we are about to look in is a legitimate direction to examine.
The Path class stores a list of Cells in an ArrayList of Cells. All of the methods in the Path class will have to work with that ArrayList, so writing most of these methods is an exercise if finding the right ArrayList methods to work with.
public class Path {
/* Member variables */
private ArrayList<Cell> cells; // Holds the path cells
/* Construct an initially empty path */
public Path() {
cells = new ArrayList<Cell>();
}
/* Accessor methods */
// Return the last cell on the path.
public Cell lastCell() {
return cells.get(cells.size()-1);
}
// Print every cell on the path
public void print() {
for(Cell c : cells)
System.out.println(c);
}
/* Mutator methods */
// Add the given cell to the end of the path
public void addCell(Cell toAdd) {
cells.add(toAdd);
}
// Remove the last cell from the path
public void removeCell() {
int lastIndex = cells.size() - 1;
cells.remove(lastIndex);
}
}
To test each of the classes I wrote, I also wrote short main methods containing test programs. Here is the test program for the Maze class:
public static void main(String args[]) throws Exception {
Maze m = new Maze("test.maze");
m.print();
System.out.println();
Cell entrance = m.findEntrance();
System.out.println("Entrance is " + entrance);
Cell neighbor = m.findOpenNeighbor(entrance);
System.out.println("Neighbor is " + neighbor);
}
Here is the test program for the Path class:
public static void main(String args[]) {
Path p = new Path();
Cell one = new Cell(1,2,'o');
Cell two = new Cell(1,3,'o');
p.addCell(one);
p.addCell(two);
System.out.println("Path before remove:");
p.print();
p.removeCell();
System.out.println("Path after remove:");
p.print();
}
Writing test programs for each class you create is a very useful practice. Doing this will allow you to debug a class's methods in isolation before you work on combining multiple classes into a complete solution.
Once all of the classes are in place and we have tested them to see that they are working correctly, the last step is to write the maze solving program itself. To do this, I created a fourth class and equipped it with a main method. Here is the code for that class.
public class Search {
public static void main(String[] args) {
Maze m = new Maze("test.maze");
Path p = new Path();
Cell end = m.findEntrance();
p.addCell(end);
while(end.isExit() == false) {
Cell next = m.findOpenNeighbor(end);
if(next == null) {
p.removeCell();
end = p.lastCell();
} else {
next.markVisited();
p.addCell(next);
end = next;
}
}
p.print();
}
}
The solution operates in a series of rounds. In each round we seek to move the path forward by searching for an open neighbor of the Cell at the end of the current path. If we can find an open neighbor we add it to the path. If we can't find an open neighbor we know we need to backtrack. In that case we will simply remove one Cell from the end of the path and then try again with the new end of the path.