SE450: Final Project Requirements

The Final Project gives you the opportunity to apply the object-oriented software development skills you have acquired during the course to a significant but moderately-sized application. The following sections describe the general behavior of the application, the simulation, and the deliverable requirements for the project. 

The final project for this class is a simple, flow-based traffic simulation. The O-O paradigm was founded in simulation and is an excellent means for exercising its strengths. The Simula programming language, followed by the Smalltalk environment, together pioneered the development and dissemination of O-O languages, and were first and foremost designed as simulation languages. 

An example executable is here: file:example-project.jar

Starter code for the project is here: file:myproject.zip

Alternative project: https://dl.dropboxusercontent.com/u/18837111/classes/se450notes/MITMUSIC.zip

Comment from a former student:

I recommend renaming this project the “No Pain No Gain” project. Going through it was a challenge at every step but it taught me a valuable lesson about discipline, and has also given me greater confidence in my skills as a developer. Challenges like this are the exact reason why I’m in this program; If I were trying to teach this to myself like many other developers do, I would have given up on the project long ago. But thanks to course materials, professor and T.A. support, plus the tuition money at stake, I pushed myself further than I thought I could go.

Later, from the same student:

... since SE450 I'm so much cooler at work. I rarely get paralyzed by a new challenge. My latest victory was writing a script using OO principles that makes a REST call to a third party system, gets an authentication token, uses it to get data, and inputs the data into a MS SQL database, which I then manipulate with Tableau to build some cool graphs. Except from huge guidance from StackOverflow that was all me! Probably the best tuition dollars I ever spent.

We are modeling a traffic grid with a variable number of rows and columns. For example, a 2x3 grid would look something like this:

       |     |     |
       |     |     |
  -----#-----#-----#-----
       |     |     |     
       |     |     |
  -----#-----#-----#-----
       |     |     |     
       |     |     |     

The # represent intersections, and the lines represent roads (or road segments).

We will assume that each car goes in a consistent direction (north to south, east to west, etc). Cars do not turn. All roads are one-way and have only a single lane of traffic.

We will consider two kinds of traffic patterns: simple and alternating.

In the simple traffic pattern, all traffic goes in the same direction. In the following picture, + represent a car source and @ represents a car sink. Cars flow from sources to sinks. Here is a 2x4 simple grid:

       +     +     +     +
       |     |     |     |
       |     |     |     |
 +-----#-----#-----#-----#-----@
       |     |     |     |     
       |     |     |     |
 +-----#-----#-----#-----#-----@
       |     |     |     |     
       |     |     |     |     
       @     @     @     @

In the alternating traffic pattern, roads alternate direction. Here is a 3x5 alternating grid:

       +     @     +     @     +
       |     |     |     |     |
       |     |     |     |     |
 +-----#-----#-----#-----#-----#-----@
       |     |     |     |     |     
       |     |     |     |     |      
 @-----#-----#-----#-----#-----#-----+
       |     |     |     |     |     
       |     |     |     |     |     
 +-----#-----#-----#-----#-----#-----@
       |     |     |     |     |      
       |     |     |     |     |      
       @     +     @     +     @

Sources generate cars and place them on a road. Sinks delete cars from the simulation.

The behavior of a car depends up the distance to the nearest obstacle. There are three attributes regulating this behavior, which may vary from car to car.

 maxVelocity    // The maximum velocity of the car (in meters/second)
 brakeDistance  // If distance to nearest obstacle is <= brakeDistance,
                //   then the car will start to slow down (in meters)
 stopDistance   // If distance to nearest obstacle is == stopDistance,
                //   then the car will stop (in meters)

Cars also have the following attribute, which determines how much space the consume:

 length  // Length of the car (in meters)

Suppose a car has the following values for the first three attributes.

 maxVelocity = 30.0 
 brakeDistance = 10.0
 stopDistance = 1.0

If the nearest obstacle is 12 meters away, then the car will assume its maxVelocity. If the nearest obstacle is 1 meter away, the car will stop. If the nearest obstacle is 5 meters away, the car will consider the distance to the obstacle in computing its velocity. You can use the following formula to compute the next position of the car.

double velocity = (maxVelocity / (brakeDistance - stopDistance))
                  * (distanceToObstacle - stopDistance);
velocity = Math.max(0.0, velocity);
velocity = Math.min(maxVelocity, velocity);
nextFrontPosition = frontPosition + velocity * timeStep;

Since we do not consider acceleration, you do not need to store the velocity as an attribute.

