CMSC 341 Fall 2007
Project 4
Assigned
| Wed, Nov 7, 2007
|
Due
| 11:59pm, Wed Nov 21, 2007
|
Updates
| You may assume that the keys are ints.
|
Objectives
- To implement a KDtree ADT from scratch
- To create and extend ADTs to serve a particular purpose
- To make sound design choices
- To perform file IO in java
- Optionally, to create an interactive GUI
Overview
In this project, you will implement the game engine for a very simple treasure
hunting game. Your game engine will read in the type, value, and location of
various pieces of treasure and store them in a KDtree. You will then move a
player through the game field, accumulating treasure and hazards. Graphical
display and interactive control of the player are available as extra credit
options.
Project Specification
Your project will create the basic infrastructure for a game where a player
wanders the game space and picks up all the treasure in the vicinity. Treasure is
located in discrete caches, each with a value. Each treasure cache has a type
identifier, but in the base game you may treat all treasure as the same,
distinguished only by different values. Some pieces of treasure will have negative
values, making them hazards. Like treasure, hazards have type ids which may be
ignored in the base project. A typical game strategy would be to move in a way to
pick up as much treasure as possible, while avoiding the hazards. Once a treasure
is picked up, it is no longer available, but hazards remain and can be triggered
multiple times. The goal of the game (if playing live, rather than from file
positions) is to end with the highest point total.
At game initialization, you will read the treasure file and store all items in
a KDtree to enable easy access later. The player will then be moved from location
to location, given in a file in the base project. At each location, the player
will collect treasure and trigger hazards in his vicinity. Treasure points will add to a player's
horde, while hazard points will reduce it.
The vicinity of a player is defined as any location within 5 units in X and Y, ie
a square box with side length of 10 units, centered on the player position. For a
given player position, you will traverse your KDtree to identify all treasure in
the vicinity and add it to the player's horde. Similarly, all hazards in the
vicinity are triggered. Treasure should be marked as collected; hazards remain.
The program takes five possible command
line arguments: a history flag (-h), a display flag (-d), an interactive flag (-i),
a filename for the collection of treasures and hazards, and a filename for the
player positions. The history flag is optional and the default history value
should be false. When the history flag is true, the program should print out the
KDTree containing the treasures/hazards,
treasures/hazards in range for each player position and output the resulting player
condition at each timestep.
The display flag specfies that a GUI is created to show treasure and player positions.
It is optional and defaults to false. When this flag is false
the program should be entirely text-in, text-out with no UI created.
The interactive flag specifies that player positions will come from the user, rather than
from a file of positions. This option only makes sense as an addition to the display
flag. The flag is optional and defaults to false. The display and interative options are
not required in the base program, only for extra credit.
The treasures file will contain a collection of treasures and hazards, each on
its own line. Each line will contain a type identifier, an X and Y coordinate, and
a value. Types will be strings. Values and coordinates may be positive or negative numbers.
The positions file will contain a series of player positions, each on its own line.
Each position will contain an X and Y coordinate.
A simple treasures file might look this:
g 100 200 25
g 20 40 75
g 10 50 4
g 300 300 50
g 50 350 27
g 75 75 25
g 175 175 10
s 150 150 8
s 200 39 15
s 175 100 30
h 103 200 -40
h 79 79 -30
h 10 50 -6
h 100 100 -75
This gives 14 treasure/hazard items of three different types. The first is of type g,
located at 100, 200 and has value 25.
A print out of the tree made from this file (with history set) would look like this:
g 100 200 25.0
g 20 40 75.0
g 10 50 -2.0
g 50 350 27.0
g 75 75 25.0
h 79 79 -30.0
h 100 100 -75.0
g 300 300 50.0
g 175 175 10.0
s 150 150 8.0
s 175 100 30.0
h 103 200 -40.0
s 200 39 15.0
Given a positions file that looks like this:
70 70
75 75
80 80
85 85
90 90
95 95
100 100
The player will move from 70,70 to 75,75 to 80,80 and so on.
At each position, the program should print out the
treasures/hazards found and the resulting player point value.
Player value now 0.0
At 70,70: items within 65,65 to 75,75
g 25.0 at 75,75
Player value now 25.0
At 75,75: items within 70,70 to 80,80
h 79 79 -30.0
Player value now -5.0
At 80,80: items within 75,75 to 85,85
h 79 79 -30.0
Player value now -35.0
At 85,85: items within 80,80 to 90,90
Player value now -35.0
At 90,90: items within 85,85 to 95,95
Player value now -35.0
At 95,95: items within 90,90 to 100,100
h 100 100 -75.0
Player value now -110.0
At 100,100: items within 95,95 to 105,105
h 100 100 -75.0
Player value now -185.0
Dr. Rheingans' public directory for this project is
/afs/umbc.edu/users/r/h/rheingan/pub/341/Proj4. It contains some test
files of treasure and player positions.
Project Notes, Hints, and Requirements
-
Your project must adhere to basic good design principles, including (but not
limited to) appropriate abstraction and encapulation, logical control flow,
reasonably efficient use of memory, and basic computational efficiency. If you feel
it advisable to violate one of these principles (or any others), be sure to explain
your reasons. We may not necessarily accept your reasons, but will consider them.
You may, of course, get feedback on your design decisions before the project is
due (ideally, WELL before the project is due). The safest source of such feedback is
your instructor, since s/he is the one who ultimately decides how your project will
be graded.
- This project can be developed using the Eclipse Integrated Development Environment (IDE).
- You must implement your KDTree class from scratch, with nothing but Object,
primitive types, or classes you develop from scratch yourself as a superclass
of KDTree or any data elements of KDTree. The single exception is that you may
store the treasure id at a String.
- Although this project could be accomplished with a 2tree (a KDTree with k=2) of ints,
you should write your KDTree class so that it works for any k and AnyType. Your KDTree
should be general in all other ways, rather than tied to the specific needs of this
project. You may assume that the KDTree will store a string id and an AnyType value.
The positions are used as the keys. Rather than doing game operations directly on the
tree, your KDTree should provide some sort of get method which returns a
list of items (which will be processed to
calculate score in the game driver code). You may use some type of Collection List for
this return set.
- As in previous projects, you should submit your project as a package (proj4). Your
project should be named Proj4.
- To create the file containing your output, use unix redirection on the command line to redirect standard output to a file. You can redirect your output to file by using the command java proj4.Proj4 -h treasure.txt positions.txt > p4-output.txt.
- This project is an OPEN assignment. You are still expected to write your
own code, but you may continue to help each other debug. Specifically, you:
- should try as much as possible to complete the project by yourself.
- may get assistance from anyone -- TAs, instructors, fellow students, relatives, friends, etc.
- must document all outside help you get as part of your file header comment.
You MAY NOT:
- copy anyone else's code
- have someone else write your code for you
- submit someone else's code as your own
Any help you receive must be documented, including discussion, books, papers, and web resources.
With each assignment, you will turn in a README text file indicating the sources you used while
working on it and the type of help you received from each. If you received no help, say so. If
you helped someone else, say so. Failure to include this README file will result in your program
being returned ungraded.
Extra Credit
There are MANY interesting ways to extend your base project.
Indicate any items of extra credit that you did in your README file. This will
allow the TA to look for that additional functionality when grading your
project.
-
Add a GUI display to your program. Your GUI should display the game space, treasures and
hazards, and player position.
Worth 5 points.
-
Add user interaction to your program.
In interactive mode, your player should be controlled interactively,
rather than by the positions file.
Include instructions so that the TA knows how
to control the interactve player.
Worth five points.
Files To Be Submitted
Submit the following files:
- *.java (including Proj4.java ),
- p4-output.txt,
- README,
- any items required for extra credit options
Project grading is described in the
Project
Policy handout.
Cheating in any form will not be tolerated. Please re-read the Project
Policy handout for further details on honesty in doing projects for this
course.
Remember, the due date is firm. Submittals made after midnight of the due
date will not be accepted. Do not submit any files after that time.