23. The Event Set and Building a Simulation

// Initialize
PendingEventSet eventSet = new PendingEventSet();
for each event e that known in advance to happen at future time e.time {
    eventSet.add( e );
{

// Simulate
while (!eventSet.isEmpty()) {
    Event e = eventSet.remove(); // e is the new current event at e.time
    simulate e by {
        // update simulation state variables to account for e at e.time
        for each event f that is a consequence of e {
            eventSet.add( f );
        }
        // if event requires, force simulation to terminate
    }
    // simulation terminated because we ran out of events
}

PriorityQueue(int initialCapacity, Comparator comparator)

Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.

PriorityQueue eventSet = new PriorityQueue<>(
    initialCapacity,
    (Event e1, Event e2)-> Double.compare( e1.time, e2.time )
);

This illuatrates a common design pattern: When one generic class is designed to operate on elements of some other class and it needs an operator to fiddle with them, you pass the operator to the constructor using a λ expression, or using a new object of an implementation of the required interface — in Java, λ expressions are merely shorthand for this.

This pattern shows up in Java's priority queue, tree-set and sorting mechanisms, allowing you to sort things into order on just about any basis. It can be used in a variety of other contexts — wherever there is a generic algorithm that can be made to operate on a variety of different data types.

Simulation Frameworks

There are many different ways of using discrete event simulation. We can describe these as simulation frameworks. They change the way we write the code to schedule events, but they do not change the underlying simulation model. Here is an initial (and poorly thought out) framework:

/** Framework for discrete event simulation.
 */
public class Simulator {

    public static abstract class Event {
        public double time;       // the time of this event
        abstract void trigger(); // the action to take
    }

    private static PriorityQueue<Event> eventSet
        = new PriorityQueue<Event> (
            (Event e1, Event e2) -> Double.compare( e1.time, e2.time )
        );

    /** Call schedule(e) to make e happen at its (future) time
     */
    static void schedule( Event e ) {
        eventSet.add( e );
    }

    /** Call run() after scheduling some initial events
     *  to run the simulation.
     */
    static void run() {
        while (!eventSet.isEmpty()) {
            Event e = eventSet.remove();
	    e.trigger();
        }
    }
}

The problem with the above framework is that it requires the user to create large numbers of subclasses of events, where each subclass includes a trigger method that does the required computation. Scheduling an event is actually an example of a delayed computation, and as we've seen, Java provides a tool that allows delayed computation and implicit creation of anonymous subclasses, the lambda expression. The above framework isn't set up to use these!

The following simulation framework uses λ expressions. We will use this framework as we develop our simulation:

/** Framework for discrete event simulation.
 */
public class Simulator {

    public interface Action {
        // actions contain the specific code of each event
        void trigger( double time );
    }

    private static class Event {
        public double time; // the time of this event
        public Action act; // what to do at that time
    }

    private static PriorityQueue<Event> eventSet
        = new PriorityQueue<Event> (
            (Event e1, Event e2)-> Double.compare( e1.time, e2.time )
        );

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

    /** run the simulation.
     *  Call run() after scheduling some initial events to run the simulation.
     */
    static void run() {
        while (!eventSet.isEmpty()) {
            Event e = eventSet.remove();
            e.act.trigger( e.time );
        }
    }
}

When writing a simulation, it is important to begin by settling on a framework, because that determines the sturcture of the simulation code. Changing the framework after you have begun writing code can be messy, but it is not impossible.

Using the Framework

Let's start with something simple (and pretty useless): Scheduling the end of time. Given that endTime is a variable set to the end of time, we could do this by adding the following to the initialization code in the main method or perhaps in buildModel:

Simulation.schedule( endTime, (Double t)-> System.exit( 0 ) );

Note that the lambda expression requires a parameter, the time, but that this parameter is not used in the body of the expression. This parameter is needed so that the Java compiler can match the lambda expression with the interface Simulator.Action.

Of course, we ought to provide some way to specify the end of time. It would make sense to allow a command in the model specification file to give the end of time, but it would also make sense to allow the end to be read as a command line argument, or even from both, ending the simulation with whatever comes first. The easiest way to do that would be to simply schedule the end of time if there is an end-time command line parameter, and also to schedule the end of time if there is an end command in the input file. With two end events in the pending event set, whichever comes first does the job.

Finally, it might be nice to allow users to be able to specify times in familiar units like days, hours, minutes and seconds, instead of just using dimensionless floating point numbers. A system of time units requires that, everywhere a time is read from any source, a time unit may follow. Typically, we would convert all times to some standard unit internally, perhaps days, or perhaps seconds, it hardly matters so long as times are also converted to human readable form in any simulation output.

A Simple cyclic series of events

In our road-network simulatioin, stop lights can have a very simple behavior: the light changes every p seconds, where p is the period of the stop light. In the real world, this models only the simplest of stoplights. Real stop lights may have different times for side roads than they have for arterial roads, and they may be reactive, waiting until they sense sensing waiting traffic on a side road before they offer a green light in that direction. We'll ignore that complexity here.

The first thing we must do to simulate stop lights is augment the StopLight class with an instance variable, the period of that stop light, and read this from the input line. We could use the following format in our road-network description file:

intersection N 1.4 stoplight 30

Assuming that times are given in seconds, this indicates an interesection named N where cars can cross the intersection in 1.4 seconds and where there is a stop light which changes every 30 seconds. It is pretty obvious that period should be an instance variable of each stop-light object, and it can be final, since for trivial stop lights, the period is a constant. In the constructor for stop-lights, we add this code:

period = sc.getNextFloat( 0.1F,
    ()-> super.toString() +": stoplight: expected period"
);
if (period <= 0) {
    Error.warn( this.toString() + ": negative period?" );
} else {
    Simulator.schedule(
        period, // BUG - Should we multiply by a random from 0.0 to 1.0?
        (double t)-> this.lightChange( t );
    )
}

One interesting puzzle in the above code involves the two error messages, one uses super.toString while the other uses this.toString. There is a compelling reason for this. These calls are from inside a constructor for an object. Within a constructor, every call to this.anyMethod needs to be thought about with great care. The reason is, this object is still under construction. Calls to methods after the object is fully constructed are safe, but before construction is complete, the methods called should never reference fields that have yet to be properly initialized.

In the case at hand, the call to super.toString is in the middle of code to initialize a final variable in the object, period. Furthermore, the toString method for stop lights needs to output the period as part of the description of this stop-light.

Within the constructor, it is safe to use super.toString because the very first line of the stop-light constructor is a call to the constructor for the superclass. After that is called, all fields in the superclass are properly initialized, so it should be safe to call super.toString or any other method of the superclass.

The above code is mostly about getting the period, but note that if a valid period is found, the code immediately schedules a lightChange event for this stop light. So, we must add an event to change the light:

private void lightChange( double time ) {
    Simulator.schedule(
        time + period,
        (double t)->> this.lightChange( t );
    )
    // BUG -- no concept of incoming roads getting unblocked on a green light
    // BUG -- no way to release waiting queue of vehicles
    
    System.out.println( this.toString() +": light change at t = "+ time );
    // BUG -- the above is just for debugging, to prove that it works
}

The above code has each light change schedule the next light change at a time that advances, and it includes a print statement for debugging only to show the time at which this light changes.