Graphs

The goal of this lab is to get you started on the programming project. This week you will be implementing a video game that uses a graph data structure as a fundamental component. We will create our own graph implementation during lab, and then build upon it for use in the video game.

There are several alternatives for organizing data to represent a graph. We will implement an adjacency list. Each vertex in the graph maintains a collection of adjacent vertices—we will use a Map for this collection.

---

Tasks

1. Vertex Class - Each vertex in our graph will be able to connect to up to four other vertices, one in each of the cardinal directions (north, east, south, west). Create a Direction enum (you can define this within its own file or within Vertex.java).

   Define a public static method in Vertex with signature public Direction opposite(Direction d) that returns the compass opposite of a direction (i.e. South for North...).

The Vertex class needs to maintain a Map (e.g. HashMap) of edges. Each entry in the edge map has a Direction as key and a Vertex as value. This is the primary field in the Vertex.

Create the following methods (these are all one-liners that manipulate the edge map):

• void connect(Vertex other, Direction dir)
• Vertex getNeighbor(Direction dir)
• Collection getNeighbors()

Add the fields int cost and boolean marked to the Vertex class along with associated getters and setters. These fields will be used during graph traversal.

Implement the Vertex.toString() method to print out the number of neighbors, the cost, and the marked flag.

Make the Vertex class implement the Comparable<Vertex> interface.

Create a main method that tests the Direction enum and Vertex class so far. This should, at a minimum, try the opposite method on each Direction, create at least two Vertex objects and assign different costs, compare the Vertex objects using the comparator, connect a Vertex to several others, and print out the Vertex.

2. Graph class - Create a Graph class that maintains a list of vertices (Vertex objects). Implement a int vertexCount() method. You are free to use a standard Java data structure here, such as as an ArrayList.

   Implement a void addEdge(Vertex v1, Direction dir, Vertex v2) method that adds v1 and v2 to the graph (if necessary) and adds edges connecting v1 to v2 via direction dir and connecting v2 to v1 via the opposite direction.

3. In the Graph class, add a method void shortestPath(Vertex v0) that implements a single-source shortest-path algorithm for the Graph. This method finds the cost of the shortest path between v0 and every other connected vertex in the graph, counting every edge as having unit cost. An outline of the algorithm—known as Dijkstra's algorithm—is below. Note that Dijkstra's algorithm works for graphs with non-negative weight edges, but in this case all edges have the same weight.

   Given: a graph G and starting vertex v0 in G
   Initialize all vertices in G to be unmarked and have infinite cost
   Create a priority queue, q, that orders vertices by lowest cost
   Set the cost of v0 to 0 and add it to q
   while q is not empty:
   	let v be the vertex in q with lowest cost
   	remove v from q
       mark v as visited
       for each vertex w that neighbors v:
           if w is not marked and v.cost + 1 < w.cost:
               w.cost = v.cost + 1
               add w to q
   Output: the cost of each vertex v in G is the shortest distance from v0 to v.
   

   Note that you can use Java's PriorityQueue implementation in the algorithm to always visit the next lowest cost vertex. An important implementation detail: in the last step, it is possible that the vertex w is already in the priority queue. In this case, updating the cost of w does not reorder its position in the queue because the queue has no knowledge of the modification. Adding the vertex a second time will lead to duplicate references to w in the queue. So, at the last step, remove w, then add w. This will work whether or not w is already in the queue. (This consideration is only necessary when dealing with weighted graphs, but we might as well be general here.)

4. Write a main method that tests the Graph implementation and shortest path algorithm. Create a simple graph with several vertices and run the shortest path algorithm on one of the vertices. It would be helpful to add a label field to the Vertex class that gets printed out to make this easier to visualize.

The final project uses a graph to represent a game map for the game Hunt the Wumpus, a classic RPG with very simple rules.

You have almost two weeks for this project, which will be due the last day of classes. You are free to change the rules of the game, so long as the game is still built around the idea of a graph specifiying the relationship between locations in the world.

Documentation for Java 1.6 is located at: Java 1.6 SE API

---

Problem Description

You are are a hunter exploring a cave and hunting the Wumpus, a large, smelly monster with a keen sense of hearing that lurks in the shadows.

You do not know how the cave is laid out initially—you know only how the rooms you have visited appear. As you carefully move from room to room in the cave, you will find clues that tell how far you are from the Wumpus: if the Wumpus is two or fewer rooms away, you will smell it.

If you wander into the room with the Wumpus, it will hear you and eat you. However, you are armed with a single arrow that you can fire from one room into an adjacent room where you suspect the Wumpus is hiding. If you fire your arrow correctly, the Wumpus will be slain. If you guess incorrectly, the Wumpus, alarmed by the sound of the arrow bouncing off the cave wall, will come eat you.

You have some freedom for how you choose to implement the details of this game. This guide is intentionally vague. If you want to find out more about the original game, visit wikipedia or download a nice version of the game from here.

For this project, the minimum you are implementing is a version of the game in which the only peril in the cave is the Wumpus and the hunter has a single arrow. For reference, I did not modify Landscape, LandscapeDisplay, or Cell in my implementation.

Tasks

