Overview

For this assignment, you may work with a partner.  If you do, you and your partner should turn in only one copy of your program.  However, both you and your partner are responsible for being able to explain everything in your code, and both of you should write a separate final report.  You may choose a partner from any student in the course, not just students in your own quiz section.

Concepts

In this assignment you will 

• Gain more experience using linked lists and queues in a realistic environment.
• Learn some basics of simulations.

Like the previous assignment, this project is very open-ended.  There are some minimum requirements, which are described below.  But you are encouraged to use your imagination and creativity to produce a realistic traffic simulator (with realistic graphics!).  A small amount of extra credit will be awarded based on the quality and amount of additional features implemented.

Program Specification

Your program should begin by opening a GP142 window and creating a city grid of Road Segments and Intersections.  (The starter code does this in a simple way.) Then the simulation starts.  The program should enter an infinite loop waiting for GP142 periodic events and for each of them performing a simulation step, otherwise known as a clock tick.

The following actions must be done at each step (you may want to add others, see Extensions section below):

1. A new Vehicle may be created and enter the simulation on a random Road Segment, by adding it to the Segment's queue.  Creation of new vehicles should happen randomly.  (To make the simulation look realistic, new vehicles should enter from the edge of the picture, but if you have special effects you might want to create vehicles in the middle of the scene.)  The user should be able to change the probability that a new vehicle is created on a particular clock tick to model both heavy and light traffic conditions.  Each new entering Vehicle should be randomly assigned an X,Y position for its desired Destination.

