CSCI-4150 - Homework 2 - Due: Mon, Feb 25, 11:59:59 PM

• For this homework, you will work individually to design your strategies. However, you are encouraged to form teams of two where you test your pursuit and evasion strategies against your partner's.
• Please utilize the discussion board on WebCT to submit your questions. This would allow others to benefit from your answers. We will periodically check the board and answer your questions.
• This homework constitutes 10% of the total grade.
• Do not cheat -- we will analyze codes manually and also pairwise-compare all codes using automated software.
  

Homework Description:

You will implement a pursuit and evasion airplane game. One player, the pursuer, tries to "capture" the evader, while the other player tries to avoid capture for a certain amount of time.

Game Environment: The area is a rectangle with obstacles inside. There is a coordinate frame whose axes are parallel to the sides of the rectangle. In the code, the maximum bounds on the coordinate are given by the constants MAX_X and MAX_Y. The origin is located at the bottom-left corner.

Planes: There are two planes. One plane is the pursuit plane, colored in red, and one plane is the evasion plane, colored in blue. Each plane has a location which is represented as a point in the coordinate system and a heading which is represented as theta. Theta is zero when the plane is pointing in the +x direction and increases as the plane turns counter-clockwise. The planes are displayed as triangles with a line representing the direction the plane is facing. The dot in the plane represents the actual location of the plane with the triangle just used for visualization purposes. The pursuer plane has a yellow triangle outline in front of it which represents its capture range.

Moving: As described earlier, each player corresponds to a point with orientation. During each time step, each plane is only allowed to turn a certain amount and move forward a certain amount from its heading, denoted by the constants PLANE_TURN_LIMIT and PLANE_MOVE_LIMIT respectively. In other words, the change in the orientation and location after a move must be less than these constants. The simulation will check to see if the next move for the plane is within the move limitations and if not, then the plane will move as far as it can forward.

Collisions, Capture, Bounds and Time Limit: Collisions, capture and bounds are calculated based on the plane's location which is represented by the black dot in the middle of the plane. If this dot hits any of the blocks or the area bounds, then that plane crashes and the other plane wins. The blocks that we will be testing your algorithm with will not be may not be the same as the ones given so make sure your algorithm works with a few different configurations. If the location of the evader plane is inside the yellow outline capture triangle of the pursuer plane, then the evader is captured and the pursuer plane wins. However, if the evader plane can avoid capture until the time runs out, then the evader plane wins.

What to Implement: Each of you will implement both the pursuit and evasion strategies individually. The pairs are formed so that you can test your algorithms against each other and improve your strategies.

Code:

You will be given the code to several Java classes to help you get started: Provided Source Code. A link to the Java Math class and the Java Collections Framework is provided (bottom of page). This framework contains a lot of classes which you will find useful. Using them is very much like using the STL libraries in C++ Note that using the framework is optional. It is provided for your convenience.

GUI Controls:

• Time The current time step and the time limit
• Random Randomly places the planes on the map
• Start Starts the game
• Step Step moves the game one time step
• Stop Stops the game
• Reset Resets the game
• Trail Toggles whether to display the plane trails since the beginning
• Quit Quit

Packages:
For this homework assignment, all of the provided source code will be located within one of two Java packages. Packages in Java are a way of organizing classes in a hierarchical manner. The first non-comment line of your code must specify the package that the class is located in. This is done with the code: package PACKAGE_NAME;. Along with this, the class must be located in a folder of the same package name. This folder is then placed in the root of the source files directory instead of the .java files themselves as before. Therefore for this homework, the folders Given and Submit, not the .java files, should be placed in the root source files directory.
All of the code that you will be submitting must belong to the Submit package. This means that all of your files should be placed in the Submit folder and they all must contain package Submit; as the first line of non-comment code. You can change any of the code in the Given package but we will only be using code from the Submit package so make sure your code works with the code we provide.
Packages also affect visibility. This means there are some functions that you cannot use because your class is in a different package from the classes that we will give you. This is normal as this is a security feature of Java and the package system. Your classes in the Submit package will only be able to access variable and functions with the public keyword.

Classes:

