17. Yet more building a simulation

Part of CS:2820 Object Oriented Software Development Notes, Fall 2017
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

 

Where Are We?

In the last lecture, we fleshed out the stub of a road, where the simulation of the activity on the road involved vehicle entry to the road and exit from the road:

void entryEvent( float t ) {
    // A vehicle arrives at the road entrance at time t
    Simulator.schedule(
        t+travelTime,
        (float time)->Road.this.exitEvent( time )
    );
}

void exitEvent( float t ) {
    // A vehicle arrives at the road exit at time t
    // Bug:  What happens next?
}

The problem we face in fleshing out the details of how a vehicle exits a road is that the details depend on the intersection at the end of the road and whether the vehicle has to wait there. We can get something that works fairly quickly if we ignore these details:

void exitEvent( float t ) {
    // A vehicle arrives at the road exit at time t
    // Bug:  What happens next?
    destination.arrivalEvent( t );
}

We can even optimize the model to bypass exit events:

void entryEvent( float t ) {
    // A vehicle arrives at the road entrance at time t
    Simulator.schedule(
        t+travelTime,
        (float time)->destination.arrivalEvent( time )
    );
}

Testing

We now have something we can test, so it's time to do so.

Of course, none of the real intersections work, but we can get going with just source intersections and sink intersections, testing the code with something like this:

intersection A source 10.0 10 1.0
intersection B sink
road A B 5.0

We can even get ambitious, adding multiple sources or sinks:

intersection A source 10.0 10 1.0
intersection B sink
intersection C sink
road A B 5.0
road A C 10.0

Running this model, once we deal with a few annoying compile errors and other details, we discover that there is no output from the simulation, so we can't tell what happened. We hope that 10 cars were launched, one per simulated second, starting at time 10. Each of these should arrive, after a delay of 5 at the sink, so the arrivals should be at times 15 through 25.

To see if this is happening, we need to add some code to sink intersections so that they report vehicle arrivals. We can change the arrival event at the sink to do this as follows:

arrivalEvent( float time ) {
    System.output.println(
        "vehicle arrives at " + toString() + " at time " + time
    )"
}

Of course, in a production simulation, we'd probably want to gather some statistics, but the trace of vehicle arrivals tells us that quite a bit is working. Events are being scheduled and triggered, roads do carry vehicles to their destinations, and with multiple sinks, the select-road mechanism at an intersection works.

Stoplights

The problem we face in fleshing out the details of how a vehicle exits a road is that the details depend on whether the intersection at the end of the road permits vehicle entry. If vehicles have to wait, do they queue up in the intersection or on the road leading to the intersection. Both of these schemes can be made to work. Here, we'll have the queues of waiting vehicles inside the intersection.

In the real world, even at uncontrolled interesections, a vehicle might have to wait briefly for another vehicle to exit the intersection before the next vehicle enters. We'll ignore this, at least for now, and assume that vehicles pass instandly through intersections.

The Stoplight as a Process

To start, we'll begin by focusing on stop lights. Just as source intersections are processes that periodically generate vehicles, stoplights are processes that periodically allow traffic to flow through an intersection from one road or another. If we ignore the possibility of traffic sensors that control the stoplight, and if we ignore the the possibility that the stoplight might give longer green lights to one road than another, the process for each stoplight is quite simple: The stoplight initializer schedule the first light-change event, and each light-change event schedule the next.

class StopLight extends Intersection {
    private final float interval; // how long light stays green in each dir
    private int direction = 0;    // the direction that is currently green

    // constructor
    public StopLight( Scanner sc, String name ) throws IllegalName {
        super( name );
                
        interval = ScanSupport.scanFloat(
            sc, () -> StopLight.this.toString()
        )

        ScanSupport.lineEnd( sc, ()->this.toString() );

        // start the stoplight process
	Simulator.schedule( 0, (float time)->lightChangeEvent( time ) );
    }

