CS 14 - Traffic Simulator

Traffic Simulator

The University of California wants to investigate alternate programming schedules for the stop light at the corner of Canyon Crest and Martin Luther King Blvd, down by Lot 30. To help out, we have volunteered you to write a program that simulates the traffic lights and tracks the average waiting time for cars going in each direction and the maximum number of cars that are waiting at any given time.

Note: In my experience, it is hard to fully specify a non-trivial simulation. If you feel anything in here is unclear, please send a message to the mailing list. -Titus

Details

You will write a program that contains 8 instances of the Queue data type. How you implement them is up to you. You may use STL if you choose.

The 8 queues correspond to cars going in the following directions:

North to South (going straight)
North to East (turning left)
South to North (going straight)
South to West (turning left)
East to West (going straight)
East to South (turning left)
West to East (going straight)
West to North (turning left)

Note that we are ignoring cars that are turning right as they generally have a negligible effect on traffic.

Your program will begin by reading in the timing pattern for the traffic lights. The University has mandated that the lights will go in the following order, but the length of each stage of the pattern may be varied (which is what they want to use your simulation for.)

North -> South or East
North -> South and South -> North
South -> North or West
East -> West or South
East -> West and West -> East
West -> East and West -> North

This means that the cycle begins with the lights set to let anyone arriving from the north go through (either going straight or turning left), and then the green arrow turns red and the cars going from the south to the north are allowed through, and so on.

The input format for the timing pattern will simply be 6 integers representing the lengths of each stage in seconds. Each value will be at least 1. (That is, no stage can be 0 or negative duration.)

Next the input will be a series of car arrivals. Each arrival will have 3 pieces of data: the source direction ('N', 'S', 'E', or 'W'), the destination direction (also 'N', 'S', 'E', or 'W'), and the arrival time since the start of the simulation. Continue reading these until EOF. (It is likely you will want to perform all of this input before beginning the actual simulation, so store these in an appropriate data structure of your choice.)

Once the input has been read in, begin the simulation. Keep an integer variable (ie simTime) to track the simulation clock. Whenever a car arrives, put it in the appropriate queue. During each second, a single car from the front of the queues that have green lights can progress through the intersection. When all of the queues are empty and there are no more arrivals scheduled, terminate, and print out at least the following statistics for each of the 8 queues that had any traffic:

Total cars passing through
Maximum queue length
Average waiting time (sum of the waiting times / cars passing through)

A binary example of the program can be downloaded here.

Two sample inputs are available here: traffic1.in traffic2.in

Hints

You may want to have some extra functionality related to your Queue class for this assignment. I recommend implementing a Lane class that contains a queue, and keeps track of its own statistics. If you design the Lane class well, this can assignment can be done in about 200-300 lines of code.

In the sample solution, the main loops are organized like this:

while (there are more arrivals or still cars in a Lane queue)
{
    for (; time < whenThisStageEnds; time++)
    {
        while (there are more arrivals in this second)
        {
	    // Add the next arrival to the appropriate queue
        }

	// Remove up to 1 car from the head of each queue that has a green
	// light in this stage
    } 
    // Move to the next stage
}