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:

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.