15. Building a Simulation

Creating Vehicles

Our code for a departure event at a source intersection has a big hole in it:

// BUG: Must simulate the departure of a new vehicle at time t

How do we create a new vehicle? We could create an object of class Vehicle, and then pass this along through the simulation, and if we wanted vehicles to have attributes such as travel itineraries, fuel consumption records or weight, we would need to do this. On the other hand, if vehicles travel at random and retain no memory, we need not create any data objects to represent them, but we still need to deliver notification of the vehicles' travels to the roads and intersections they visit.

This leads us to the following minimal code for the departure event at a source intersection:

// simulation methods
void departureEvent( float t ) {
    // new vehicle departs at time t
    // BUG: We could create a vehicle object here.
    this.pickRoad().entryEvent( t );

    carCount = carCount - 1;
    if (carCount > 0) {
        Simulator.schedule(
            t + departureInterval,
            (float time)->Source.this.departureEvent( time )
        );
    }
}

In the above code, this.pickRoad() is the code that determines what road the vehicle will follow as it leaves this intersection. If vehicles have plans, pickRoad() will need a parameter so that it can look at the travel plan of the vehicle, but if vehicles are stupid, as in our initial model, no parameters are needed. We can simply pick an outgoing road at random.

In the above, we assume that each road object has an entryEvent(t) method that is used to tell that road that an intersection has injected a vehicle into that road at time t. If we had actually created vehicle objects, we would have to pass the vehicle itself to the road's entry event.

Here is an outline of the pickRoad() method. The code makes no pretense of being correct, but rather, outlies the steps we know we need to follow in order to randomly select a road from the list of outgoing roads in an intersection. First, we need to know how many roads there are, then we need to pick a random number in the range of outgoing roads, and then we need to select that road. It takes research to find how to do each of these steps. We will defer that, leaving the job for later, with bug comments marking our unifinished work:

Road pickRoad() {
    // BUG: Should return a random road from outgoing list.
    int size = outgoing.sizeOf();
    int roadNumber = randomIntegerBetween( 0, size-1 );
    return outgoing.memberNumber( roadNumber );
    // Bug: end of buggy code!
}

We have two choices when it comes to the road entry event. We could schedule that event at the current time, that is, we could write this:

schedule(
    t,
    (float time)->Intersection.this.pickRoad().entryEvent( time )
);

Or we could write the code already given:

this.pickRoad().entryEvent( t );

Some authors of simulation code seem to like scheduling everything, so that there are no naked calls to simulation methods in the code. Basically, this programming approach uses the scheduler as the primary control structure. The useful result of this is that all code in each event service routine is guaranteed to run to completion before any other event service routine runs, so you don't have to worry about partially completed work.

In our object-oriented framework, however, the entryEvent() method we are calling operates on roads, while the call is from within an intersection. Because of our object-oriented programming rules, there is no direct access to the fields of a road from within an intersection, so the fact that we may not be done working on this intersection event has no effect on the code for the road. As long as we are sure of this, we can safely make direct calls to the road entry event instead of scheduling that event to occur at the current time.

What does a road entry event do? As usual, we'll start by creating a a skeleton with some bug messages:

void entryEvent( float t ) {
    //Bug:  A vehicle arrives here at time t
    Simulator.schedule( t+travelTime, ()->Road.this.exitEvent() );
    //Bug:  End of buggy code
}

Here, we commit to only one detail: When a vehicle enters a road, that means that it will leave that road at the end of the road's travel time.

Picking a road

We wrote this code as a stub for work we knew we needed to do:

Road pickRoad() {
    // BUG: Should return a random road from outgoing list.
    int size = outgoing.sizeOf();
    int roadNumber = randomIntegerBetween( 0, size-1 );
    return outgoing.memberNumber( roadNumber );
    // Bug: end of buggy code!
}

It is time to flesh this out.

Methods of class LinkedList

Two of the lines of buggy code above ask for properties of linked lists, the size of the list and selecting a member of a list. Searching the methods of class LinkedList shows us that the methods we need already exist:

If x is an object of class LinkedList then x.size() gives the number of elements in the list.

Similarly, x.get(i) gets element number i from the list. It takes a bit of careful reading of the specifications to discover that for an n item list, the elements are numbered from 0 to n–1.

Class Random

The other issue that we were left with by our stub code was the problem of drawing a random element from the list. A web search for the keywords Java and random reveals that Java has a class called Random. A quick read of the documentation for this class revals that:

• It is possible to create multiple objects of this class.
• Each object purports to be able to generate a stream of random integers.
• Methods are provided to draw random floating point values drawn from various distributions including uniform and gaussian distributions. These are generated by drawing one or more integers for each floating point value.
• The integer values are not actually random, but are computed by fairly simple arithemtic that yields a result that satisfies most people's sense of randomness, except that:
• The stream of integer values will eventually repeat, and
• Each object of class Random draws from the same stream, but may start at a different point in the stream.

In point of fact, genuine physical randomness is hard to get on a computer. We design our computers to be genuinely deterministic machines. What package Random actually provides is called a pseudo-random number generator or PRNG. It behaves in a manner that is "random enough" for most purposes while being computationally fast.

Good PRNGs are extremely difficult to develop. The one provided by Java is mediocre at best. It is certainly not good enough for cryptographic use. There are cryptographic quality PRNGs, but these are computationally difficult.

