Searching through Grids

In this project, you will be implementing 3 different algorithms for searching for a path through a maze with obstacles using data structures we have seen this semester--breadth-first search, depth-first search and A* search. You have been provided with a fully implemeneted Cell and Maze class to expedite the process.

Tasks

Cell Class (Provided)

README: In order to expedite the process of this project, we're including a fully implemented Cell class and CellType enum. However, do take a few minutes to peruse the methods described below and their implementations to make sure you understand the underlying Cell class.

In a return to familiarity, this project will be based around a 2-D Landscape consisting of individual Cells. Each Cell will have an underyling type; specifically, each Cell will either be an

  1. Declaring the enum CellType

    To implement this we'll create an additional file CellType.java with the following contents:

    public enum CellType {
        FREE, OBSTACLE;
    }
    An enum is something like a restricted class in Java, in that you're declaring a type of object that can only take on specific values. In this case, we're declaring that the enum type can either be free or obstructed.

  2. Cell's Fields

    Each Cell should have the following (private) fields:

    • boolean visited for determining whether we've visited this Cell yet
    • Cell prev for determining which Cell we came from to visit this Cell
    • int row, col for determining which row and column this Cell belongs to in the Landscape
    • CellType type for determining which type of Cell this is

  3. Cell's Methods

    All of Cell's methods are basically just getter/setters, but they'll become more obviously useful in the Landscape class.

    • public Cell (int row, int col, CellType type) constructor that sets up the row, col, and type as specified; prev should be null and visited should be false.
    • public int getRow() returns the row
    • public int getCol() returns the column
    • public CellType getType() returns the type
    • public boolean visited() returns visited
    • public Cell getPrev() returns prev
    • public void visitFrom(Cell c) sets visited to true and prev to c
    • public void reset() sets visited to false and prev to null

Maze Class (Provided)

README: In order to expedite the process of this project, we're including a fully implemented Maze class. However, do take a few minutes to peruse the methods described below and their implementations to make sure you understand the underlying Maze class.

The Maze class will manage a grid of Cells.

  1. Maze Fields and Methods

    What fields you keep track of in your Maze class is up to you. However, you'll need to implement the following methods:

    • public Maze(int rows, int cols, double chance) constructs the Maze to have the specified number of rows and columns, where each Cell has a probability given by chance of being an Obstacle.
    • public int getRows() returns the number of rows.
    • public int getCols() returns the number of columns.
    • public Cell get(int row, int col) returns the Cell at the specified row and column.
    • public void reset() resets all the Cells in the Maze.
    • public LinkedList<Cell> getNeighbors(Cell c) returns a LinkedList of Cells containing all the adjacent (diagonals not included) non-Obstacle neighbors of the specified Cell in the grid.