A student comment The updateVelocity algorithm allowed cars move at their maximum velocity if there were no obstacles within braking distance. However, it's possible for a slow car to be in front of a fast car, outside the fast cars braking distance but within the fast cars maximum velocity. On the next time step the fast car jumps ahead of the slow car. To clarify, a fast car has position 0, maximum velocity 30, and braking distance 10. A slow car has position 15 and maximum velocity 10. On the next time step the fast car will update it's position to 0+30 = 30, leapfrogging the slow car that is now at position 15+10 = 25. To fix this, I changed the updateVelocity algorithm to say that if there's a car outside of our braking distance but inside our max velocity, we adopt velocity of distanceToObject / 2.

Each intersection has two traffic lights; one for each direction (NS=North/South, EW=East/West). The traffic lights of an intersection are coordinated by a light controller.

Light controllers have four state: GreenNS/RedEW, YellowNS/RedEW, RedNS/GreenEW, RedNS/YellowEW. The rate at which a light controller transitions between these states is determined by two attributes:

 greenDurationNS  // Duration of the North/South green phase (in seconds)
 yellowDurationNS // Duration of the North/South yellow phase (in seconds)
 greenDurationEW  // Duration of the East/West green phase (in seconds)
 yellowDurationEW // Duration of the East/West yellow phase (in seconds)

Suppose a light controller has the following values for these attributes:

 greenDurationNS  = 55.0
 yellowDurationNS = 5.0
 greenDurationEW  = 25.0
 yellowDurationEW = 5.0

Then the light will make the following transitions:

time=0    state=GreenNS/RedEW
time=55   state=YellowNS/RedEW
time=60   state=RedNS/GreenEW
time=85   state=RedNS/YellowEW
time=90   state=GreenNS/RedEW
time=145  state=YellowNS/RedEW
time=150  state=RedNS/GreenEW
time=175  state=RedNS/YellowEW
time=180  state=GreenNS/RedEW

Intersections also have a length, and therefore may hold cars.

From the point of view of a car, an intersection is an obstacle if any of the following are true:

• The light state in the car's direction is Red.
• The light state in the car's direction is Yellow and the light is at least brakeDistance away.
• The light state in the car's direction is Green, but the intersection is occupied by cars travelling in the other direction (gridlock).

Thus, a car will ignore Yellow lights within it's brakeDistance.

All spatial units will be given as meters. All time units will be given in seconds. Use the type double to store space and time parameters.

The simulation has the following parameters.

• Simulation time step (seconds) Default=[0.1]. This indicates how much model time elapses between each simulation step. You can use this to adjust the granularity of the simulation.

• Simulation run time (seconds) Default=[1000.0]. The length of the simulation in model seconds. When the user chooses Run simulation from the main menu, this indicates how long the simulation should run.

• Grid size (number of roads) Default=[row=2,column=3]. This indicates the size of the grid. If there are 2 rows and 3 columns, then the grid looks like this:

         |     |     |
         |     |     |
    -----#-----#-----#-----
         |     |     |     
         |     |     |
    -----#-----#-----#-----
         |     |     |     
         |     |     |     
  

• Traffic pattern Default=[alternating]. This indicates how the direction of roads should vary. The choices are simple or alternating.

• Car generation delay (seconds/car) Default=[min=2.0,max=25.0]. Each car source generates cars at a fixed rate, but the sources may vary. You should set the delay between car generations by each source to be a random number between the min and max chosen here.

• Road segment length (meters) Default=[min=200.0,max=500.0]. Each road segment has a fixed length, but the road segment lengths may vary. You should set the length of each segment to be a random number between the min and max chosen here.

  Although road segment lengths vary, they will all appear the same size in the graphical output. Thus, cars will appear to move more slowly on longer segments.

• Intersection length (meters) Default=[min=10.0,max=15.0]. Each intersection has a fixed length, but the intersection lengths may vary. You should set the length of each intersection to be a random number between the min and max chosen here.

• Car length (meters) Default=[min=5.0,max=10.0]. Each car has a fixed length, but the car lengths may vary. You should set the length of each car to be a random number between the min and max chosen here.

• Car maximum velocity (meters/second) Default=[min=10.0,max=30.0]. (You get the idea.)

• Car stop distance (meters) Default=[min=0.5,max=5.0]. (You get the idea.)

• Car brake distance (meters) Default=[min=9.0,max=10.0]. (You get the idea.)

