26. Yet more building a simulation

Aside?

The next machine problem requires us to think about disease transmission. If you are in a room with someone who is contageous for a minute, you have a certain probability of catching their disease. Each minute you are with them is the same. Ther is no history effect, where the fact that you were in the room with them before or not changes your likelihood of catching the disease in the next minute.

We can think of this in several ways. First, you can ask, "on the average, how many minutes must I stay in the room to have some particular chance of catching the disease?" A general answer to this question gives the probability distribution of times until you catch the disease. Here, the answer is the time until infection.

Alternatively, you can ask, "If I am in the room for so long, what is the chance that I've caught the disease?" A general answer to this question gives you the chance of infection as a function of how long you stayed.

Where Are We?

In the last lecture, we fleshed out the mechanisms to inject vehicles into the road network simulator.

private void produce( double time ) {
    waiting = waiting + 1; // add this new car to the line!
    if (waiting <= 1) { // this is the only waiting car
        Simulator.schedule(
            time + travelTime,
            (double t)-> this.leave( t )
        );
    }

    Simulator.schedule(
        time + rand.nextExponential( period ),
        (double t)-> this.produce( t )
    );
}

We made source intersections a subclass of no-stop intersections, since the logic of what a vehicle does when it is freshly produced at a vehicle source should be similar to the logic of what a vehicle does when it arrives at an uncontrolled intersection. The method leave() scheduled above goes in the uncontrolled intersection, along with the variable waiting, which counts the number of vehicles in the intersection or waiting to get through the intersection.

protected void leave( double time ) {
    waiting = waiting - 1;
    if (waiting > 0) { // let next car in
        Simulator.schedule(
            time + travelTime,
            (double t)-> this.leave( t )
        );
    }

    this.pickOutgoing().enter( time );
}

When a vehicle leaves an intersection, it checks for waiting vehicles and lets one enter the intersection if one was waiting. In any case, after it leaves, it picks one of the roads away from that intersection and immediately enters that road.

Note: we could have written the final line as:

    Simulator.schedule( time, (double t)-> this.pickOutgoing().enter( t ) );

In some languages designed for discrete event simulation, event-service routines are the only abstraction tool, so event scheduling is used instead of normal calls and programmers who learned simulation in such environments or who learned simulation from those who learned in such environmennts frequently schedule many events at the current time when a normal call would suffice.

In any case the call to pickOutgoing() referenced above is a tool that we put in class Intersection to pick an outgoing road. This tool is put in the base class because how a person navigates usually does not depend on the type of intersection.

We have not made cars intelligent here, so picking an intersection is done without any attention to the car's intended destination or travel plans. As a result, all it does is draw a random number to pick from among the outgoing roads leading away from the intersection:

protected Road pickOutgoing() {
    return outgoing.get( rand.nextInt( outgoing.size() ) );
}

The use of outgoing.get() places constraints on how we handle the collection of outgoing roads from each intersection. Java's collection framework does not support this get(i) method because collections have no implied ordering, while get(i) assumes that we can index through the collection. Java's list framework does allow this, but the efficiency get(i) depends very much on what kind of list we are using.

On a linked list, getting the i^th element requires iterating through the list from element to element, starting at the head each time. If the structure of the list changes dynamically, with lots of additions and deletions, linked lists are very efficient, but they are not effecient for indexing.

On an array list, getting the i^th element is just a matter of indexing into the array that represents the list, a very fast operation. However, addition and deletion from array lists is a bit messy, and deletion or insertion into the middle of array list is very messy.

The lists of incoming and outgoing elements for each intersection are built by adding new elements when the model is built, and then they are fixed for all time after that. During the simulation, each time a vehicle passes through the intersection, it has to index into the array list to make its navigation decision. Therefore, array lists are our favored data structure here.

Roads

We added a leave method to class NoStop but it seems that all instances of class Intersection should have leave methods, and for that matter, all intersections should also have enter methods. Similarly, all roads should have enter and leave methods.

Leaving a road implies entering an intersection, and leaving an intersection implies entering a road. As a rule, entry to a road or intersection will schedule leaving that place, and the leave method of the place will directly call the enter method of the next place. This is the model that was demonstrated by NoStop.leave above.

These methods are easy for class Road:

/** A vehicle arrives at the road entrance
 *  @param time of vehicle arrival
 *  This should be called from i.leave(), for some intersection i
 */
public void enter( float time ) {
    Simulator.schedule(
        time + this.travelTime,
        (float t)->this.leave( t )
    );
}

/** A vehicle leaves this road
 *  @param time of vehicle departure
 *  This should be scheduled by this.enter()
 */
private void leave( float time ) {
    this.destination.enter( time );
}

We could have omitted Road.leave() by writing Road.enter() as follows:

public void enter( float time ) {
    Simulator.schedule(
        time + this.travelTime,
        (float t)->this.destination.enter( t )
    );
}

The disadvantage of the above is that it doesn't allow even the simplest of adjustments to the model. Consider, for example, the possibility of travel times on roads that depend on the vehicle density. If enter() increments the population of the road, and leave() decrements the population, then population/travelTime is the number of vehicles per unit time and we can compute the actual travel time for any trip down the road as, perhaps travelTime*(1+(population/travelTime)).

When there are only a few cars on the road, the travelTime is the real time it takes to travel down the road, but as the number of cars increases, the travel time gets slower and slower. With the right scale factors, this might be quite realistic.