The MazeSearchers

    We will write a few different implementations of searching a Maze, specifically:

    To unite these classes (as they will all behave extremely similarly), we'll start out with an AbstractMazeSearch class.

  1. The AbstractMazeSearch class:

    This class will manage the following fields:

    • private Maze: a Maze object that will be the basis for the search
    • private Cell start: the Cell which the search starts from
    • private Cell target: the Cell which the search is trying to reach
    • private Cell cur: the Cell where the search is currently at
    To initialize these fields, we'll have a constructor:
    • public AbstractMazeSearch(Maze maze): initializes the fields. In particular, saves the given Maze to the relevant field and sets cur, start, and target to be null.
    As an abstract class, there are a few methods that will be left up to the inheriting class to implement. These will be:
    • public abstract Cell findNextCell(): this method returns the next Cell to explore.
    • public abstract void addCell(Cell next): this method adds the given Cell to whatever structure is storing the future Cells to explore.
    • public abstract int numRemainingCells(): this method returns the number of future Cells to explore (so just the size of whatever structure is storing the future Cells).
    There are some methods, however, that can be written without even knowing which type of search we will be using:
    • public Maze getMaze(): just returns the underlying Maze.
    • public void setTarget(Cell target): sets the given target to be the target of the search.
    • public Cell getTarget(): returns the target of the search.
    • public void setCur(Cell cell): sets the given cell to be the current location of the search.
    • public Cell getCur(): returns the current Cell location of the search.
    • public void setStart(Cell start): sets the given start to be the start of the search. Additionally, set start's prev to be itself - the reason for this will make sense a bit later.
    • public Cell getStart(): returns the start of the search.
    • public void reset(): sets the current, start, and target Cells to be null.
    • public LinkedList<Cell> traceback(Cell cell): finds a path from the start to the specified cell by repeatedly following the prev path. Returns the path if found, otherwise returns null.
    • public LinkedList<Cell> search(Cell start, Cell target): the most important method of the class. This is the method that actually does the searching. Despite that we don't event know exactly which search algorithm we'll use, we can use the abstract methods to organize the search regardless. The LinkedList we return will be the path our search algorithm finds to reach the target from the starting Cell. If one isn't found, we'll return null. To aid you, consider the following pseudo-code:
      public LinkedList<Cell> search(Cell start, Cell target){
          setStart(start);
          setTarget(target);
          setCur(start);
      
          add the starting cell to the set of Cells to explore
          while (there are still Cells left to explore){
              set Cur to be the next Cell from the Cells to explore (findNextCell())
      
              for (each neighboring Cell of cur) {
                  if (this neighbor hasn't been visited before (if its prev is null)){
                      set this neighbor's prev to be cur
                      add this neighbor to the future Cells to explore
                      if (this neighbor is the target){
                          return traceback(target); // we found the target, we're done
                      }
                  }
              }
          }
      
          return null; // we couldn't find the target, but we're done
      }
      

  2. Now that we've got our AbstractMazeSearch class, we just need to extend it with a few specific algorithms:
  3. MazeDepthFirstSearch: this class will extend the AbstractMazeSearch class and implement the DFS algorithm. We've seen this algorithm before, actually, back when we solved Sudoku! We'll use a Stack as the backbone of the algorithm and continually dive down a particular solution until we reach the target or exhaust all reachable Cells.

    In order to write this class, we'll need to manage a Stack: private Stack<Cell> stack. In addition, we'll need a constructor public MazeDepthFirstSearch(Maze maze): this will call the parent's class constructor (via the super keyword) with the given Maze and initialize the Stack (as a new LinkedList).

    Additionally, we need to implement the abstract methods of the parent class - these all simply call the relevant Stack method. And that's it! Ah, the usefulness of polymorphism...

  4. At this point, we recommend jumping directly to visualizing the search so you can watch how your maze searching algorithm works and make sure it's working as you expect it to! Return here once you have done that.
  5. MazeBreadthFirstSearch: another class to extend the AbstractMazeSearch class and implement the BFS algorithm. This one is new: we'll use a Queue as the backbone of the algorithm and simultaneously work on 'every solution' by working on all directions at once until we reach the target or exhaust all reachable Cells.

    In order to write this class, we'll need to manage a Queue: private Queue<Cell> queue. In addition, we'll need a constructor public MazeBreadthFirstSearch(Maze maze): this will call the parent's class constructor (via the super keyword) with the given Maze and initialize the Queue (as a new LinkedList).

    Additionally, we need to implement the abstract methods of the parent class - these all simply call the relevant Queue method. And that's it! Ah, the usefulness of polymorphism...

  6. MazeAStarSearch: the final class to extend the AbstractMazeSearch class and implement the A* algorithm. This one is slick: we'll use a PriorityQueue as the backbone of the algorithm and use our knowledge of where the target is to try to walk in the 'right direction' until we reach the target or exhaust all reachable Cells.

    In order to write this class, we'll need to manage a PriorityQueue: private PriorityQueue<Cell> priorityQueue. In addition, we'll need a constructor public MazeAStarSearch(Maze maze): this will call the parent's class constructor (via the super keyword) with the given Maze and initialize the PriorityQueue (as a new Heap). Of course, Cells aren't innately Comparable, so we'll need to provide the Heap constructor a Comparator to tell it how to prioritize Cells.

    To build the Comparator, we'll need to make a public int compare(Cell cell1, Cell cell2) method that returns a negative number if cell1 is of greater priority than cell2, a positive number if cell2 is of greater priority, or 0 if they have the same priority. To do this, consider what we want to prioritize: we want to follow the Cell that results in the shortest overall path to the target. Note that we only add Cells to the priorityQueue if they have already been reached, so we now how many steps it takes to get to the given Cell (you can use the traceback method for this). We might not know exactly how many steps are required to get to the target from each Cell, but we do have a lowerbound: we have to take at least one step for each difference in column and one step for each difference in row! So the Cell with higher priority should be whichever Cell has the smaller sum of the number of steps to reach it and the estimated distance to the target.

    Lastly, we need to implement the abstract methods of the parent class - these all simply call the relevant PriorityQueue method. And that's it! Ah, the usefulness of polymorphism...

