25. Building a Simulation

Using the Event 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 4 source 20

This means that intersection X, a source intersection, can pass one car every 4 seconds, and has a median inter-arrival time of 20 seconds. To do this, we construct the source intersection so that each event that generates a new vehicle also schedules the generation of the next one:

// Constructor
private void produce( double time ) {
    Simulator.schedule(
        time + period, // BUG -- need to randomize time of next production
        (double t)-> this.produce( t )
    );
    // BUG -- produce a vehicle v
    // BUG -- what is the travel time of a source intersection?
    // BUG -- pick an outgoing road r
    // BUG -- r.enter( time, v );

    System.out.println( this.toString() +": produces at t ="+ time );
}

Here, each production event injects one car into the road network and also schedules the next event. We have several problems with this. First how do we randomize the production times? Second where is the bottleneck implicit in the travel time of the interesection? Third, how do cars select a road and leave the interesection?

Back to the traffic model

Returning to the traffic simulation problem, we can now begin to make sense of source intersections:

// Constructor
static MyRandom rand = Myrandom.stream();

private void produce( double time ) {
    Simulator.schedule(
        time + rand.nextExponential( period );
        (double t)-> Source.this.produce( t )
    );

    System.out.println( this.toString() +": produces at t ="+ time );
}

Here, each production event injects one car into this intersection, where it may travel right through, if no car is in the intersection, or it may have to wait if the intersection is occupied. The mechanism for handling the vehicle after it arrives at the intersection is handled by the arrive method. This can be the same for all intersections, since whatever intersection a vehicle arrives at, it must wait to pass through the intersection if it is already occupied.

Why Source.this.produce?

Why did we write Source.this.produce instead of this.produce? It turns out that both work, but in early versions of Java, they did not. 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(
    time + rand.nextExponential( period ),
    (double t)-> Source.this.produce( t )
);

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

MyAction act = new MyAction();
Simulator.schedule(
    time + rand.nextExponential( period ),
    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 and has no methods named produce. In the lambda expression, that object and its class still exist, but Java hides this fact and allows us to use this, but that happened late in the development of the language.

The Concept of a Process

We use the term process to refer to the chain of events that is triggered by scheduling the first produce event in the initializer and all of the produce 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.

Creating Vehicles

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

// BUG -- produce a vehicle v
// BUG -- what is the travel time of a source intersection?
// BUG -- pick an outgoing road r
// BUG -- r.enter( time, v );

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.

Note that when a vehicle enters a source intersection, the outcome in terms of travel through the source intersection is largely the same as the outcome when a vehicle enters an uncontrolled intersection. In both, the vehicle must wait. This suggests that class Source should be a subclass of NoStop (the class for uncontrolled intersections).

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

// simulation methods
void produce( float time ) {
    // new vehicle enters this intersection at this time
    // BUG: We could create a vehicle object here.

    this.waiting = this.waiting + 1;
    
    // now see if this vehicle can go through now
    if (this.waiting <= 1) { // this is the only vehicle
        Simulator.schedule(
	    time + this.travelTime, // the vehicle drives through
            (float t)->Source.this.depart( time )
        );
    }

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

In the above code, we assumed that no-stop intersections (including source intersections) count the number of vehicles waiting to get through.

We also assumed a method for vehicle departure. This can be a methof of class noStop:.

void depart( float time ) {
    // vehicle departs this intersection at this time

    // count vehicles on their way through this intersection
    this.waiting = this.waiting - 1;
    
    // now see if any vehicles were waiting and let one through
    if (this.waiting >= 1) { // there is another vehicle
        Simulator.schedule(
	    time + this.travelTime, // the vehicle drives through
            (float t)->this.depart( time )
        );
    }

    // the departing vehicle picks one of the outgoing roads and enters it
    this.pickRoad().enter( time );
}

In the above, we assume that each road object has an enter(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() {
    return outgoing.get( rand.nextInt( outgoing.size() );
}

The above code can go in class Intersection, since vehicle navigation decisions do not depend on the class of intersection.