Maze Application Background

In the remainder of the lab, we will be exploring how stacks and queues can be useful for solving search problems such as searching for a solution to a maze. This part of the lab will provide useful background about how we can represent a maze in Java, so please read carefully to help you with the remainder of the lab. There is nothing to implement in this part.

Objective

The goal of this application is to implement an algorithm that finds a path from a unique starting location in a maze (shown below in green) to a unique exit location (shown in red). If such a path exists, the provided application will visualize not only the maze, but also the found solution path, shown in yellow below. If no path exists (which is possible for some mazes), the application should also be able to detect that no solution is possible.

We will explore how using queues or stacks in the algorithm will change the order that possible paths are explored due to the FIFO and LIFO properties, respectively. More formally, this algorithm is called Breadth First Search when using a queue and Depth First Search when using a stack. These algorithms are the basis upon which more intelligent algorithms are created, including solutions like A* from artificial intelligence that operates similar to common GPS navigation applications (e.g., in your car or phone, such as Google or Apple Maps).

Maze Application Files

In your GitHub repository, we have provided you with several files already implemented:

  1. Square.java defines a Square class that represents a single location within the maze
  2. Maze.java defines a Maze class that represents the collection of squares that comprise a complete maze. Note: not every maze will necessarily be solvable.
  3. MazeApp.java defines a MazeApp class that is an application with a GUI that can visualize a given Maze object and its solution (if one is found).

We also provide a partially implemented file that you will complete in Part 4:

  1. MazeSolver.java defines a MazeSolver class where we will create our algorithm for finding solution paths through a given Maze.

Finally, we have also provided you with a folder called mazes that contains multiple files (e.g., maze-1, maze-4 pictured above, maze-occs), each containing a different maze that can be read by the MazeApp application.

Square Class

Instances of the Square class contain useful information about their particular location in the maze. Squares exist in a given row and column within the maze and they have one of four types:

  • Start: the starting location of the maze (only one per maze)
  • Exit: the ending goal location of the maze (only one per maze)
  • Space: an open space that might be part of a path from the start to the exit (many per maze)
  • Wall: an invalid location that cannot be part of a path from the start to the exit (possibly many per maze)

Important methods of the Square class that you will use as you implement your MazeSolver include:

  • isStart(), isExit(), isSpace(), and isWall() allow you to check the type of a Square by returning true if the Square is the corresponding type of location, else false (e.g., isSpace() returns true whenever the Square is a space location, else it returns false).
  • isMarked() allows you to check whether the Square has been marked as already explored by the solution algorithm.
  • mark() records that the Square has been explored in our algorithm so that isMarked() will later return true.
  • setOnPath() records that the Square is part of the solution path from the start to exit locations.
  • setPrevious(Square sq) saves the previous Square sq that led to this Square along the current path from the start location
  • getPrevious() returns the Square that preceded this Square along a possible path from the start location (saved using setPrevious(Square sq))

Other methods implemented in the Square class are used by either the Maze or MazeApp classes to make the application work, and you do not need to understand these methods to complete the assignment (but you are welcome to read their Javadocs to learn more!).

Maze Class

Instances of the Maze class represent the maze read in from a user-chosen file, which mostly consists of the collection of Square objects that represent every location in the maze. You should be somewhat familiar with this class from filling in its documentation using Javadocs in Part 2 of the Warmup. We also suggest reading the Javadocs for Square.java to familiarise yourself with what each method does.

Although there are several methods implemented in the Maze class, the only one you need to know about for your maze solving algorithm is:

  • getNeighbors(Square sq) returns an ArrayList<Square> containing all the neighboring Squares of a given Square sq.