The maze problem

For this lab exercise we are going to write a program that can use a collection of objects to solve a moderately complex problem. The problem is finding a path through a maze. In class on Wednesday I started the process of building the classes needed to solve this problem.

Getting set up

Start by downloading the project containing the code I have written so far for the path finding problem.

The project contains code for three classes, a Cell class, a Maze class, and a Path class.

The code for the Cell class is already complete. In this lab exercise you will be filling in the remaining code for the Maze and Path classes and then writing a main program to solve the maze.

Complete the Maze class

I have provided code for some of the methods in the Maze class. Your first task is to fill in the code for the methods I did not complete (including the main method) and then run the Maze program to confirm that the Maze class is working correctly.

Complete the Path class

The path class is used to track our progress through the maze as we work our way from the entrance to the exit. The key requirements for a path class are that it should

• Allow you to record what cells are on the path
• Grow as new cells get added to the path
• Shrink as we backtrack out of blind alleys

I have provided the skeleton of a Path class for you to work with. The Path class contains an ArrayList named cells that allows us to record a sequence of cells along a path.

Your job now is to fill in the code for the remaining methods in the Path class, including some code for a main method that will test the Path class. In this main method you should create a Path object, add some cells to it, print the path, remove a few cells, and then print the path again.

Solving the maze

When we have completed writing the code for the Cell, Maze, and Path classes we have all of the ingredients in place to solve the maze problem. The only thing left to do is to add a fourth class to the project. That class will contain a main method that does the following:

• Construct a Maze object that holds the maze.
• Construct an initially empty Path.
• Find the entrance cell in the Maze and add it to the Path.
• Run the path finding algorithm from that starting point.
• Print the successful path.

To conduct the path-finding process I suggest you write a separate method to implement the path-finding algorithm. Here is an outline of the logic for that algorithm:

while(the exit node is not at the end of the path) {
  Find an open node next to the end of the path
  If you can find an open node, mark it visited and add it to the path
  If you can not find an open node, remove the last node from the path
}

This simple algorithm is all that is required to solve our problem. The algorithm is smart enough to back-track out of portions of the maze that are dead ends, it will not fall into an infinite cycle, and it will keep searching until it finds a path to the exit.