- Case StudyHelp.com
- Sample Questions
CS 367: Introduction to Data Structures
The goals of this assignment are:
- Understand and implement the Graph ADT
- Understand and implement BFS, DFS, and Dijkstra’s Shortest path graph traversal methods
- Complete a class implementations according to their design.
- Complete implemenation of an interesting game that can be configured in a variety of ways.
- Learn about graph traversals by playing the game.
You are the Batman of Madison and you are going to catch the spy moving across our city. If he is not caught within a particular time frame (a number of steps-moves), he will invoke a macroscopic black hole that will suck us all into it. Save Madison!
The spy moves randomly in the city and you move around searching for him. You can also use a limited number of your spycams to catch the spy, since you cannot be everywhere! You win when you catch or surround him before the time expires. If not, the Spy wins.
You will be implementing an interactive game that will allow the player to take various actions by typing a command. If the player lands on the same location as the spy or successfully surrounds the spy before the number of steps is reached, the city is saved..
We have coded the
Game class for you and this will handle much of the game play once you implement the missing classes. At the start of the program, the input files are read and the game parameters and
SpyGraph are initialized. Next, the player is asked for their name and a brief help instruction is provided.
java Game config1.txt area1.txt Enter the name of your player: Bucky Badger Your random starting location is a Type 'h' at any time for a list of commands. Enter command:
Various areas in Madison are modelled as a graph. Each location represents a vertex or node in the graph and the road connecting between the two locations represent the edge between the nodes. In addition, each road has a toll fee (weight) that should be spent in order to use the road. The player and spy start out at a random spots in the city. As a player, enter your name, and then choose your action to wisely to catch the spy before time expires. At each instant of time, the player has the following set of actions to choose from:
All commands can be activated with the first character. 'budget' prints the money you have remaining to use on moves. 'clock' returns the number of moves remaining. 'drop' places a spycam at your current location if there is one available. 'get NODE' retrieves a spycam from NODE if NODE has a spycam 'location' prints your location 'move NODE' moves you to NODE if possible. 'neighbors' prints all neighbors of your location and the cost to get there. 'onspy' tells you if you are at the same location as the spy and decreases your budget by a prespecified amount 'path NODE' prints three possible paths from your location to NODE using DFS, BFS, and Dijkstra's 'quit' ends the game 'spycams' prints the nubmer of spycams remaining and the locations of placed spycams.
The spy will periodically reveal their location and this will help you to make a better decision when choosing the next course of action to catch the spy.
If you catch the spy, you’ll see the win message:
GAME OVER, spy is surrounded. Bucky Badger wins! Spy is at node e Player is at node f
If you don’t catch the spy, you’ll see this message:
GAME OVER, you did not find the spy, spy wins Spy is at node red_gym Player is at node gordon_commons
Specifications (and files for download)
There are several files provided to you. They can be found in the provided_src folder.
You must implement the missing classes for the program. See the javadocs lines for each class for details about the
public members required for each required class. You may add
private methods, but not
package visibility methods or other classes. You may not edit the classes that have been provided with the exception of the
Test.java class. You may edit this class in any way you choose for individual unit or other testing. There is no requirement to handin
Test.java class. There is a DFS and BFS test that you can try on your SpyGraph when you have completed that and the Neighbor class. Be sure to have the test_area.txt file in the same folder, or change the path name for that test.
You will need to implement:
SpyGraph (javadocs) – represent the game space as a graph with a spy hiding and a player trying to find.
Among other methods, you will need to implement the Breadth-First Traversal and Depth-First Traversal algorithms. You may also implement Dijkstra’s Shortest path algorithm, but this is not required. When the player selects
path NODE, the Game class will call these methods to display different path options from the player current location to the desired node location. Recall and implement the algorithms for these traversals from lecture. Be sure to choose in alphabetical order (of uninvited nodes) when you have a choice. Hint: Graph Node and Neighbor are comparable, so collections of them can be sorted by calling the sort method on the collection.
GraphNode (javadocs) – represent a vertex (node) of the game space where the Player and Spy can be located.
Instances of this class maintain a vertex name and a list of adjacent vertexes (neighbors) and supporing operations. It is comparable by vertex name (so it can be sorted) and its neighbors are returned in a list that can be iterated through. Our implementation maintains the neighbors in a sorted list to ensure that the “367 convention” for picking nodes alphabetically is preserved.
Player (javadocs) – stores information about the player, like name, budget, spycams, etc.
This is probably a good class to implement first. There is no skeleton provided. You are required to implement the public methods that are described in the javadocs for this class. Try writing some test methods for your Player class in the Test.java class
Neighbor (javadocs) – each edge between nodes is represented as a Neighbor (of the first node in the pair of nodes).
The Neighbor class represents an edge between two nodes. Each GraphNode maintains a list of its neighbors. When, an edge is found in the area input file, each node becomes a neighbor of the other node. Each edge also has a cost or weight. It is the instance of the Neighbor class that stores this cost.
Be sure to implement each class as it is described in the javadocs. Failure to implement each class according to its specifications willl result in points lost for that class.
Input Files: Used to configure the game
To configure different game play, the program requires two input data files entered as command-line arguments. The names of these two files must be included as command-line arguments in your build process. The configN.txt file is listed first and the areaN.txt file is listed second. We provide the sampel files input files, but you can try your hand at making your own also.
A text only file that contains the area information (the graph information), that is, the locations(nodes) and paths(edges). The contents of the area file will follow this form. The NODES section lists the node names and the EDGES section lists the edges between nodes that exist. The
Game class will parse these files for you, but you must have the
SpyGraph complete before this can by completed correctly. Each line following the line “NODES” represent a node in the graph. Each line following “EDGES” specifies an edge between the two nodes
NODES a b EDGES a b 1
The graph described by this area file has two nodes, “a” and “b” and one edge, between “a” and “b” with a cost or weight of 1. That means it will cost 1 unit of your budget to move from a to b or b to a. The graph is undirected and constructed from
GraphNode instances that are linked together according to the edge list.
config.txt file gives information about the parameters required for the gameplay.
REVEALSPY 2 MOVES 10 BUDGET 15 SPYCAMS 3 UNIT pound COST 2
- UNIT specifies the currency type.
- BUDGET is the total amount money units you are allowed during the entire gameplay. This budget is used to spend on different moves during game play.
- REVEALSPY is the number of time units after which the spy reveals his location. These hints help the player follow the spy.
- MOVES is the total number of moves along paths the player has to find the spy during the entire gameplay.
- SPYCAMS is the number of spycams the player has available to drop in an effort to surround the spy.
- COST is the cost of checking if the spy is in your location or not.
To help you understand the game play, we have created several sample runs for you to review.
After you have read this program page and given thought to the problem we suggest the following steps:
- If you are working with a partner, review the rules for pair programming and register your partnership using the 367 Forms before 10 PM ON MONDAY, 5/2. After this deadline you’ll need to work individually.
- Review these style and commenting standards that are used to evaluate your program.
- You may use the Java development environment of your choice in CS 367. However, all programs must compile and run on the lab computers for grading. If you are going to use the CS lab computers, we recommend that you use Eclipse. You may want to review the Eclipse tutorial to learn the basics. Note: On the Linux lab computers, enter “eclipse&” to launch Eclipse at the prompt instead of what is described in the tutorial.
- Download the files from the following link for your programming assignment 5. The files are in pairs, one config and one area file for each type of Spy game you can try.
- provided_src files : the source files we provide and a skeleton for SpyGame.java (you must write your own Player.java and Neighbor.java source files)
- input files : several config.txt and area.txt pairs for different game play. May add more.
- sample runs : showing the program’s user interface
Do not use a package name for your program.
- If you are not using the lab computers to develop your program, make sure you compile and run your program to ensure that it works on the Linux lab computers. You can compile your Java source using javac in a terminal window as in this example:
javac *.javaand then run your program with the input files listed as command-line arguments as in: java Game <Config(number).txt> <Area(number).txt>
- Submit your work for grading.
Submitting Your Work
Make sure your code follows the style and commenting standards used in CS 302 and CS 367.
All submitted classes should belong to the default package.
If you are working with a partner, only one partner needs to submit.
Submit the following files by the due date and time (or refer to the late policy) using the 367 Forms:
Please CHAT WITH LIVE Assignment Advisor to know more about Referencing styles and Citations.
Chat with our 24 x 7 Online Agents CLICK CHAT NOW