    ...

If stop lights have behavior, we need to add variables to the light to support this. Each light could have a different timing, so we add this, and we add a variable to describe which direction the green light currently points.

The code given above extends the simulation language by making the stop light interval a parameter that is set by the model. We could, of course, make the initial light direction a parameter as well. Here is the specification of a stoplight that stays green in each direciton for 2.5 time units:

intersection X stoplight 2.5

Given this, the basic light-change process at each stoplight can be coded something like this:

    // simulation methods

    /** Process cycling through incoming roads at this stoplight
     *  @param time the light changes
     */
    private void lightChangeEvent( float time ) {
        direction = direction + 1;
        if (direction >= incoming.size()) direction = 0;

        // Bug: how does this release waiting cars?

        // schedule the next light-change event
        Simulator.schedule(
            time + interval,
            (float time)->lightChangeEvent( time )
        );
    }

Small Efficiency Questions

Note above the use of the following code framework to update the direction:

        direction = direction + 1;
        if (direction >= incoming.size()) direction = 0;

We could just as easily have written this:

        direction = (direction + 1) % incoming.size();

Why pick one or the other of these? The first one is long winded, but it uses intellectually trivial code, just assignment, increment and comparison. Any beginning programmer understands these.

The second is considerably shorter, using just the % operator instead of an if statement. The problem is, this operator that is understood by a smaller fraction of the population. In fact, one way to divide computer scientists from mere "coders" is that a computer scientist should understand the mod operator, including its strange and far from intuitive behavior with negative numbers.

But run-time efficiency also matters. The mod operator is typically computed by division, although if the dividend is a constant power of two, faster operations can be used. Division, on a typical CPU, is 10 to 20 times slower than simple operations such as addition and comparison. The net result is that the version of the code with the if statement is typically significantly faster than the version of the code using division.

But that is not true in low-performance implementations of Java. There, the overhead of the JVM may make the difference in speed between comparison and division negligible.

There is a second issue hiding here: The call to incoming.size(). For linked lists, the typical code to compute the size iterates down the list counting list elements. This can be painfully slow. The official Java documentation for class LinkedList does not indicate whether the linked list implementation keeps a running count of the number of list items. but even if it does, it would likely be faster for each stoplight to keep a field that counts the incoming roads. This count is a constant once the simulation begins because roads are not dynamically created and destroyed.

The next question is, how do stop lights interact with roads to allow vehicles to enter the intersection from only one direction at a time? And, while vehicles are waiting to enter, where (and how) do they wait.

Where do vehicles wait?

In a real road network, when entry to an intersection is blocked, vehicles wait at the end of the road leading into that intersection. Equally, we could say that the interesection includes that part of the road on which vehicles wait. Wherever it is that vehicles wait, there must be some way that the roads entering an interesection communicate with that interesection to know which road has a green light and which does not. Either:

  • The road tells the intersection what direction a vehicle is entering from so that the intersection can either let it through or make it queue up, or
  • The intersection tells the road what color the light is, so that the road can either deliver the vehicle (when the light is green) or hold the vehicle until the light changes.

Both of these alternatives can be made to work, and both of these require that the road or intersection somehow understand what direction each road enters the intersection from. Here, we will store the road's direction as an attribute of the road:

class Road {
    // default values below for errors involving incompletely defined roads
    private float travelTime = 99.99f;      // measured in seconds
    private Intersection source = null;     // where road comes from
    private Intersection destination = null;// where road goes
    private int direction;                  // which road into the destination
    // name of road is source-destination

    ...

We could set the direction directly from the input file for the simulation, but we opt to use another approach. This leaves the question open, how does the road learn what direction it enters the intersection from, and also, what do the values mean.

We could encode physical parameters such as compass direction in the variable direction, but here, we opt to simply assign integers so that the roads into an intersection are numbered consecutively starting at zero, with road numbers assigned sequentially as each road into an intersection is declared. At the end of the constructor for class Road the new road registers itself with the source and destination intersections. At this point. The code we already have is as follows:

source.outgoing.add( this );
destination.incoming.add( this );

Just before adding this road to the incoming list of the destination intersection, the length of that incoming list is the correct value for the road direction. So we change the code as follows:

source.outgoing.add( this );
direction = destination.incoming.size();
destination.incoming.add( this );

Arrival at the end of a road

When a vehicle reaches the end of a road, the driver looks into the intersection and makes a decision, step on the brakes or keep going. How do we simulate this? C.A.R. Hoare's law of large problems states: "Inside every large problem is a smaller problem struggling to get out." (Hoare invented Quicksort and was the author of one of the first Algol compilers; he taught at the Queens University of Belfast and later Oxford.) So what are the small problems waiting to be found here?

First, there is the problem of looking into the intersection. The intersection knows that it is a stoplight, and it is the intersection that determines whether the car has to wait. However we do it, we must know the direction we are arriving from.

