Searching through Grid-Graphs

This week we'll explore Depth-First Search and Breadth-First Search. This time, we'll be implementing both of these methods on a grid in order to find a path from a starting point to a target point.

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.

Landscape Class

The Landscape class will store a grid of Cells and keep track of the starting Cell and the target Cell.

  1. Landscape Fields and Methods

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

    • public Landscape(int rows, int cols, double chance) constructs the Landscape to have the specified number of rows and columns, where each Cell has a probability given by chance of being an Obstacle. Should probably also set the start and target Cells.
    • public Cell getStart() returns the start Cell.
    • public Cell getTarget() returns the target Cell.
    • public int getRows() returns the number of rows.
    • public int getCols() returns the number of columns.
    • public Cell getCell(int row, int col) returns the Cell at the specified row and column.
    • public void reset() resets all the Cells in the Landscape.
    • public ArrayList<Cell> getNeighbors(Cell c) returns an ArrayList of Cells containing all the adjacent (diagonals not included) neighbors of the specified Cell in the grid. It's up to you whether this filters out Obstacles and previously visited cells.

  2. Drawing to a Graphics Object

    As per usual, we're going to give you the draw methods for the Cell and Landscape classes:

    • Cell's draw: public void draw(Graphics g, int scale, Landscape scape) draws this Cell to the given Graphics object. Note that you'll need to import java.awt.Graphics and java.awt.Color for the code to compile. 
      public void draw(Graphics g, int scale, Landscape scape) {
    g.setColor(Color.BLACK);
    g.drawRect(getCol() * scale, getRow() * scale, scale, scale);
    switch (getType()) {
        case FREE:
            g.setColor(visited() ? Color.YELLOW : Color.GRAY);
            break;
        case OBSTACLE:
            g.setColor(Color.BLACK);
            break;
        case START:
            g.setColor(Color.BLUE);
            break;
        case TARGET:
            g.setColor(Color.RED);
            break;
    }
    g.fillRect(getCol() * scale + 2, getRow() * scale + 2, scale - 4, scale - 3);

    g.setColor(Color.RED);
    if (getPrev() != null && getPrev() != this) {
        int midX = ((getCol() + getPrev().getCol()) * scale + scale) / 2;
        int midY = ((getRow() + getPrev().getRow()) * scale + scale) / 2;
        g.drawLine(getCol() * scale + scale / 2, getRow() * scale + scale / 2,
                midX, midY);
    }
    for (Cell neighbor : scape.getNeighbors(this)) {
        if (neighbor.getPrev() == this) {
            int midX = ((getCol() + neighbor.getCol()) * scale + scale) / 2;
            int midY = ((getRow() + neighbor.getRow()) * scale + scale) / 2;
            g.drawLine(getCol() * scale + scale / 2, getRow() * scale + scale / 2,
                    midX, midY);
        }
    }
}
    • Landscape's Draw: public void draw(Graphics g, int scale) draws the Landscape to the specified Graphics object. Again, you will need to import java.awt.Graphics and java.awt.Color in order for this to compile. 
      public void draw(Graphics g, int scale) {
    for(int r = 0; r < getRows(); r++){
        for(int c = 0; c < getCols(); c++){
            getCell(r, c).draw(g, scale, this);
        }
    }
    g.setColor(Color.RED);
    CellQueue queue = new CellQueue();
    queue.offer(start);
    while (!(queue.size() == 0)) {
        Cell cur = queue.poll();

        for (Cell neighbor : getNeighbors(cur)) {
            if (neighbor.getPrev() == cur) {
                queue.offer(neighbor);
                g.drawLine(cur.getCol() * scale + scale / 2, cur.getRow() * scale + scale / 2,
                        neighbor.getCol() * scale + scale / 2, neighbor.getRow() * scale + scale / 2);
            }
        }
    }

    if (target.visited()) {
        Cell cur = target.getPrev();
        while (cur != start) {
            g.setColor(Color.GREEN);
            g.fillRect(cur.getCol() * scale + 2, cur.getRow() * scale + 2, scale - 4, scale - 3);
            cur = cur.getPrev();
        }
        cur = target;
        while (cur != start) {
            g.setColor(Color.BLUE);
            g.drawLine(cur.getCol() * scale + scale / 2, cur.getRow() * scale + scale / 2,
                    cur.getPrev().getCol() * scale + scale / 2, cur.getPrev().getRow() * scale + scale / 2);
            cur = cur.getPrev();
        }
    }
}
  3. Visualizing the Landscape

    Download this LandscapeDisplay class. If everything has been done correctly up to here, you should be able to run the main method of this code and see a Landscape (nothing will really happen yet, though).

    4. The GridSearch Class

    The final task (you're in the home stretch!) is to write the GridSearch class that will actually search the maze. You need a constructor that can initialize the Landscape, a LandscapeDisplay object, as well as some methods that can search the grid.

    1. Constructor and Fields

      You'll probably want to store a Landscape object and a LandscapeDisplay object as the fields of the GridSearch class, and initialize those objects with reasonable values in the constructor.

    2. Methods

      You'll be implementing two search methods: Depth-First Search and Bredth-First Search. You actually implemented Depth-First Search last week, so the pseudocode for it will look quite familiar. Breadth-First Search is morally the exact same as Depth-First Search, except that instead of using a Stack as our memory we use a queue.

      1. Depth-First Search

        Below you'll find pseudocode for a Depth-First Search algorithm. As stated above, it should look very similar to the method you created for solving Sudoku last week. 

        public boolean depthFirstSearch(int delay) throws InterruptedException {
    /**
     * Using last week's CellStack, create an empty Stack of Cells.
     * Mark the start as visited
     * Push the start onto the stack
     *
     * while the stack isn't empty {
     *   if (delay > 0){
     *       Thread.sleep(delay);
     *       display.repaint();
     *   }
     *
     *   pop a cell off the stack, let's call it cur
     *   for each neighbor n of cur
     *     if n isn't an obstacle and hasn't been visited
     *       set n as visited from cur
     *       if n is the target, return true
     *       push n onto the stack
     * }
     * return false
     */
}
      2. Breadth-First Search

        The pseudocode for BFS will literally be exactly the same as DFS, except that we'll use a queue instead of a stack.

        public boolean breadthFirstSearch(int delay) throws InterruptedException {
    /**
     * Using this week's CellQueue, create an empty Queue of Cells.
     * Mark the start as visited
     * Offer the start into the queue
     *
     * while the queue isn't empty {
     *   if (delay > 0){
     *       Thread.sleep(delay);
     *       display.repaint();
     *   }
     *
     *   poll a cell off the queue, let's call it cur
     *   for each neighbor n of cur
     *     if n isn't an obstacle and hasn't been visited
     *       set n as visited from cur
     *       if n is the target, return true
     *       offer n into the queue
     * }
     * return false
     */
}

    Exploration

    Use your simulation to explore the following questions. 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?
    2. What is the relationship between the minimal length path from the start to the target to the number of vertices visited by BFS?
    3. What is the relationship between the minimal length path from the start to the target to the number of vertices visited by DFS?
    4. What is the relationship between the minimal length path from the start to the target to the length of the path found by DFS?

      5. Include a table or otherwise present your results in your report.

    Extensions

    1. Take some time to research, implement, and analyze another searching algorithm, such as A*.
    2. Make really good tester files, and write about your choices of how to implement specific tests.
    3. Realistically, BFS doesn't make a lot of sense from a human's perspective. How are you, a human, going to continually run around the maze 'expanding' your search iteratively? Analyze the number of steps required in a grid to 'follow' BFS compared to DFS in finding the target.
    4. 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.