The only way for the computer to behave nondeterministically is for it to extract randomness from its environment. We could:

• Measure the time between successive keypresses or mouse clicks, and look only at the fractional milliseconds.
• Use a radiation detector to measure the time between successive radioactive decay events in a chunk of radioactive material.
• Use a radiation detector to measure the time between successive arrivals of cosmic rays from different parts of the universe. (At sea level, the cosmic ray flux is approximately one particle per square centimeter per second.)

All of these techniques for extracting physical randomness from the environment can only get a few bits of randomness per second, so they are not of much use in something like a simulation program that might need thousands or millions of random integers.

Most modern operating systems include tools that attempt to extract randomness from the environment. This is extraordinarily important as a source of cryptographic keys to secure communications channels in today's hostile internet, and we can take advantage of these tools.

Specifically, the Random() initializer uses physically random numbers to set the starting point (seed) in the sequence of random numbers it draws. If you use this default approach to seeding a random number generator, your program will behave differently every time you run it, except for a very small probability that it will accidentally draw the same seed value twice. If the seed values are 32 bits, each, your program has only a 1 in 4 billion chance of repeating itself on two successive runs.

This is good enough for video games, where it would be very dissapointing if two successive runs of the game followed exactly the same scenario, but it is a real problem if you are debugging something like a video game or a simulation. When you are debugging, you'd like to have the program behave identically each time it is run on the same input, so that you can tell that the change you made actually fixed the bug.

Using class Random

Using class Random in a program requires that you import the class:

import java.util.Random;

In our case, we need only one global instance of this class, so we'll package it in our own service class and provide a utility method that gets the next random value in the desired range:

/** Randomness
 */
class PRNG {
    public final static Random stream = Random( 1234 );
    // Bug:  The above code may be too determinstic!

    /** Get random value from 0 to n-1
     */
    public static int fromZeroTo( int n ) {
        int v = stream.nextInt();
        if (v < 0) v = -v;
        return v % n;
        // Bug: above could be replaced with nextInt( n )
    }
}

The above code explicitly sets the seed, so that our program will be deterministic during debugging, with a bug notice to say we ought to change this later.

We provide a fromZeroToN() method that satisfies the needs of our original unfinished code given at the top of these notes.

Why only one instance of class Random? It turns out that, with pseudo-random number generators, it is almost always a mistake to launch multiple instances of the same generator. The problem is, the sequence of pseudo-random numbers repeats, so you can view the sequence as a cyclic sequence such as 1,3,2,4,1,3,2,4,1,3,2,4,1,3,2,4.

Setting the seed in this sequence merely determines where you start. One user would see 3,2,4,1,3,2,4,1 while another user with a different seed sees 4,1,3,2,4,1,3,2. A decent pseudo-random number generator will have a cycle that only repeats after billions of trials, and no integer will be generated twice during this cycle.

If you start two streams running from the same pseudo-random cycle, with different starting points, one stream will begin to duplicate the sequence of numbers the other stream already delivered. The best-case scenario is that one stream will be halfway through the cycle from the other, but on the average, they will be closer to each other, and their correlation will show up sooner than half-a cycle. The situation gets worse and worse if more streams are involveed.

As a result, as a general rule, you should never have more than one instance of a pseudo-random number generator in an application. In fact, the ability to create multiple instances of a pseudo-random number generator can be considered to be a design error in the Java library.

So what is a pseudo-random number generator? Here is an old one, the Park-Miller minimum standard pseudo-random number generator, that is pretty good for games and simulations, but nowhere near good enough for security critical applications:

The cyclic sequence X repeats itself after producing all integer values between 1 and 2147483646. Given any member of the sequence, the next member can be computed with just one multiplication and one mod (remainder) operation, as outlined above. The seed for the sequence, the initial value X₀ is any value in the range of the sequence. Generatgors with this structure are called linear congruential pseudo-random number generators.

Fleshing out our stub

With all of the above pieces, we can rewrite our stub code as follows:

Road pickRoad() {
    int size = outgoing.size();
    int roadNumber = PRNG.fromZeroTo( size-1 );
    return outgoing.get( roadNumber );
}

Note that the above code is a bit long winded. We can rewrite it as:

Road pickRoad() {
    // Bug: This is really dumb, drivers act as if totally lost!
    return outgoing.get( PRNG.fromZeroTo( outgoing.size() ) );
}

This code eliminates unneeded variables and includes a bug notice indicating how stupid the code is, from the point of view of simulating a real highway network.

Further development of the simulation model

Now, we are ready to do something with roads. When we created cars, we sent them to the entry point of a road by calling the entryEvent() method of that road. This is a fairly simple method of class Road. All it does is schedule vehicles to exit that road later, after traveling down 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 )
    );
}

Of course, in a more sophisticated simulation, we could make travel times vary on a gaussian distribution, with some vehicles taking longer times, and other vehicles taking shorter times.

What happens when a vehicle reaches the end of the road? That depends on whether it has to wait to enter the next intersection. We will flesh this out later:

void exitEvent( float t ) {
    // A vehicle arrives at the road exit at time t
    // Bug:  What happens next?
    // if the intersection is open, the vehicle goes on
    // if the intersection is blocked (stoplight?) the vehicle wait
}