CS231

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

unobstrocted cell (free cell)
obstructed cell

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.
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
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 setPrev(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.

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. Additionally chooses two random non-Obstacle Cells to be the start and the target.
- public Maze(Cell[][] grid, Cell start, Cell target)uses the given grid as the maze with the given start and target.
- 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 Cell getStart() returns the starting Cell of the maze.
- public Cell getTarget() returns the target Cell of the maze.
- 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

Testing: Once you have completed all of the maze searchers below, test them with these SearchTests. For debugging, you will most likely find the visualization more helpful. We recommend running the visualization with a small maze (e.g. 5x5) and viewing the searched cells (in yellow) as well as the found path. You may need to think about what each of these methods should do to check if they are working correctly from the visualization!

We will write a few different implementations of searching a Maze. Specifically, we will write:

The AbstractMazeSearch class:
This class will manage the following fields:
- private Maze 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 and removesit from your data structure.
- public abstract void addCell(Cell next): this method adds the given Cell to whatever structure is storing the future Cells to explore.
- public abstract void updateCell(Cell next): this method updates the Cell in the structure (this will only be applicable for A* search)
- 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 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 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){
    setCur(start);

    // This line is just to make the drawing work correctly
    start.setPrev(start); 

    Make sure you set the start/target of this object to be the given start and target
    (something like this.start = 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
            } else if (we've found a faster path to this neighbor (hint: use traceback)){
                set this neighbor's prev to be cur
                update this neighbor in our search structure
            }
            
            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
}
```

AbstractMazeSearch

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

Note that updatePriority doesn't need to do anything for this method
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.
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...

Note that updatePriority doesn't need to do anything for this method
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...

Note that updateCell does need to do something here: it just needs to call updatePriority

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.

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?
What is the relationship between the lengths of the paths found by DFS, BFS, and A*?
What is the relationship between the average number of Cells explored by DFS, BFS, and A*?

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

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. Up to 4 points
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. Up to 4 points

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