### 1. Summary

In this project, I used a graph to implement the game Hunt the Wumpus with very simple rules. A graph is a non-linear data structure consisting of vertices and edges. I implemented a game in which only a Wumpus and a hunter are in the cave and the hunter has a single arrow to shoot the Wumpus. I reused my LandscapeDisplay, Landscape, and Agent classes from prior projects. Specifically, I stored the vertices in LinkedLists and used Dijkstra's algorithm and a PriorityQueue to find the shortest path between two vertices in the graph. I also added UI elements to allow user control the actions of the player. The final game worked as expected.

1) Graph

Testing the Vertex class:

The Graph class maintains a list of vertices.

In the addEdge method, I checked the ArrayList already contains the vertices to avoid duplicates.
I used Dijkstra's algorithm to implement the shortestPath method. Firstly, I initialized all vertices in the Arraylist G to have infinite cost. And then I used java's built-in priority queue to order the vertices by the lowest cost.

Testing the Graph class:

2) Agent

The Agent class is abstract. The agents are on a grid, and each has int fields to indicate its row and column indices.

3) Landscape

The Landscape stores the agents so that they can be drawn in the proper order. It has a list of foreground agents to store the hunter and the Wumpus and a list of background agents to store the rooms.  In the draw method, it loops through the background agents first, then the foreground agents, calling the draw method on each.

4) Vertex

The vertex class extends the Agent class and implements a room in the game. All rooms are invisible initially. When the hunter enters a room, it becomes visible.

The draw method indicates doorways with black rectangles. If the Wumpus is two rooms away or closer--which I used the getCost method to determine--then the room that the hunter enters becomes red.

5) Hunter

The Hunter class extends the Agent class and represents the player. It stores a reference to its current location, currVertex. The hunter's position is associated with the Vertex it is on. I also added two boolean fields to indicate if the hunter is armed with an arrow or is dead.

For the draw method, I drew an image to represent the hunter, as shown below. I also used an if statement to check whether the hunter is dead, if it is, then it draws a String "The wumpus killed you!" on the window.

6) Wumpus

The Wumpus class extends the Agent class and represents the Wumpus who does not move. The Wumpus also has a reference to its home vertex and it is visible only if it is killed by the Hunter or it eats the Hunter. I added boolean field dead to indicate the Wumpus's alive status. In the draw method, I made if-else statements to draw different images of the Wumpus. If it is still alive, then it draws the normal image, as shown below.

Otherwise, it draws a dead Wumpus and a String "You killed the wumpus!"

7) HuntTheWumpus

The HuntTheWumpus class is the main game controller and uses InteractiveLandscpaeDisplay as a template. It contains a Graph, a Hunter, and a Wumpus.

In the constructor, I used a 2D array of type Vertex for inserting the vertices into the Landscape. Firstly, in a double for loop, I created new Vertices. Next, I used two double for loops, in which I called the addEdge method, to insert and connect the vertices vertically and horizontally. Then, I arbitrarily placed the Hunter and the Wumpus in fixed locations, set their Vetices, and added them to the Landscape's LinkedList field fgAgents. After this, I called the shortestPath method using the Wumpus as source Vertex. Finally, I used a for each loop to add the vertices to the Landscape's LinkedList field bgAgents.

Next step was to add the user interface elements.

In the HuntTheWumpus class, I made an update method that updates the states of the Hunter and the Wumpus. I moved the call to repaint function and Thread.sleep to an if case here from the main method.

I also created methods such as moveHunter, killHunter, and fire to control the Hunter's and the Wumpus's actions.

The moveHunter method updates the hunter's new location.

The killHunter method sets the Wumpus's Vertex to where the hunter is and draws the Wumpus.

The fire method first checks the bounds, and then moves the arrow all the way down in the given direction until it hits the bounds or the wumpus. If the arrow hits the wumpus, the wumpus dies. Otherwise, the wumpus is startled, moves to and kills the hunter.

In the keyTyped function inside the Control class, I added other if-else statements.

If the player hits the space bar, it arms the Hunter's arrow. Hitting the space bar a second time disarms the arrow and enables the Hunter to move again.

If the hunter is not armed with an arrow, it moves around the graph (w = up, a = left, s = down, d = right), as shown below.

With an armed arrow, the next wasd key hit determines which direction to shoot.

The game:

Shot but missed the wumpus:

Ran across the wumpus:

Killed the wumpus:

### 3. Extensions

#### 1) Make the game visually interesting.

I modified my Vertex's draw method to make the game aesthetically appealing.

I changed the rooms represented by black rectangles to images of cave-like rooms.

A room:

A smelly room near the wumpus:

If the hunter gets close to the Wumpus, then the hunter can smell the wumpus.

The green rectangles show the doorways.

#### 2) Have your game generate interesting random graphs so you can replay a different game every time.

Instead of arbitrarily choosing the locations of the hunter and the wumpus, I modified the constructor to allow it to randomly generate the hunter's and the wumpus' initial positions. And I used a while loop to check if the hunter is too close to the wumpus; if so, it relocates the hunter.

As shown below, the initial room where the hunter is and the home of the Wumpus are unpredictable, which makes the game more interesting.

Additionally, I made the constructor connect the rooms with a 50% chance by adding two if statements inside the double for loops.

The green rectangles indicate the accessible doorways. Without a green rectangle connecting two rooms, the hunter could not move from one room to the other.

I also made sure the hunter could get to the Wumpus by adding another condition in the while loop where the hunter would be located if it is too close to the Wumpus or it cannot get to the Wumpus, given the fact that the cost of getting to an inaccessible room is infinity.

#### 3) Add a replay button that resets the game.

I added another state REPLAY to the PlayState enum.

In the constructor, I also added another JButton replay and added it to the JPanel.

In the actionPerformed function, I added an if case to check if the user clicks the "Replay" button and set the state accordingly.

The main function creates a new HuntTheWumpus object if the PlayState is REPLAY.

### 4. Reflection

At the end of the project, I learned about a new data structure—a graph--and set it up by adding UI elements. I practiced implementing Dijkstra's algorithm to calculate shortest paths. Combining different data structures such as LinkedLists, Arrays, ArrayLists, and Priority Queues, I developed more profound understanding of these data structures and their advantages. The game was hard to design at first due to the complicated structures and multiple classes. I was glad to finally figure it out.

### 5. Sources

I would like to thank Professor Taylor, Professor Maxwell, and Professor Layton for all the help and the amazing semester.

I also referenced the following sources for the project:

Prashant

Roujia

Sihang

http://www.dreamcodex.com/playwumpus.php

https://gist.github.com/rcgheorghe/ce34ed6c3510dc80faf2

https://en.wikipedia.org/wiki/Hunt_the_Wumpus