  • If the exit event from the road is responsible for managing the queue for that road, then we could call destination.isBlocked(direction) to see if we should deliver a vehicle to the itersection, or.
  • If the intersection has queues for each entering road, then exiting the road calls destination.arrivalEvent(direction).

Assuming that the queues are part of the interseciton, the arrival event at an interseciton will look something like the following:

    void arrivalEvent( float t, int direction ) {
        // A vehicle arrives at this stoplight intersection
        if (direction == this.direction) { // light is green
            // send the vehicle on through the intersection
        } else { // light is red
            // make the vehicle wait
        }
    }

Sending a vehicle onward is merely a matter of sending it into an outgoing road. If we ignore the time it takes a vehicle to get through the intersection, we can do this with this.pickRoad().entryEvent( t ). The question of how vehicles wait poses more difficulty.

We need one queue per incoming road. A sensible way to manage this is as an array of queues, indexed by direction. If we don't have vehicle objects, our queues are simple counters of the number of waiting cars.

class Intersection {

    ...

    public String name;         // textual name of intersection, never null!
    LinkedList  outgoing; // set of all roads out of this intersection
    LinkedList  incoming; // set of all roads in to this intersection

    // queues of waiting vehicles for each incoming road
    private int[] queues; 

Here, queues is the array of incoming queues. We don't know how many incoming roads there are, so this cannot be initialized in the intersection, rather, once all of the roads have been defined, only then can it be initialized. So, it can be initialized in a sanity-check routine that runs after the road-network description file has been processed but before the simulation runs, or it can be initialized the first time a vehicle arrives at this intersection. The sanity check approach is probably best, and we really ought to have a sanity check to assure that each regular intersection has at least one incoming and one outgoing road.

Given that the initialization is done, the arrival event at an intersection will look something like this:

    void arrivalEvent( float t, int direction ) {
        // A vehicle arrives at this stoplight intersection
        if (direction == this.direction) { // light is green
            // send the vehicle on through the intersection
            this.pickRoad().entryEvent( t )
            // Bug: the above assumes that the intersection has no delay
        } else { // light is red
            // add the vehicle to the queue
            queues[direction] = queues[direction] + 1;
        }
    }

What happens when the light changes?

When a stoplight changes, all the waiting vehicles in one of the roads leading into that interseciton will be unblocked. This must happen in the StopLight.lightChanges() method, since that is the place where the program knows about the light change.

    private void lightChanges( float t ) {
        direction = direction + 1;
        if (direction >= incoming.size()) direction = 0;

        // new code
        while (queues[direction] > 0) {
            // dequeue and send a vehicle onward
            queues[direction] = queues[direction] - 1;
            this.pickRoad().entryEvent( t );
            // Bug: the above assumes that the intersection has no delay
        }

        // old code
        Simulator.schedule(
            t + interval,
            (float time)->Source.this.lightChanges( time )
        );
    }

If our model included an actual object for each vehicle, queues would be an actual array of vehicle objects, and we would write queues[direction].isEmpty instead of queues[direction]>0 and we would actually dequeue a vehicle and pass it to the appropriate outgoing entry event.

If we decide that it takes time to traverse an intersection, this code would be more complex. The loop would be a loop of events, where each event in the sequence schedules the next until either the stoplight changes or the incoming queue is empty.

What about un-regulated intersections?

So long as vehicles zip through intersections infinitely quickly, no-stop intersections are trivial. It is only when such intersections have delays that vehicles will have to stop to permit other vehicles to pass through. At that point, we'll have to add queues to no-stop intersections to hold the waiting cars.