Visualizing the Search

The final task (you're in the home stretch!) is to add a visualization component to your searches. As per usual, we're providing you with the draw methods of the AbstractMazeSearch class (they are already in the Cell and Maze classes provided). The draw method for your AbstractMazeSearch class calls every other class' draw method. Make sure to import java.awt.Graphics and java.awt.Color.

public void draw(Graphics g, int scale) {
    // Draws the base version of the maze
    getMaze().draw(g, scale);
    // Draws the paths taken by the searcher
    getStart().drawAllPrevs(getMaze(), g, scale, Color.RED);
    // Draws the start cell
    getStart().draw(g, scale, Color.BLUE);
    // Draws the target cell
    getTarget().draw(g, scale, Color.RED);
    // Draws the current cell
    getCur().draw(g, scale, Color.MAGENTA);

    // If the target has been found, draws the path taken by the searcher to reach
    // the target sans backtracking.
    if (getTarget().getPrev() != null) {
        Cell traceBackCur = getTarget().getPrev();
        while (!traceBackCur.equals(getStart())) {
            traceBackCur.draw(g, scale, Color.GREEN);
            traceBackCur = traceBackCur.getPrev();
        }
        getTarget().drawPrevPath(g, scale, Color.BLUE);
    }
}

Download MazeSearchDisplay class. To use it, add two parameters to your search method in the AbstractMazeSearch class: public LinkedList<Cell> search(Cell start, Cell target, boolean display, int delay): if display == true, create a MazeSearchDisplay with arguments: this, 20 before the start of the while loop. (If display is false you'll want to create a null MazeSearchDisplay object). In the while loop, if display == true call Thread.sleep for delay milliseconds and call repaint on the MazeSearchDisplay object. You'll need to handle the Interrupted Exception that can be thrown by calling Thread.sleep. One option to do that is this:

try{ Thread.sleep(delay); }

catch(InterruptedException e) {} ;

Exploration

Include your answers to these questions in your results section

Use your simulation to explore the following questions. You can change the density of obtacles in the constructor for the Maze class. Note, you can always set the delay to 0 to maximize the speed of the solve.

  1. What is the relationship between the density of obstacles to probability of reaching the target? Note that this should be independent of whichever search algorithm you use, as they should all find the target if it is reachable. Specifically, around what density of obstacles does the probability of reaching the target drop to 0?
  2. What is the relationship between the lengths of the paths found by DFS, BFS, and A*?
  3. What is the relationship between the average number of Cells explored by DFS, BFS, and A*?
  4. Present your results as a table or as multiple graphs and be sure to include both a caption explaining any tables/graphs and at least a paragraph describing your findings. You should include the results of experiments with at least 10 different settings of the density of obstacles spaced out between 0 and 1.


Reflection Questions

Please answer the following 2 questions. Put any written responses numbered in the Reflection section of your report, and include any code with your other code files. This section is worth a substantial portion of your project grade, and generally includes the type of more conceptual exercise you can expect to see on exams, so it's good preparation for that!

Question 1: (Arrays vs Nodes)

In this project you implemented an Array-based Heap. However, anytime we draw a Heap we almost always draw it as a node-based structure. Discuss the trade-offs between using arrays vs nodes specifically for a heap structure. Why is an array-based heap easier to implement? What would be the biggest advantage of using a Node-based heap?

Question 2: (A* vs BFS vs DFS)

So now that we've implemented these search methods, how do they relate?

In particular:

(If you start writing about a search method that we haven't used in this class, you're thinking about this wrong)


Extensions

  1. Realistically, some of these algorithms don't make a lot of sense from a human's perspective. How are you, a human, going to teleport around the maze to get to the next Cell your search wants to move to? Analyze the number of steps required in a grid to 'walk to' the next Cell while finding the target and see how your search algorithms fare.
  2. Try and find the 'shortest path' making some assumptions about acceleration, such as in the Micro Mouse game. For example, you could assume that going straight is faster than turning, and try to determine the fastest path under that assumption.

Congrats, you're done with everything except for your project report where you will communicate your findings from all that code! Make sure to write up your report in the project report file in the Google Classrooms assignment. The project report is an important part of the work in this project, so don't forget to do it!