Skip to end of metadata
Go to start of metadata

Introduction:

The main data structure for this week's project was graph, which is a non-linear data structure like tree.  However, graph is fundamentally different from tree because each data can be connected to every other data.  Graph was an essential component of this project's game - Hunt The Wumpus - in order to color the grid cells close to wumpus differently.  Graph{}'s shortestPath() method implemented Dijkstra's algorithm to calculate the costs of grid cells from wumpus.  A brief overview of the game is that hunter seeks wumpus to kill it by looming around the grid cells.  To implement the game, I created following classes in addition to graph class: Vertex class to represent each grid cell (or cave room), Hunter class for hunter, wumpus class for hunter, landscape class modified from project 5, Agent class modified from project 5, and lastly HuntTheWumpus class, which puts other classes and uses java's swing package to create GUI for the game.  This project initially seemed similar with the simulation projects, such as game of life and check-out lines.  However, it was ultimately different because it didn't involve updating the status of agents like vertex, hunter, and wumpus.  The challenge was rather to figure out how to integrate different agent classes, landscape, graph, and user interface elements into one class.

Main Code:

Vertex{}

Vertex class represents a cave room, or a grid cell of the graph.  It can be connected to other vertices through cardinal directions(north, east, south, west) and stores information regarding its neighbors, position, cost, and whether it is marked (this is for shortesPath() method), and visibility information.  I saved the neighbors in java's built-in hashmap so that it would be easier to identify a neighbor with particular direction.  Hashmap's (key, value) feature was handy in Vertex's draw() method.

(Snippet 1.)

Graph{}

Graph class maintains a list of vertices, in my case as an arrayList, and establishes links between the vertices.  It is essentially a map of the game; however, it is different from landscape because it does not involve any drawing of the agent classes.  When compiling and running my Graph.java please provide one command line argument: 0 to implement java's built-in priority queue or 1 to implement my own PQHeap.  I will explain my implementation of PQHeap in the extension section.

Based on shortestPath() and draw() method of vertex, grid cells that are two distances away from wumpus will be colored red.  The rest will be colored gray.  The corridors to the nearby grid cells are colored yellow.  See Figure 1. for an illustration.

 (Figure 1.)

Note that green square is the wumpus, and pink circle is the hunter.  I manually set the visibility of wumpus and all vertices to true just for an illustration.

Agent{}

This agent is identical with that from project 5.  It was copied in order to group Vertex, Hunter, and Hunter class as one and enable to call same method on them collectively in LandScape class.

Hunter{}

Hunter class stores information regarding its location, i.e. the vertex it is currently in, and its visibility status.  Hunter is a pink circle; when it's dead, it will simply disappear from the window.  I added set/get methods of its location to Hunter class for user interface elements in HuntTheWumpus class.

Wumpus{}

Similar to Hunter class, Wumpus class stores information regarding its location and visibility status.  In addition, it contains a field about how to pose depending on the result of the game.  In case of hunter's defeat, it will appear on the window and be colored green like in the above illustration.  If hunter succeeds in killing wumpus, wumpus will disappear and be colored red.  See below Figure 2.

 (Figure 2.)

Landscape{}

Landscape class is slightly modified from that of project 5; its main functionality is still to draw all the agent classes in it.  In addition, it now adds foreground agents - Hunter and Wumpus - and background agents - Vertex - to two separate LinkedLists and stores the lists separately.  The reason is that vertices need to be drawn first, and then hunter and wumpus if applicable.  Therefore, Landscape class's draw() method draws background agents first.

 (Snippet 2.)

HuntTheWumpus{}

HuntTheWumpus is a lengthy class because it contains java swing's GUI and user interface elements in addition to landscape, graph, 2D array for graph, hunter, wumpus, and other necessary instance variables.  Note that I did not create a separate LandscapeDisplay class; everything happens in HuntTheWumpus class.

In the main constructor, I initialize the given fields and first build a 2D array of vertices through a nested for-loop.  Then I repeat another nested for-loop twice to add the vertices to the graph and connect them in every direction: North, East, South, West).  Once graph, hunter, and wumpus are set up, I call shortestPath() method to calculate the distances of grid cells from wumpus.  Then I add the vertices, hunter, and wumpus to the landscape.  Finally, I add the user interface elements to the main frame.


In order to play this game, user must use wasd functionality to move around the hunter (w = up, a = left, s = down, d = right).  User can armed the hunter's arrow using spacebar.  Once armed, hunter cannot move.  wasd will indicate the direction to shoot the arrow instead of moving the hunter.  User can disarm the hunter's arrow and enable hunter to move again by clicking (lowercase L).  

My user interface elements are essentially controlled by the texts of JLabels that I created such as status(whether hunter's arrow is armed) and outcome(whether hunter won or lost).  For example, key w will move the hunter to north as long as hunter is unarmed and not lost.  See below snippet for detail.

 (Snippet 3.)

In order to run HuntTheWumpus class, user must provide three command line arguments: 1) number of rows/columns to create, 2) which implementation to use for shortesPath() method: 0 for java's built-int priority queue or 1 for my own PQHeap implementation, and 3) number of rows given to the hunter.  If user types 7, 0, 3 as arguments, the program will create 7x7 grid of vertices and give three arrows to the hunter.  More details about the arguments are provided in the extensions section.

 (Figure 3.)

Extensions:

  • Use your own priority queue (heap) implementation. For real extension credit, do something that compares your PQ with the built-in one.

In order to enable my PQHeap to remove a specific node to be removed, I created a new method remove(T element), which removes a specific element instead of the head of the queue.  Then I created removeDown() method based on reheapDown().  The difference is that the outOfPlace index is where the element was removed rather than the head of the heap.

Once I confirmed that my own PQHeap implementation works (because shortestPath() method colors correct grid cells red), I compared java's built-in priority queue and my PQHeap's time performance.  In the main method of Graph class, I created add 250000 vertices to the graph and ran shortestPath() method.  Java's built-in priority was about 10 milliseconds faster than my PQHeap implementation.  

When running Graph class, provide one command argument: 0 for java's built-in priority queue or 1 for my PQHeap implementation.

 

  • Add user interface elements like a replay button that resets the game.

I added three JLabels.  From the right, 1st label indicates the number of left arrows to shoot; 2nd shows the armed status of hunter, either Unarmed or Knock!!!; 3rd shows the output of the game, either TBD, LOST, or WIN.  Lastly, I added quit and reset button.  Reset button locates hunter and wumpus to new random locations.  In addition, it restores initial status of JLabels and calculates the distances of vertices again using shortesPath() method.

 (Snippet 4.)

 

  • Make the game visually interesting.

I colored vertices, hunter, wumpus, corridors, and background all differently.
 (Figure 4.)
  • Modify the rules so the game is more challenging. Add traps, transporters, or additional levels. Think carefully about balancing the gameplay.

In order to make the game more challenging, I added an additional element, number of arrows.  Throughout the game, hunter can only have limited number of arrows to shoot.  I incorporated this by adding a new integer instance variable count and used it to control keyListener actions.

 (Snippet 5.)

Once the number of possible arrows becomes 0, hunter loses.  I found that it is challenging to play HuntTheWumpus when the number of rows/columns is 5 or smaller, and the number of possible arrows is 3 or smaller.  Below is the demo of playing the game.

Demo.mov

Conclusions: 

This final project was the most challenging one this semester.  It was difficult to understand the functionality of graph and incorporate it into game like HuntTheWumpus along with other components, such as user interface elements.  However, this project taught me a lot about designing and debugging codes.

I received help from TAs and professor Maxwell.

 

Labels