2. For each Road Segment, all Vehicles in that Segment's queue should drive for a single step and their positions should be updated accordingly.  When a Vehicle reaches its Destination point, it should park and be removed from the simulation.  (Yes, we are assuming that you can actually find parking downtown).
3. Each Intersection should have a traffic light, which changes from red to green and back with a certain frequency (i.e., once in a certain number of ticks).  On each clock tick, vehicles that encounter a green light may pass through the corresponding Intersection.  To pass a Vehicle through an Intersection, it should be removed from the queue of the road Segment it exits and added to the queue of the Segment it enters (assuming there is room for it in the new Segment - i.e., the Segment's queue is not full).  If the new Segment has no space, the Vehicle is blocked for that tick of the clock and doesn't move.  Vehicles should move straight or turn onto a new road based upon their Destinations.  This means that the Intersection must query the Vehicle about which Road Segment is wants to proceed to.  Vehicles which encounter a red light are blocked and should not progress through the intersection at that simulation step. 

4. Each object should be redrawn (if necessary) to reflect its new state.

Implementation Requirements

• Road Chunks, which are either Road Segments or Intersections.  Road chunks form the city (at least as far as the simulation is concerned) and do not change during the simulation.  They should be created at the start of the program stored in a list (see road_chunk_list.h), and deleted just before the program terminates.

• Vehicles which enter and leave the simulation, i.e., are created and deleted, as the simulation proceeds. The program uses the convention that each Vehicle is owned by exactly one Road Chunk.  Upon a simulation step, the ownership of a Vehicle may be transferred from one chunk to another, for example, when crossing an Intersection.  (An immediate consequence of this convention is that certain operations on a Road Chunk, such as draw() and tick() discussed below, should invoke the same operation on each Vehicle that the Chunk currently owns. Likewise, when a Road Chunk is deleted, it must delete all owned Vehicles.)

An Intersection is defined as an X,Y location on the screen and is connected to the Road Segments that intersect at that point.  An intersection may include up to 8 Road Segments (2 one-way segments in each of 4 compass directions).

Both Road Chunks and Vehicles are kinds (subclasses) of Simulation Objects. The Simulation Object class defines two pure virtual functions to be implemented by all its subclasses:

• draw - displays the object on the screen by calling the GP142 graphics routines, and
• tick - defines the actions that the object should take at each simulation step.

The starter code defines the classes discussed above.  However only very limited functionality is provided.  You must expand the implementation and the class hierarchy to meet the following requirements:

• Currently a Road Segment can only hold a single car.  You should create a queue capable of holding multiple cars (up to the road length divided by the car length, for example).  The case when the queue is full should be properly handled, simulating a traffic jam.
• Using the Vehicle class as a parent class, define at least one derived class which implements a specific type of Vehicle, e.g., car, bike, truck, etc.  It is up to you what attributes to keep with each Vehicle (for example, speed and size).
• Currently, there is no method of controlling traffic at Intersections.  Implement traffic control based on traffic lights as explained above. 
• Allow Vehicles to move from their starting location to their desired Destinations.  This will entail writing code to decide which road the Vehicle should enter at each Intersection. This could be fairly simple (blindly decide what to do based on coordinates of the intersection and the destination), or fairly sophisticated (try to avoid traffic jams).

This program is potentially the most complex yet and there is a great deal of flexibility in how you design your system.  Be sure to design the program architecture on paper before beginning to code.   

Starter Code

Download the following files, individually or as a bundle:

• individually:
  • application files main.cpp, sim_object.h, road_chunk.h, road_segment.h, road_segment.cpp, intersection.h, intersection.cpp, vehicle.h, vehicle.cpp, road_chunk_list.h, road_chunk_list.cpp, position.h, position.cpp
  • and GP142 files: gp142.h, gp142.c, gp142display.h, gp142display.cpp, gp142lib.h
    (Hint: You can add many files to your MSVC project in one step.  Select Project>Add to Project>Files... .  Navigate to the folder containing the source files, select all of the ones you want to add in the Insert Files into Project dialog box, and click OK.  You don't need to add them to the project one at a time.).
• alternatively, all files as a WinZip archive for Windows or gzipped tarfile for UNIX

If you are using MSVC, create a new project, which must be of type Win32 Application.  Then add all the above files to that project.  Now you should be able to compile and run the project as-is.

If you are not under MSVC, you will need to follow the instructions at the bottom of the GP142 webpage.  Your installation is successful if you are able to compile and run the program.

Hints and Suggestions

As always, it is crucially important that you decide first what you want your program to do.  Write down sketches of the additional classes and methods that need to be written, or existing methods need to be modified, before you start coding.  Develop your program one feature at a time, debugging that feature and ensuring that the entire simulation works.  Do not attempt to implement all extensions at once.

Make a point of writing a comment before you implement a method. Document the assumptions the method makes about what to expect before and after calling it.

Make the intersection object hold and advance a vehicle, so that vehicles don't "jump" from one segment to the other. If you decide to allow multiple vehicles in a single intersection (not required), it might be useful to model the "collection of vehicles" behavior inside the class RoadChunk, and use it from both RoadSegment and Intersection.

When vehicles are advanced along the road segment, they have to keep some distance from each other. It might make sense to add some member functions to Vehicle that enable measuring the distance between two vehicles. It's not enough to know the position of each vehicle, because they might have different sizes.

Have each "border intersection", i.e. an intersection with one or more NULL Road Segments next to it, randomly create and enqueue vehicles that would "normally" come from these unexisting segments; e.g. if an intersection is only connected on the east, it should randomly enqueue vehicles so they start down the east Road Segment, as if they came from the west entry. Of course, you can choose to create vehicles in a more systematic way - maybe every constant interval.

You can use the tick() function to keep track of time; in the Vehicle class and its derived classes it can be used to modify the appearance of the vehicle (e.g. police cars with rotating lights).

Extensions

• Add more kinds of Vehicles
• Define other ways of processing traffic at Intersections, for example a 4 way stop sign.
• Add multi-lane highways.  This would require adding code to allow vehicles to change lanes based upon which Road Segment queue is shorter.
• Implement random "incidents."  These may include road construction or accidents that may close roads for a certain period of time. During this time cars must find an alternative route to their Destination.
• Unusual weather conditions - rain, snow, hail, tornados.
• Road rage.
• Drivers being ticketed and arrested for road rage.
• Encounters with alien spacecraft.
• Read the city map from a file, similarly to reading shapes in the previous homework.

This is by no means a complete list of extensions.  Use your imagination and create your own!!  Of course, before adding extensions, be sure that your program satisfies the basic requirements AND TURN IN A WORKING COPY before you start extending it.

Testing

Test the entire program on a couple of different road grids.  Observe congestions and ensure that the program behaves the way you intend.

Report

If you work with a partner, each of you should write a separate report (i.e., you must do this independently).  In addition to the other requirements, you should describe how you and your partner worked together and who did what.  Attach both reports to the final program.

Electronic Submission

When you've finished your program, turn in the source program (.cpp and .h files only) using the turnin form.  As before, you do not need turn in the GP142 files, assuming you did not change them.  If you altered GP142, you can use this other turnin form; in that case you need to turn in all of the GP142 header and implementation files, in addition to your code for this assignment.  Print out the receipt that appears, staple it and your written report together, and hand them in during quiz section.  If you worked with a partner, staple both reports to the receipt, and hand it in at one partner's quiz section.

Demonstrations

During the last week of the course, you (and your partner, if you have one) will meet with your TA to demonstrate your program and talk about it.  More details will be announced later.

Introductory Programming for the Department of Computer Science and Engineering at the University of Washington
Maintained by cse143-webmaster@cs.washington.edu