1. Vertex class - use the vertex class to implement a room in the game. Have it extend the Cell class and implement the required abstract functions. Both updateState and isNeighbor need do nothing in the basic game. You probably want to add a new field to a vertex indicating whether it is visible or not.

   All rooms should initially be invisible except the one occupied by the hunter. When the hunter enters a room, it should become visible.

   The Vertex.draw() method should indicate several things about the room: it should show possible exits from the room and it should indicate whether the Wumpus is two rooms away or closer. Connected rooms do not need to be linked visually—if you place the rooms roughly on a grid, it will be easy to figure out where an exit leads.

   The following is a basic implementation that works well for a LandscapeDisplay scale of 64 or 100.

   public void draw(Graphics g, int x0, int y0, int scale) {
       if (!this.visible) {
           return;
       }
       int xpos = x0 + x*scale;
       int ypos = y0 + y*scale;
       int border = 2;
       int half = scale / 2;
           
       // draw rectangle for the walls of the cave
       if (this.cost <= 2)
           // wumpus is nearby
           g.setColor(Color.red);
       else
           // wumpus is not nearby
           g.setColor(Color.black);
       
       int sideLength = scale - 2 * border;
       g.drawRect(xpos + border, ypos + border, sideLength, sideLength);
       
       // draw doorways as boxes
       g.setColor(Color.black);
       if (this.edges.containsKey(Direction.NORTH))
           g.fillRect(xpos + half - 4, ypos, 8, 12);
       if (this.edges.containsKey(Direction.SOUTH))
           g.fillRect(xpos + half - 4, ypos + scale - 12, 8, 12);
       if (this.edges.containsKey(Direction.WEST))
           g.fillRect(xpos, ypos + half - 4, 12, 8);
       if (this.edges.containsKey(Direction.EAST))
           g.fillRect(xpos + scale - 12, ypos + half - 4, 12, 8);
   }
   

2. Hunter class - the Hunter should extend the Cell class. It represents the player moving around the cave. The Hunter should store a reference to its current location, which should be a Vertex object. When the Hunter's current vertex changes, it should also change its location. The Hunter is always visible on the map.
3. Wumpus class - the Wumpus should also extend the Cell class. It represents the Wumpus; in the default game the Wumpus does not move. The Wumpus should also have a reference to its home vertex. Unlike the Hunter, the Wumpus is only visible if it is killed by the Hunter or it eats the Hunter. Until then, it should not be drawn. Somehow, you need to pass in the visibility information to the Wumpus, including whether it should adopt a victorious pose or play dead.
4. HuntTheWumpus class - this class is the main game controller class. It should contain at least: a Landscape, a LandscapeDisplay, a Graph, a Hunter, and a Wumpus. Other things you may want to define are a GameState enumerated type and a status field, as in the Elevator Simulation. (The ElevatorSimulation.java file from project 7 is a nice template.)

   The constructor needs to build the graph, insert the vertices, Hunter, and Wumpus into the Landscape, and add any other user interface elements. As part of the UI setup, it should add a KeyListener and an ActionListener to the display to listen for keystrokes and clicks (if you define a quit buttom). Look at the example code from last week for an example.

   The most important function in the game is the one listening for keystrokes. My implemention uses 'wasd' functionality for moving around the graph. If the player hits the space bar, it arms the Hunter's arrow. With an armed arrow, the next 'wasd' key hit determines which direction to shoot. Hitting the space bar without hitting one of 'wasd' disarms the arrow and enables the Hunter to move again.

   In the keyTyped method in the KeyListener, you can evaluate the effect of the user's actions, changing the state of the game, the position of the Hunter, the state of the Wumpus, or the position of the Wumpus, as needed. Most of the gameplay rules are executed there.

   You may also want to implement a very simple iterate function that simply calls scape.advance(), this.display.repaint(), and then sleeps for some amount of time.

   The overall simulation should be run from the main method of HuntTheWumpus. It should also be simple: create a HuntTheWumpus object, enter a while loop that calls Iterate so long as the GameState is not Quit, then call the dispose method on the display object after the while loop terminates.

The basic game should not take a significant effort to implement. Think carefully about extensions and how you want to make it more interesting.

---

Extensions

1. Add user interface elements like a replay button that resets the game.
2. Have your game generate interesting random graphs so you can replay a different game every time. You probably still want to have rooms on a grid.
3. Make the game visually interesting.
4. Modify the rules so the game is more challenging. Think carefully about balancing the gameplay.
5. Develop your own implementations of one or more of the data structures in the project (e.g. priority queue or hash map).

---

Handin

Before handing in your code, double check that it is well-styled:

• All variable names and function names use camelCase.
• All class names are in PascalCase.
• All public classes and methods use complete JavaDoc. (Double-check this by hand; the javadoc will only point out malformed Javadoc, not alert you to missing documentation!)
• All private class members (fields and methods) have their own descriptive comment (but not JavaDoc).
• Comments are added to explain complicated code blocks.
• All variable and function names are appropriately descriptive.
• All indenting and squigly-braces are properly placed.
• Each concrete (non-abstract) class should have a unit test (main method) that calls and tests all methods in the class.

Make your writeup for the project a wiki page in your personal space. If you have questions about making a wiki page, stop by my office or ask in lab.

Your writeup should have a simple format.

• A brief description of the overall task, in your own words.
• As explanation of your solution, focusing on the interesting bits. The interesting bits here are how you modified the basic design and implemented different simulations.
• Printouts, pictures, animations, or results to show what you did.
• Other results to demonstrate extensions you undertook.
• A brief conclusion and description of what you learned.

Once you have written up your assignment, give the page the label:

cs231f13project9

You can give any page a label when you're editing it using the label field at the bottom of the page.

Do not put code on your writeup page or anywhere it can be publicly accessed. To hand in code, put it on the Courses volume in your folder within the COMP/CS231 directory.