Searching through Grids

You will submit your heap and priority queue implementations as a checkpoint on November 13th, a week before the full project sumission! We'll grade them using the supplied tester. Submit them in your project 7 folder.

Tasks

Testing

As always, as you are coding up this project create testing files for each class you create exercising the public methods implemented in this class.

Maze Class

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

    Now that we have our Maze class, let's 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> traceback(Cell cell){
    Cell curCell = cell;
    LinkedList<Cell> path = new LinkedList<>();

    while (curCell != null){
        add curCell to the front of path
        if (curCell is the start){
            return path; // we've completed the path from the start to the specified cell
        }
        curCell = curCell.getPrev();
    } return null; // we weren't able to find a path, so we return 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:

  2. 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...

  3. 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...

  4. 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);
    }
}

Lastly, 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

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.

Extensions

  1. Implement different types of Cells, like mud (where it's slow to walk through) or ice (where it's difficult to turn, but going straight takes less time). How do your algorithms do on this changed environment?
  2. 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.
  3. Somewhat relatedly to the previous extension, 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.

Report

Your intended audience for your report are your peers not in the class, but who have taken a CS course. Your report should explain the core CS concept used, present the results of your program, and discuss the meaning of the results: what did you discover and does it make sense?

Your project report should contain the following elements. Please include a header for each section.