# CS 231: Data Structures and Algorithms (Lab Page)

Project 9
Fall 2016

### Hunt the Wumpus

The final project uses a graph to represent a game map for the game Hunt the Wumpus, a classic role-playing game 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 specifying the relationship between locations in the world.

### Problem Description

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

1. Copy Agent.java, Landscape.java, and LandscapeDisplay.java from Project 5. The Landscape will now have a list of foreground agents (`LinkedList<Agent>` and background agents. The only job of the Landscape is to store them and draw them (loop throug the background agents first, then the foreground agents). Update your Landscape to reflect this simplification. Then update LandscapeDisplay, if it needs to be.
2. Vertex - update your vertex class to implement a room in the game. The Vertex class will now need to extend the Agent class, so that is has a location (row, column) and a draw method. The only method you will need to override in the Vertex class is the draw method, which will fill in its location in the grid to make it look like a room. When all Vertices (rooms) are visible, you will see a 2D grid of rooms (on the left is an image of a subset of rooms made visible).

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 gridScale) {
if (!this.visible)
return;
int xpos = this.getCol()*gridScale;
int ypos = this.getRow()*gridScale;
int border = 2;
int half = gridScale / 2;
int eighth = gridScale / 8;
int sixteenth = gridScale / 16;

// 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);

g.drawRect(xpos + border, ypos + border, gridScale - 2*border, gridScale - 2 * border);

// draw doorways as boxes
g.setColor(Color.black);
if (this.edges.containsKey(Direction.NORTH))
g.fillRect(xpos + half - sixteenth, ypos, eighth, eighth + sixteenth);
if (this.edges.containsKey(Direction.SOUTH))
g.fillRect(xpos + half - sixteenth, ypos + gridScale - (eighth + sixteenth), eighth, eighth + sixteenth);
if (this.edges.containsKey(Direction.WEST))
g.fillRect(xpos, ypos + half - sixteenth, eighth + sixteenth, eighth);
if (this.edges.containsKey(Direction.EAST))
g.fillRect(xpos + gridScale - (eighth + sixteenth), ypos + half - sixteenth, eighth + sixteenth, eighth);
}
```
3. Hunter - create a Hunter class that extends the Agent 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. You will need to override the draw method. When you do so, be sure to use the position associated with the Vertex it is on, rather than the row, col position associated with the Hunter itself.
4. Wumpus - create a Wumpus class that extends the Agent 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.
5. HuntTheWumpus - create a 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. You can use Basic.java as a 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 button). Look at the code in Basic.java for an example.

The most important function in the game is the one listening for keystrokes. My implementation 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 `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

Each assignment will have a set of suggested extensions. The required tasks constitute about 85% of the assignment, and if you do only the required tasks and do them well you will earn a B+. To earn a higher grade, you need to undertake at least one extension. The difficulty and quality of the extension or extensions will determine your final grade for the assignment. One significant extension, or 2-3 smaller ones, done well, is typical.

1. Use your own map, i.e. use BSTMap. Or, even better, make your own new map class, such as a Hashtable, and use it.
2. Add user interface elements like a replay button that resets the game.
3. Have your game generate interesting random graphs so you can replay a different game every time.
4. You probably still want to have rooms on a grid.
5. Make the game visually interesting.
6. Modify the rules so the game is more challenging. Think carefully about balancing the gameplay.
7. For any assignment, a good extension will be to implement a Java class yourself and demonstrate that it has the same functionality as the Java class. For example, you could implement your own ArrayList class for this assignment.
8. For any assignment, a good extension will be to annotate your code to indicate all places where memory is "lost" (in other words, each place where the last remaining reference to an object is either destroyed or is given a new value). If you do this extension, please indicate so in your write-up.

### Handin

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.
• An explanation of your solution, focusing on the interesting bits. The most interesting bits for this project is your gameplay implementation. You can include code snippets in your writeup to help describe your solution. A code snippet is usually less than 10 lines of code.
• Specific!
• Printouts, pictures, or results to show what you did. For this assignment, you should include an animated gif of at least one game being played.
• Other results to demonstrate extensions you undertook.
• A brief conclusion and description of what you learned.
• A list of people you worked with, including TAs, and instructors. Include in that list anyone whose code you may have seen, such as those of friends who have taken the course in a previous semester.

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

`cs231f16project9`

You can give any wiki page a label using the label field at the bottom of the page. The label is different from the title.

Do not put code on your writeup page or anywhere it can be publicly accessed. To hand in code, put it in your folder on the Courses fileserver. Create a directory for each project inside the private folder inside your username folder.