• Given/Main.java This class will contain the main function which starts the application. It is responsible for creating the frame to hold the rest of the application. It also contains the buttons and action commands for when the buttons are pressed.
• Given/EvasionGame.java This is the main class of the game and it represents the actual game itself. It is responsible for moving the planes, getting the next locations, checking for collisions and such. This class is threaded so that you can press buttons while the simulation is running. It contains references to the planes, blocks and the constants for the game.
• Given/DisplayPanel.java This class extends a JPanel and is responsible for displaying the planes and blocks on the screen. Normally, the origin for drawing is located at the top-left corner but a transformation is used to place it at the bottom-left corner that most mathematician use. Also, the entire scene is scaled so that it will always fit in the display area.
• Given/Plane.java This class represents a plane. Each plane's location and heading is represented as a coordinate (x,y) and a theta in degrees. The coordinates and theta can be obtained from calling the getter functions. There is also a function which returns theta in radians to facilitate with using the math functions.
• Given/Block.java This class represents a obstacle which will crash a plane if it is hit. Its variable are public and can be accessed directly.
• Given/Utilities.java This class contains static functions for the game. They are used for checking collisions, capture and for drawing triangles. The given code will check for valid moves, capture and collisions but you can use these functions if you want to as well.
• Submit/PlaneMovePursue.java and Submit/PlaneMoveEvade.java These classes contain the static functions which you will be required to program. The functions will be used to move the planes to their next location. Each function will be given references to both of the planes and an array contain references to all of the blocks on the screen. These functions will return an array of doubles representing the coordinate of the plane's next location: double[]{ x coord, y coord}. The plane's heading will automatically be calculated so that it can move from the previous location to the next location. If this function returns an invalid move, then the plane make a default move which is just a certain number of steps in their current heading. You can obtain any of the game constants by calling EvasionGame.CONSTANT_NAME. These classes are also called to get the initial locations for the planes. However, if these initial locations put the planes inside of a block or the evasion plane in the pursuit plane's capture triangle, they are then randomly placed on the map.

Running the provided code:
The code given to you will be a zip file with the java files stored in a src folder with a makefile and a Manifest.txt file in main folder. The source code files are stored in two folders, Given, and Submit. These correspond to the packages that the classes are assigned to so you must make sure that the source files remain in the folder. If you are compiling and running from the command line, use the makefile with the commands "make" and "make run".
If you are using an IDE such as Eclipse or NetBeans, simply create a new project and either import the code with the IDE's functions or just copy the Submit and Given folders into whichever folder your project is saved in. When you create a new class, make sure you specify that you want the class to be in the Submit package.

Goals:

Write algorithms for the pursuit and evasion planes so that they can perform their best in any environment.

Grading:

50% will be automatically taken off from submissions that do not compile. Therefore, make absolutely sure that your code will work with the code that we provide in the Given folder.
Your algorithms will be tested in various environments so think about situations where there could be obstacles, walls, tunnels, rooms or even empty environments. Everything will be created using the Block class.
You will be graded on both the pursuit and evasion algorithms.
Runtime Time Limits: As always, the faster your algorithms can run, the better. As for a maximum limit, the entire game should take no longer than about 5 mins and each step should only take a second or two. Five points will be deducted from your grade, for each algorithm, if takes longer than a couple seconds to calculate the next plane step. This is to ensure that the assignment can be graded and returned in a timely manner.

Some of the environments used are pictured below. Their names correspond to their settings file in the "trials" folder. You will need to use the new source code provided in order to read the settings file.

cshape_e

empty

facing

multiple

rooms

trapped_e

Submitting:

Submit the following items in a zip file.

1. Everything in the Submit folder. All of the code and classes that you create should reside in this folder. You should not be submitting anything from the Given folder or anything that does not belong to the Submit folder.
2. A readme describing what files you are submitting, any problems that you encountered and anything else that you need to explain or feel that we should know.
3. A pdf file that contains both of your (pursuit and evasion) algorithms in pseudo-code and an explanation + justification of both of your pursuit and evasion strategies. In your pdf file, mention your partner's name and include the trace of three games (as pictures) you played against each other. That is, choose an initial configuration. Member A plays the pursuer, Member B plays the evader. Play the game and include the trace. Now swap the roles and play the game with the same initial configuration. Do this thrice with different initial conditions, so there will be six traces. Even though you will write your documents separately, you can use the same images in your document.

Links:

• Packages: When you make a new class, make sure you put this file in the Submit folder and put the following code as the first non-comment line in your .java file: package Submit;
• Integer Math: When you perform division with two integers in Java, the result will be an integer. So the answer to 3/2 will be 1, not 1.5. If you want to perform normal division, you must cast the numbers to doubles: (double) 3 / (double) 2 or specify them as doubles: 3.0 / 2.0.