Finding a Maze Solution

Class Overview

The MazeSolver class is an abstract class that implements most of the functionality needed to find a solution path through a given Maze (or determine that no solution exists). It is an abstract class because later in the lab, we will implement two children classes: one that uses a queue to explore the possible paths through the maze and another that instead uses a stack.

Finding a Solution Path

The general algorithm for finding a solution for a maze works by expanding possible path one step at a time from the start location until either (1) we reach the exit location, indicating we found a solution path, or (2) we explore every reachable location from the start location without reaching the exit location, indicating no solution path exists.

To explore all reachable paths, we need to keep track of three important pieces of information:

  • We need a collection of Squares that would expand our current paths by a single step. We will call this collection our exploration collection.
    • In Part 5 of the lab, we will explore what happens when the exploration collection is either a queue or a stack.
  • Each Square location needs to know whether it has already been added to the exploration collection by our algorithm (so that we never repeat locations, which at best would result in longer paths than needed, and at worst could cause our algorithm to become stuck in an infinite loop).
    • The isMarked() and mark() methods defined in Part 3 of the lab will be helpful here
  • Each Square location along a possible path needs to know which Square location preceded it in the path back to the start location. We can use these previous links (similar to the previous variable of our DoublyLinkedNodes of our linked list in Lab 4) to trace an entire path through the maze.
    • The getPrevious() and setPrevious() methods defined in Part 3 of the lab will be helpful here.

When our algorithm starts, our exploration collection will contain only the start location, all Squares other than the start location will not be marked as explored (so their isMarked method will return false), and no Square has a previous Square. The algorithm will proceed by:

  1. Checking whether the exploration collection is empty. If so, the algorithm should record that it is finished and that no solution is possible.
  2. Otherwise, the next Square from the exploration collection should be retrieved from the exploration collection.
  3. If the Square in Step 2 is the exit location, use its previous Squares to build the path from the start location to the exit location. The algorithm should also record that it has finished and a solution has been found.
  4. Otherwise, each of the neighboring Squares of the Square from Step 2 should be added to the exploration collection as long as (i) the neighbor Square is not a wall and (ii) the neighbor Square location has not already been added to the exploration collection. When a neighboring Squares location is added to the exploration collection, then (i) the Square from Step 2 should be saved as the neighbor’s previous location back towards the start location, and (ii) the neighbor should be marked as added to the exploration collection.
  5. Repeat Steps 1-4 until the algorithm finishes in Step 1 or 3.

Below, we describe how to complete the MazeSolver class in two parts so that it executes this algorithm.

Implementing our Search Algorithm

Steps 1 and 2 of the algorithm have already been implemented for you in the public void step method of the MazeSolver class. Your assignment in this part of the lab is to implement Steps 3-4 in the bottom of the method under the comment:

/*
 * TODO: implement one step of maze exploration algorithm
 */

Running the algorithm until it completes in Step 5 is also implemented for you by the MazeApp class.

As part of Step 3, you should call the public void buildPath(Square sq) method that is responsible for saving the solution path in the this.path instance variable as a list of Squares starting with the starting location and ending with the exit location. You should also use the this.finished instance variable to record that the algorithm has finished executing (similar to Step 1 that is implemented for you) and the this.pathFound instance variable to record that a solution path has been found.

As part of Step 4, you can add a neighbor to the exploration collection using the public void add(Square sq) method of the MazeSolver class.

Creating the Solution Path

The public void buildPath(Square sq) method is not already implemented, so you will need to fill in the necessary code after the comment:

/*
 * TODO: fill in this.path with the Squares from the start to the end.
 */

You can assume the public void buildPath(Square sq) is only called with the exit location as its Square sq argument. You can use the Square class’s getPrevious() method to find the full path of Squares from the exit location back to the start location. As you add each Square to the path, do not forget to record that it is on the path using the appropriate method of the Square class. Finally, the built-in function:

Collections.reverse(this.path);

might be helpful to then reverse the order of your path so that it instead goes from the start location to the exit location (although you are welcome to fill in the this.path instance variable however you wish).

Testing Your Progress

Unfortunately, at this point, we cannot quite test our progress, yet. Instead, we first need to implement children classes that are not abstract, which we will do next in Part 5 of the lab.

Committing Your Progress

Don’t forget to frequently save your progress periodically to GitHub using the add, commit, and push commands with git.