CS 231: Lab #10

Title image Spring 2020

Graphs

The primary goal of this lab is to give you experience implementing a graph. The application is to build a simple video game that uses a graph data structure as a fundamental component. You will create your own graph implementation and then use the graph to represent the layout of the game world.

A second goal of this project is give you experience implementing Dijkstra's algorithm for computing the shortest path from a node to all other nodes in a graph.

There are several alternative designs for representing a graph. A straightforward design is to use an adjacency list at each vertex in the graph. The adjacency list holds all of the connections leaving that vertex.

Because the primary goal of this project is to give you experience with creating and using a graph, demonstrating your graph data structure and Dijkstra's algorithm will be worth 25 of the 30 points. If you choose to implement the Hunt The Wumpus game, that will be worth up to an additional five points.

Hunt the Wumpus

The particular application this week is the game Hunt The Wumpus. The Wumpus is a monster that lives in a maze (represented by a graph, where each vertex is a room). The Hunter can leave each room through a door (by default, there can be doors in the North, South, East, or West directions). Rooms can have anywhere from 1 to 4 doors.

The Wumpus is located in one of the rooms. If the Hunter walks into the room with the Wumpus, it will eat the Hunter and the game ends (Hunter loses). When the Hunter is within two rooms of the Wumpus, the Hunter can smell the Wumpus, but that doesn't tell the Hunter anything about direction. In order to kill the Wumpus the Hunter has one arrow. At any point, the Hunter can shoot the arrow in a single direction. If the Wumpus is along the path of the arrow, and there are no walls (only doors) in between the Hunter and the Wumpus, then the Hunter slays the Wumpus and wins the game.

Video: Graphs

Tasks

  1. Create a Vertex Class

    Create a Vertex class to represent the nodes in a graph. For the game application, each vertex will represent a room and will connect to up to four other rooms (vertices), one in each of the cardinal directions (north, east, south, west). In general, a node in a graph may connect to an arbitrary number of other nodes in the graph.

    The Vertex class needs to maintain a data structure that stores adjacent vertices. It is up to you exactly how to store it. A simple method is to use an ArrayList. A Hashmap or a Linked List would also work.

    In addition, the vertex needs fields for the room's position (x, y) whether a room (Vertex) should be visible, its cost or distance (from the Wumpus), whether it has been marked (or visited), and its parent on the shortes path back to the root. The latter three fields will be used during graph traversal and Dijkstra's algorithm.

    Write get and set functions for each field. You can write a single setPosition method for x and y if you wish.

    PurposeType
    Adjacency list or arrayyour choice of array, ArrayList, LinkedList, HashMap. It needs to hold stuff of type Vertex
    x coordinate of nodeint
    y coordinate of nodeint
    Is the Vertex visible?boolean
    Distance from root nodedouble
    Has the node been visited? boolean
    The parent of this nodeVertex

    Define the following Vertex methods:

    • public double distance( Vertex other ): returns the Euclidean distance between this vertex and the other vertex based on their x and y positions.
    • public void connect(Vertex other): updates this vertex' adjacency list/map so that it connects with the other Vertex. This is a uni-directional link.
    • public Vertex getNeighbor(int x, int y): returns the Vertex at position (x, y) if the Vertex is in the adjacency list, otherwise null.
    • public ArrayList<Vertex> getNeighbors(): returns an ArrayList of type Vertex which contains all of this Vertex' neighbors.
    • public int numNeighbors(): returns the number of connected vertices.
    • public String toString() returns a String containing (at least) the number of neighbors, this Vertex' cost, and the marked flag.

    Make the Vertex class implement the Comparable<Vertex> interface using cost as the value to be compared. That means the class must implement the method int compareTo( Vertex other), which returns a value < 0 if this vertex comes before other, 0 if this is equal to other, and a value > 0 if this comes after other.

    You may also find it useful to create a static function public static boolean matchPosition( Vertex a, Vertex b ) that returns true if the x and y positions of the two vertices match.

    Create a main method that tests the Vertex class so far.

  2. Define a Graph class

    Create a Graph class that maintains a list of vertices (Vertex objects). You are free to use a standard Java data structure here, such as as an ArrayList. You could also use a simple array of Vertex objects.

    Implement the following methods.

    • public int vertexCount(): returns the number of vertices in the graph.
    • public boolean inGraph(Vertex query): return true if the query Vertex is in the graph's vertex list.
    • public void addUniEdge(Vertex v1, Vertex v2): adds v1 and v2 to the graph (if necessary) and adds an edge connecting v1 to v2, creating a uni-directional link.
    • public void addBiEdge(Vertex v1, Vertex v2): adds v1 and v2 to the graph (if necessary), adds an edge connecting v1 to v2, and adds a second edge connecting v2 to v1, creating a bi-directional link.
    • public void shortestPath(Vertex v0): implements a single-source shortest-path algorithm for the Graph, Dijkstra's algorithm.

      This method finds the cost of the shortest path between v0 and every other connected vertex in the graph. The cost of an edge should be the distance between the two vertices computed using their (x, y) positions. An outline of Dijkstra's algorithm is given below. Note that Dijkstra's algorithm works for graphs with non-negative weight edges. For a fully connected grid with unit spacing, edge weights will all be one.

      Given: a graph G and starting vertex v0 in G
      	
        Initialize all vertices in G to be unmarked, have a large cost, and a null parent
        (A large cost can be 1e+7)
      	
        Create a priority queue, pq, to hold objects of type Vertex
      	
        Set the cost of v0 to 0 and add it to pq
      	
        while q is not empty:
      
          remove v from pq where v is the vertex with lowest cost
          if v is already marked as visited, continue
      
          mark v as visited
      
          for each vertex w that neighbors v:
            compute the distance between v and w
            if w is not marked and v.cost + distance < w.cost:
              w.cost = v.cost + distance
              make v the parent of w
              add w to pq
      				
      Output: the cost of each vertex v in G is the shortest distance from v0 to v.
      Each vertex also specifies its parent on the shortest path back to v0 from v.
      										

      You can use Java's PriorityQueue implementation in the algorithm to always visit the next lowest cost vertex or use your own Heap set up as a min heap.

  3. Test the Graph class

    Write a main method in the Graph class that tests the Graph implementation and shortest path algorithm. Create a graph with 5+ vertices and run the shortest path algorithm on one of the vertices. Print out the vertices in the graph prior to the shortestPath algorithm and after the shortestPath algorithm. Draw your graph in pencil and paper and make sure the results make sense.

When you are done, go ahead and get started on the project.