CSCI-4150 - Homework 4

• For this homework, you will work individually to design your strategy.
• 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 musical cars game. The objective is to get your car from the starting position to being parked in a parking spot as soon as possible.

Game Environment: The area is a rectangle without 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. It is the same environment used as the Pursuit Evasion game.

Cars: There are multiple cars on the map at a time, one of which you will control. Each car has a location which is represented as a point in the coordinate system and a heading which is represented as an angle. The heading is zero when the car is pointing in the +x direction and increases as the car turns counter-clockwise. The cars are displayed as rectangles with a line representing the direction the car is facing. The dot in the center of the car represents the actual location of the car, with the rectangle used for collision and visualization. This is similar to the Pursuit Evasion game with the planes. If selected, the next step of the car will be displayed as a black outline.

Turns: The game uses discrete time or in another words, it's turn based. At every time step, the main application goes through the list of cars and asks for their next action. Each car object will have a Driver object which is the class you will be coding. So essentially, at every time step, the main class will call your driver class for the next action. Your driver class will be given a car which represents the car you control, an array containing all of the other cars and an array containing the green centers all of the parking spaces. When you access a car, the position that you will be getting will be their current position and heading. To give you a better feel of the game, this is the logic the main application will follow (only applies to cars that are not done):

1. Go through and call every car's nextAction function which will call the car's driver's getNextAction function
1. If the action is to move, save the new location as the next position, heading and car shape. You will not have access to this next position and location, only the car's current position and location.
2. If the action is to change direction, save the new direction as the next direction.
3. If the action is to claim a spot, check to see if the car is in that parking spot with the correct orientation. If it is, then the car is done. Otherwise, do nothing and continue with the next car in the list.
2. Go through and check every car to see if it in bounds or in a collision. This is done with the car's next position, not their current one. If the car didn't move, it uses their current position to check. If a car is out of bounds, it will be reset in the next step. If the car is in a collision, both cars will be reset unless the other car is done.
3. Go through all of the cars and reset any with the reset flag. If a car does not need to be reset, it's current position/shape/direction is set to the values stored in the next position/shape/direction.
4. Repeat 1-3

Next Action: You (the driver), can have your car perform any of the 3 actions when it is your turn. You can have your car move in its current direction by returning an angle, change its moving direction or claim a parking spot. You will return a double array in one of the three following formats depending on what you want your car to do:

double[0] = Consts.ACTION_MOVE
double[1] = angle to drive in. 0 = straight, + = left, - = right. Angle must be less than the turn limit defined in the Consts class

OR

double[0] = Consts.ACTION_CHANGE_DIR
double[1] = direction to change to. 1 = forward, 0 = stay still. -1 = backwards

OR

double[0] = Consts.ACTION_CLIAIM
double[1] = index # of parking spot to claim

Parking: During your move, you can claim a parking spot by returning the index of the spot you are claiming. By doing so, the game will check to see if your car is in that parking spot (center of your car is in the green square) and with the correct orientation (parallel to the space, facing either forward or backwards, give or take a few degrees). If these conditions are met, then your car will be set to done and you have accomplished the goal of the game. The black parking spot lines do not represent bounds and can be driven over.

Collisions, Bounds and Time Limit: Collisions and bounds are calculated based on the cars's location which is represented by the black dot in the middle of the car. If this dot hits any of the other cars' rectangles then those cars will be reset. When a car is reset, it will be sent back to its initial starting position. The reset function will be called in the Driver class in case you want to perform any operations when this happens.

What to Implement:You will implement a strategy to park your car in any of the parking spot.

Trial Run: You can submit a copy of your code by the trail run due date if you want to see it tested in class on April 3rd. Simply submit your code through the submission system for the trail run assignment. Your car will be placed with anyone else who submitted their cars and the game will be run in class to give you a preview of how your algorithm might perform with other cars. This is optional.

Code:

You will be given the code to several Java classes to help you get started: Provided Source Code and Java Docs for all public classes and functions.
A link to the Java Math class and the Java Collections Framework is provided (bottom of page).

