CIT 591 Assignment 5: Traffic Jam
Fall 2003, David Matuszek

Purposes of this assignment:

General idea of the assignment:

A certain number of cars and a certain number of trucks (both are vehicles) are placed randomly in an array. Each vehicle is given a destination in the array. Vehicles take turns moving toward their destinations, avoiding other vehicles in the process. The program terminates when all vehicles have reached their destinations, or when no additional moves can be made by any vehicle.

Details:

First of all, all numbers may vary. Accordingly, don't put magic numbers in your code. Get all necessary numbers (number of rows, number of columns, number of cars, number of trucks) from the command line. You will probably want to play around with the numbers to see what effect it has on the simulation.

This program is a (very crude) simulation of traffic.

This will be easier to explain if I draw some pictures. Here they are:

. . . . . e . . D .
. . . A . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. c . . . . E C . .
. . . . . . E . . .
. . . . . . . . . .
. . B . b . a . . .
. . . . . e . D . .
. . . d . . . . . .
. . . A . . . . . .
. . . . . . E . . .
. c . . . . E C . .
. . . . . . . . . .
. . . . . . . . . .
. . . B b . a . . .
. . . . . e D . . .
. . . d . . . . . .
. . . . . . E . . .
. . . A . . E . . .
. c . . . . . C . .
. . . . . . . . . .
. . . . . . . . . .
. . . . B . a . . .
. . . . . D . . . .
. . . d . . E . . .
. . . . . . E . . .
. . . . . . . . . .
. c . A . . C . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . a . . .
Initial setup. After one move. After two moves. After 3 moves.

The figures show four cars, A, B, C, and D, and one truck, EE (trucks are longer than cars). It also shows their intended destinations: A wants to go to destination a, B to b, C to c, D to d, and EE to e. You can't see destination d in the first figure because A happens to be sitting on it. Also, truck EE will have reached its destination e when either of the two E's is on e. After one turn, all vehicles have moved one step closer to their destinations(except car C, which is blocked by truck EE) . After two turns B reaches its destination, and on its next move B is removed from the array.

Vehicles can only move horizontally or vertically, never diagonally.

Trucks turn like this:

e . . . .
. . . . .
. . . E .
. . . E .
e . . . .
. . . E .
. . . E .
. . . . .
e . . E .
. . . E .
. . . . .
. . . . .
e . E E .
. . . . .
. . . . .
. . . . .
e E E . .
. . . . .
. . . . .
. . . . .

To begin:

Create an array of Vehicle. The size of the array should be given by constants (final int variables) in the program.

Initially, every location in the array will have the value null. Create a certain number of cars and place them in random locations in the array; for each car, give it a random destination that is not too close to where it starts.

For a distance measure, use the Manhattan distance: The number of rows it has to move, plus the number of columns it has to move. For example, car A has to move 6 down and 3 right, for a Manhattan distance of 6+3=9. For a minimum distance, add the number of rows to the number of columns and take 1/3 of the result; for instance, if you have 10 rows and 15 columns, use a minimum distance of (10+15)/3=25/3=8. When you choose a random destination for a vehicle, make sure it is at least this far from the vehicles initial location (and keep choosing random destinations until you get a legal one).

For obvious reasons, no two vehicles should have the same destinations.

To run the simulation:

The simulation proceeds in a series of turns. At each turn, give each vehicle a chance to move. Here are the rule for movement:

  1. If a vehicle has no move because it is already at its destination, remove it from the array, so it doesn't continue to block other vehicles.
  2. If a vehicle is on a direct line, either horizontal or vertical, to its destination, it should move in that direction, unless blocked by another vehicle.
  3. If a vehicle is neither on the correct row or the correct column, it should try first to move in the direction that it has farthest to go (for example, car A should try first to move down rather than to the right). If it is blocked from moving in that direction, it should try moving in the direction that it has less distance to go (if car A can't go down, it should try to go right). It should not move in any direction that would increase its Manhattan distance from the destination.
No vehicle should move more than one square on a turn! (This is a particularly easy mistake to make when you are moving a vehicle down or to the right.)

To end the simulation:

The simulation ends when all vehicles have reached their destinations, OR when no further moves can be made.

Requirements:

You may and should talk to a partner about how to go about coding the program. However, when it comes to actually writing code, you are to program this solo, that is, by yourself. You may not copy code from anyone else, nor may you lend your code to anyone else. Doing so is a violation of academic honesty and will result in a grade of F for the course.

You should have a Vehicle class which does the work common to both cars and trucks, and you extend it with Car and Truck classes. (The main difference between a car and a truck is how they move.)

At the beginning of the program, print out the locations and destinations of each car and truck, and display the traffic array as in the examples above. For each succeeding turn, just print out the traffic array. At the end of the program, tell whether all vehicles have successfully reached their destinations.

Due date:

Your program is due before midnight, Friday October 24. Zip up all files (.java, .class, and any extra files produced by BlueJ, such as .pkg and .pkh files), and submit via Blackboard.