• Traffic light green time (seconds) Default=[min=30.0,max=180.0]. (You get the idea.)

• Traffic light yellow time (seconds) Default=[min=4.0,max=5.0]. (You get the idea.)

Note than some combinations of simulation parameters may not make sense. For example if the simulation time step is too large, then cars may disappear before they every display. You do not need to worry about this. Make sure that the simulation works for sensible values.

You may choose whatever defaults you like. The ones I have listed are just to get you started.

The program should be started and run from the command line.  The UI should be based on the textUI from homework 3. The main menu should present the following options:

  1. Run simulation
  2. Change simulation parameters
  3. Exit

If the user selects option 1, a graphic window appears (if there is none already) and displays the simulation using default simulation parameters.

The user may select option 1 again to continue the simulation.

Here is a use case for how one uses option 2.

a)  The user selects option 2 from main menu.
b)  The user modifies parameters.
c)  The user selects option 15 from parameter menu, returning to the main menu.
d)  The user selects option 1 from main menu (run the simulation).
    The simulation runs using the parameters that the user entered in step (b).
    (Any previous simulation is destroyed/ignored.)

If the user selects option 2, then the program should print the following options:

  1. Show current values
  2. Simulation time step
  3. Simulation run time
  4. Grid size
  5. Traffic pattern
  6. Car entry rate
  7. Road segment length
  8. Intersection length
  9. Car length
 10. Car maximum velocity
 11. Car stop distance
 12. Car brake distance
 13. Traffic light green time
 14. Traffic light yellow time
 15. Reset simulation and return to the main menu

The user will stay with this menu until they select option 15. When option 15 is selected, any previously running simulation is destroyed and a new simulation is initialized. Control returns to the main menu.

The output when the user selects option 1 should look like this:

 Simulation time step (seconds)       [0.1]
 Simulation run time (seconds)        [1000.0]
 Grid size (number of roads)          [row=2,column=3]
 Traffic pattern                      [alternating]
 Car entry rate (seconds/car)         [min=2.0,max=25.0]
 Road segment length (meters)         [min=200.0,max=500.0]
 Intersection length (meters)         [min=10.0,max=15.0]
 Car length (meters)                  [min=5.0,max=10.0]
 Car maximum velocity (meters/second) [min=10.0,max=30.0]
 Car stop distance (meters)           [min=0.5,max=5.0]
 Car brake distance (meters)          [min=9.0,max=10.0]
 Traffic light green time (seconds)   [min=30.0,max=180.0]
 Traffic light yellow time (seconds)  [min=4.0,max=5.0]

1. The application must be written in Java using the Java2 SDK 1.4 or higher.

2. All input must be text based, using a variation of the classes provided in homework 3. Graphics are used for output only.

3. Only features and capabilities that are part of the Java2 SDK may be used in the application. No third-party software such as BlueJay or JBuilder class libraries or COM/CORBA components.

4. You should must write unit tests for at least one class.

5. The application must use at least four different design patterns that we have discussed in class. You will be expected to demonstrate and explain the patterns in your final written description.

6. The application should conform to Sun's Java Coding Conventions.

Every day that you work on your project, write down the number of hours spent and what was achieved. Record any design problems or solutions you explored.

Keep this electronically. Your name at the top. Start a new paragraph for each day, indicating the date, number of hours spent, followed by comments. This should take no more than a few minutes per day.

Estimate the time you spent in the following activities:

• Design (any activity other than coding and debugging).
• Coding and debugging.
• Dealing with BIG bugs. (If a bug takes more than five minutes to fix, it is worth remembering.)

At the end of each week, compute the total time spent in each of the three areas.

At the end of the project, compute the total time spent in each of the three areas.

Thirty percent of your grade is based is based on a written report. Although no specific style guidelines are being enforced, the report must be presented in a neat, legible, and consistent format.

All text must be typed. Diagrams may be hand-drawn; however they must be neat, ie, drawn with a ruler. DL students may scan hand-drawn diagrams. The diagrams should conform to the UML notational conventions presented in class.

The written report should be structured as follows:

1. Title page with your name at the top.

2. Class diagrams for each package. Include a design class diagram for each package in your your project. Be sure to include all significant class relationships: realization, specialization, and association. Show associations as dependencies, aggregations or compositions when appropriate. Show attributes and methods only if they are crucial to understanding the class relations.

   Do not use tools that automatically generate diagrams from your code. The diagrams they produce are unreadable.