GUI Controls:

• Time The current time, step and the time limit
• Random Randomly places the cars in the garage
• 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 car trails since the beginning
• Next Toggles whether to display a car's next move
• 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.[YOUR RCS ID] package (without brackets). This means that all of your files should be placed in a folder with your RCS ID inside the Submit folder and they all must contain package Submit.[YOUR RCS ID]; 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.[YOUR RCS ID] package so make sure your code works with the code we provide.

Packages also affects 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.[YOUR RCS ID] package will only be able to access variable and functions with the public keyword. To see the public functions you have access to, take a look at the HW 4 Java Docs

The folder format should be as follows: [project root]/src/Submit/[YOUR RCS ID]/*.java

Classes:
Please see HW 4 Java Docs for all given public classes and functions.
You will be implementing a class called Driver which implements the Given.IDriver interface. This is where you will return the next action you want your car to do. This class belongs in the Submit.[YOUR RCS ID] package. If you want, you can make a copy of one of the folders for the sample cars in the Submit folder, change the folder name and the package line in the Driver.java to your RCS ID. Any other class you want to implement will go in this folder as well.

Loading cars:
You can load cars in one of two ways:

• Since the submission format is that each folder/package in the Submit folder/package contains a Driver class, the application will list all of the folders in the Submit folder and create a Driver class (and a Car) for each of them. This is defined as the function loadCarsNameArray(carNames); on line 48 of the MusicalCars.java file.
• You can also load the cars by specifying the name of one of these folders and the number of cars to create using the Driver class in this folder. This allows you to create multiple cars of using the same driver. This is defined as the function loadCarsSameName([FOLDER NAME], [NUMBER OF CARS]) on line 47 of the MusicalCars.java file.

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.[YOUR RCS ID] package.

Goals:

Write an algorithm for your car so that it can get to and park in a parking spot as quickly as possible.

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.

Testing: Your algorithms will be tested in a similar environment but with different number of cars and arrangements. You will always start out in a garage surrounded by other cars with rows of parking spaces in front of you but the number and orientation of the parking spaces will be different. You can see an example of this if you comment out loadCarLots() and uncomment loadCarLots2() around line 57 in MusicalCars.java. The only obstacles will be the other cars.

Algorithms: Your algorithm will be graded on its complexity, robustness and efficient. An greedy algorithm that simply moves towards the closes parking spot will not receive as many points as one which predicts where the other cars are going, picks the best path to avoid them using heuristics and/or search functions. Also, points will be taken off if your algorithm simply runs your car into other cars. Think of intelligent algorithms

Runtime Time Limits: As always, the faster your algorithms can run, the better. As for a maximum limit, each step should only take a second or two. Five points will be deducted from your grade, if takes longer than a couple seconds to calculate the next car move. This is to ensure that the assignment can be graded and returned in a timely manner.

Submitting:

Submit the following items in a zip file.

1. Everything in the Submit/[YOUR RCS] 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/[YOUR RCS] folder. Your folder should also contain the Driver.java class which implements the IDriver interface. This is where your algorithm will interact with the rest of the project. You can submit any other classes you want, as long as they're in the same 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. You do not need to submit this for the trial run.
3. A pdf file that contains your algorithm in pseudo-code and an explanation + justification of your strategy. Play the game and include a trace or two of your car's performance. You can use the musical cars layout or the vertical facing layout. The other cars can be the sample cars or copies of your own car. You do not need to submit this for the trial run.

Links:

• Packages: When you make a new class, make sure you put this file in a folder with the name of your RCS ID. Then, put this folder in the Submit folder and put the following code as the first non-comment line in your .java file: package Submit.[YOUR RCS ID]; without the brackets.
• 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.
• Static Imports: If you want to use the constant variables from the Const class without always referring to them as Consts.VAR_NAME, you can use static imports. You simply import the Consts class with the following line: import static Given.Consts.*; and then you can use the variables with just their names.