15. Building a Simulation

Let's Build a Simulation

We have a Java program that builds an internal representation of a road network on the computer, and we have a pending event set mechanism (actually two of them), so it's time to marry the two and create a simulation of a road network.

Of course, we need to add some things to our road network to do this:

• Vehicles: Where do they come from and where do they go?

• Behavior: How do vehicles behave as they traverse a road?

Vehicle Sources and Destinations

One way to add vehicles to a highway network is to add some new classes of intersection, vehicle sources and sinks. In the real world, these might model roads coming into the highway network from the outside world and roads leaving the highway network, or they might model parking lots.

In the simulated world, vehicle sources create new vehicles out of nothing and spit them out into the road network. Similarly, vehile sinks consume any vehicle that enters them, utterly and completely destroying those vehicles.

In our model, we'll keep things simple with the following two new intersection types:

• Vehicle sources: Each source can have a different behavior. For example, one source might inject a single vehicle at the start of simulated time, while another might inject a vehicle every t seconds. Source intersections can be characteriszed by three numbers, when they start injecting vehicles, the number of vehicles the source will inject, and the interval between successive productions. In our textual model, an intersection that starts creating cars at time 100 and produces 10 cars, one car every 3.5 time units might be described as:

  interseciton X source 100 10 3.5
  

• Vehicle sinks: If we were traffic engineers, we'd make the sink intersection accumulate some kind of statistics about the life history of each vehicle as it is destroyed, but since we're just building the simulation engine, we'll ignore that. Sinks could look like this in our textual language:

  interseciton Y sink
  

Adding source intersections to the program

We need to add parsing support for source intersections. Step 1 in this venture is to just parse the details of the source and store the parameter values. This is straightforward code that imitates the kind of code we've already written. Half of this code is copied from other intersection types.

class Source extends Intersection {
    float startTime;
    int carCount;
    float departureInterval;

    // constructor
    public Source( Scanner sc, String name ) {
        super( name );

	// first scan the new fields
        startTime = ScanSupport.nextFloat(
            sc,
            () -> Source.this.toString()
	)
        carCount = ScanSupport.nextInt(
            sc,
            () -> Source.this.toString()
        );
        departureInterval = ScanSupport.nextFloat(
            sc, );
            () -> Source.this.toString()
        );
	// Bug:  Some fields of this are undefined in each error message above

	// deal with end of line
        ScanSupport.lineEnd(
            sc,
            () -> StopLight.this.toString()
        );

        // check sanity of field values
        if (startTime < 0.0f) {
            Errors.warning( "Negative start time: " + Source.this.toString() );
	}
        if (carCount < 1) {
            Errors.warning( "Never produces cars: " + Source.this.toString() );
        }
        if (departureInterval < 0.0f) {
            Errors.warning( "Negative interval: " + Source.this.toString() );
        }
    
        // BUG: schedule the first departure from this source
    }

    // simulation methods
    void departureEvent() {
        // BUG new vehicle departs
    }

    // other methods
    public String toString() {
        return (
            "intersection " + name + " source " + startTime
	    + " " + carCount + " " + departureInterval
        );
    }
}

The details of the simulation of an departure are all missing above, replaced by bug notices. We need to flesh this out.

In contrast, the Sink subclass of Intersection is relatively easy. We won't give the code here to parse vehicle sinks.

Using the Scheduler

Recall the interface to our scheduler in package Simulator:

/** Call schedule to make act happen at time.
 *  Users typically pass the action as a lambda expression:
 *  <PRE>
 *  Simulator.schedule(t,(float time)->method(params,time))
 *  </PRE>
 */
static void schedule( float time, Action act ) {
        Event e = new Event();
        e.time = time;
        e.act = act;
        eventSet.add( e );
}

Our goal here is to flesh out the details of class Source and then start adding detail to the other classes as needed to build on this start.

Scheduling the departures from a source intersection

Suppose we had this code in our model description file file:

interseciton X source 100 10 0.5

This means that, starting at time 100, we will schedule 10 cars to depart from location X, one car every 0.5 time units. Specifically, we will schedule cars to depart at the following times:

There are two ways to do this. First, we could schedule all of these events from the initializer:

public Source( Scanner sc, String name ) throws IllegalName {
    ...

    for (int i = 0; i < carCount; i++) {
        Simulator.schedule(
            startTime + i * departureInterval,
            (float time)->Source.this.departureEvent( time )
        );
    }
}

The disadvantage of scheduling all of the events at the start of time is that it could clutter up the pending event set with large numbers of events. While the best pending event set implementations have execution times that increase as the log of the number of events in the set, the simulation will run at least somewhat slower if the event set is unnecessarily large. Therefore, it makes sense to keep the number of future events small.

One way to do this is to reognize that each source intersection can be thought of logically as a process where each scheduled event causes the next event in the sequence of events at that source. In that case, we write something like the following:

// initializer
public Source( Scanner sc, String name ) {
    ...

    Simulator.schedule(
	startTime,
	(float time)->Source.this.departureEvent( time )
    );
}

This second alternative assumes that each departure event will inject one car into the road network and also schedule the next departure event, if there are any more cars. Here is a start at writing code for this more complex version of an departure event:

// simulation methods
void departureEvent( float t ) {
    // BUG: Must simulate the departure of a new vehicle at time t

    // schedule the next departure, if there is one
    carCount = carCount - 1;
    if (carCount > 0) {
        Simulator.schedule(
            t + departureInterval,
            (float time)->Source.this.departureEvent( time )
        );
    }
}

In the above code, the initializer just scheduled the first departureEvent() and each subsequent departureEvent() is scheduled as a side effect of triggering the previously scheduled event.

Why Source.this.departureEvent?

Why did we write Source.this.departureEvent instead of this.departureEvent? To understand this, it is necessary to recall that λ notation in Java is a shorthand for creating an anonymous instance of an anonymous subclass of an abstract class. In this case, using our simulation framework, we are creating an anonymous subclass of class Simulator.Action, and the body of the λ expression is actually the body of the subclass's trigger() method. So, when we wrote:

Simulator.schedule(
    departureInterval,
    (float time)->Source.this.departureEvent( time )
);

Class MyAction implements Action {
    void trigger( float time ) {
        Source.this.departureEvent( time )
    }
}

MyAction act = new MyAction();
Simulator.schedule( departureInterval, act );

In this long-wided version of the code where nothing is anonymous, had we written just this instead of Source.this, it would have referred to a field of the object act, which is a member of classmyAction. In the lambda expression, that object and its class still exist, so the meaning of this can still be interpreted as a reference to the anonymous object instead of the object we intend.

The Concept of a Process

We use the term process to refer to the chain of events that is triggered by scheduling the first departure event in the initializer and all of the departure events that follow from that initial event at any particular source intersection.

We can similarly describe a stop-light intersection as a process where the light repeatedly changes state, where each state change allows traffic to flow through the intersection from a different incoming road. That process would be an infinite loop.

Similarly, we can describe the sequence of events that follow an individual vehicle through the simulation as a process. That is the view most natural for a driver to take.

The term process used here is extremely similar to the term as used in the field of operating systems, where a process is the sequence of actions taken by one processor as it interprets a particular program. This is also a sequence of events, where each event is the execution of one machine instruction.

The parallel between discrete event simulation and operating systems is actually fairly deep. The pending event set in a simulator is very similar to the process scheduling queue in an operating system. The same data structures apply.