3. Sequence Diagram. Draw a sequence diagram indicating the how a car updates its position. Show all the objects involved.

4. Time Summary. Provide a table breaking down the amount of time (in hours) you spent each week in the three areas. The table should look like this:

   Week    | 1 | 2 | 3 | 4 | Total
   --------|---|---|---|---|------
   Design  |   |   |   |   |
   Code    |   |   |   |   |
   Bigbug  |   |   |   |   |
   

5. Notes on patterns. Indicate the design patterns used in your project. For each pattern, note the specific problem in your project that the pattern solved. Also indicate the classes involved and briefly discuss the implementation of the pattern. These notes should take 1 to 2 pages.

6. Successes and Failures. Discuss what went right with your project? What went wrong? Note design issues that arose during development, such as specific decisions, use of design patterns, failures, successes, etc. This should take about 1 page.

1. 2015/10/27: Initial prototype (baseline/high risk). A working program implementing limited functionality.

   Submit a jar file of your source code, as for hw 1.

2. 2015/11/03: Release 2.

   Submit a jar file of your source code, as for hw 1.

3. 2015/11/10: Release 3.

   Submit a jar file of your source code, as for hw 1.

4. 2015/11/17: Final release.

   Submit a jar file of your source code, as for hw 1.

   Test your jar file by unzipping it into a fresh directory. Make everything works.

   In class students may submit their written report on paper. You can also submit online.

   DL students may submit their report using the link provided online. You must submit a single file in PDF or DOC format. Do not submit a ZIP or other archive for your report. This requires that you somehow get diagrams into the report. Microsoft word and OpenOffice are very good at this. Please use one of them. In the worst case, print out your report and scan it in as a single PDF.

        
To get all the initial code working, you need to keep things simple.
Until I got all the distance to obstacle stuff correct, I would keep
things very simple:

Road1 and Road2 each have length 50 (positions 0-49)
Car1 and Car2 each have length 10
Car1 and Car2 each have maxVelocity 10
Simulation timestep is 1

Then we expect output something like this (with one car):

Time=1,  Car1 on Road1 at 0
Time=2,  Car1 on Road1 at 10
Time=3,  Car1 on Road1 at 20
Time=4,  Car1 on Road1 at 30
Time=5,  Car1 on Road1 at 40
Time=6,  Car1 on Road1 at 0
Time=7,  Car1 on Road1 at 10
Time=8,  Car1 on Road1 at 20
Time=9,  Car1 on Road1 at 30
Time=10, Car1 on Road1 at 40
Time=11, Car1 dies


Once you get that working, try putting Car2 behind Car1 and see if you
can get it to compute its velocity correctly.        

You can tell where how a method is being called by setting a
breakpoint in the debugger.

Or you can do:

new Throwable().printStackTrace();

or use a function something like this (from
http://mindprod.com/jgloss/trace.html):

static void imAt (PrintWriter log) {
  Throwable t = new Throwable();
  StackTraceElement[] es = t.getStackTrace();
  StackTraceElement e = es[1];
  log.println( "at " + e.getClassName()
               + "."+ e.getMethodName()
               + " line:" + e.getLineNumber() );

The real world is full of redundancy and circular references. "Mutual
experience" and "common knowledge" are standard parts of human
experience, but are completely foreign to OO programming.  In OO
programming, you are trying to eliminate redundancy and circularity as
much as possible, since these are well-known sources of bugs and
maintainability issues.

So computer models don't do things the way people do.  Compare with
our discussion of the "Observer" pattern.

It is often better to let the one with the knowledge make the choice.

When the required knowledge for a decision is spread over two (or
more) objects, the art is to decide how these objects should interact.

In the case of cars and roads/lights: the car knows its brake distance
and max velocity, the road/light knows whether the brake distance
matters and what the "next" road/light is.

Since the road's behavior depends on its actual class, it make sense
to put the code that resolves the choice in the road, rather than the
car.

You can assume that as the ArrayList of cars is iterated through, the
cars will move one at a time in the same sequence they were created.

One way to make the simulation insensitive to such
effects to to change the interface of agent from:

 Agent { void run(double time); }

to

 Agent { void setup(double time); void commit(); }

with the idea that these will always be called in alternation.  The
main loop becomes:

 for (t in times) {
   for (a in agents)
     a.setup(t)
   for (a in agents)
     a.commit()
 }

And the car becomes something like this:

 Car {
   void setup(double time) {
     _velocity = // newly computed velocity
   }
   void commit() {
     _position += _velocity;
   }