25. Adding Randomness to a Simulation

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

 

Where Are We?

In the last lecture, 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:

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:

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 fromZeroToN( int n ) {
                int v = stream.nextInt();
                if (v < 0) v = -v;
                return v % 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.

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.fromZeroToN( size-1 );
        return outgoing.get( roadNumber );
}

But note that the above code is awfully long winded. We can rewrite it as:

        Road pickRoad() {
                // Bug: This is really dumb, drivers act as if lost!
                return outgoing.get( PRNG.fromZeroToN( 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
}