26. Yet more building a simulation
Part of
CS:2820 Object Oriented Software Development Notes, Fall 2015
|
At the end of the last lecture, we added this bug notice to the code of our road network simulation, in the start of the abstract class Intersection.
private LinkedList outgoing = new LinkedList ();
private LinkedList incoming = new LinkedList ();
// stop lights need to know incoming to release waiting cars
// Bug: Incoming and outgoing are never updated!
The solution to this problem is fairly trivial, so it is left as an exercise.
Of more importance, we had just created the basic mechanism of a stop light:
class StopLight extends Intersection {
float interval = 99.99f; // how long the light stays green in each dir
int direction = 0; // the direciton that is currently green
// initializer
public StopLight( Scanner sc, String name ) throws IllegalName {
... // previously discussed code
// start this stoplight cycling through its incoming roads
Simulator.schedule(
0.0f,
(float time)->Source.this.lightChanges( time )
);
}
// simulation methods
/** Process cycling through incoming roads at this stoplight
*/
private void lightChanges( float t ) {
direction = direction + 1;
if (direction >= incoming.size()) direction = 0;
// Bug: incoming.size() is expensive and constant for each
Simulator.schedule(
t + interval,
(float time)->Source.this.lightChanges( time )
);
}
The question is, how do stop lights interact with roads to allow vehicles to enter the intersection from only one direction at a time? And, while vehicles are waiting to enter, where (and how) do they wait.
In a real road network, when entry to an intersection is blocked, vehicles wait at the end of the road leading into that intersection. We can use exactly the same idea here. This means that each road needs a queue of waiting vehicles, or in our case, where vehicles have no distinct identity, a count of waiting vehicles. This is a new attribute of every object in class Road:
class Road {
// default values below for errors involving incompletely defined roads
private float travelTime = 99.99f; // measured in seconds
private Intersection destination = null;// where road goes
private Intersection source = null; // where road comes from
// name of road is source-destination
// simulation fields
int waiting = 0; // count of cars blocked at exit of this road
...
Note that we have divided the fields into two categories. One category does not necessarily apply to the simulation problem. We could use the travel-time, source and destination fields to build many other applications, for example, a travel planning application that searches the road network for the path that gives the shortest travel time.
In contrast, our new field is only applicable to the simulation problem, and we would change this field if we wanted, for example, to model vehicles as objects — something that would make sense if vehicles had travel plans or if we wanted to compute the average time it takes for a trip from source to destination.
When a vehicle reaches the end of a road, the driver looks into the intersection and makes a decision, step on the brakes or keep going. How do we simulate this? C.A.R. Hoare's law of large problems states: "Inside every large problem is a smaller problem struggling to get out." (Hoare invented Quicksort and was the author of one of the first Algol compilers; he taught at the Queens University of Belfast and later Oxford.) So what are the small problems waiting to be found here?
First, there is the problem of looking into the intersection. The intersection knows that it is a stoplight, and it is the intersection that determines whether the car has to wait. So, logically, we should call a method of class Intersection to determine what to do. Let's call this method isBlocked(). What parameters does this need? In our model, intersections are blocked by stoplights, and stoplights block some incoming roads and not others. Therefore, isBlocked() needs to know what road is asking the question. This leads us to the following code for Road.exitEvent():
void exitEvent( float t ) {
// A vehicle arrives at the end of this road at time t
if (destination.isBlocked( this )) {
waiting = waiting + 1;
// Bug: if vehicles are objects, this is an enqueue
} else {
destination.arrivalEvent( t );
}
}
If the destination was blocked (for this road), we add the vehicle to the queue of waiting vehicles corresponding to this road. If, on the other hand, the destination was not blocked, we enter the intersection with an arrivalEvent() and let the intersection shove the vehicle onward into an outgoing road. Here is the code for the arrivalEvent() at a StopLight:
void arrivalEvent( float t ) {
this.pickRoad().entryEvent( t );
}
This version is trivial, just shove the car onward. A more sophisticated simulation would have the car briefly occupy the intersection before permitting the next car to enter. The body of this method was stolen from the corresponding method for Source intersections.
When a stoplight changes, all the waiting vehicles in one of the roads leading into that interseciton will be unblocked. This must happen in the StopLight.lightChanges() method, since that is the place where the program knows about the light change.
private void lightChanges( float t ) {
direction = direction + 1;
if (direction >= incoming.size()) direction = 0;
// new code
for( int i = 1; i < incoming.get( direction ).waiting; i++ ) {
this.pickRoad().entryEvent( t );
}
incoming.get( direction ).waiting = 0;
// old code
Simulator.schedule(
t + interval,
(float time)->Source.this.lightChanges( time )
);
}
If our model included an actual object for each vehicle, the waiting field of each road would be a queue of vehicles, and the new code would dequeue the successive vehicles from this queue and send them onward. As it is, however, waiting is just a count, so our loop merely sends the correct number of vehicles onward and then sets the count to zero.
If we decide that it takes time to traverse an intersection, this code would be more complex. The loop would be a loop of events, where each event in the sequence schedules the next until either the stoplight changes or the incoming queue is empty.
How do we reconcile this with regular intersections? We'll probably need to add an isBlocked() method that always returns true and an arrivalEvent() method to push the vehicle through the intersection. If it takes time for vehicles to pass through, then this gets more complex, with logic to enforce the "priority to the right" rule for intersections and block waiting vehicles while each vehicle passes through.
Are we doing anything inefficient here? Consder this code from our new version of StopLight.lightChanges():
for( int i = 1; i < incoming.get( direction ).waiting; i++ ) {
this.pickRoad().entryEvent( t );
}
incoming.get( direction ).waiting = 0;
Each iteration fo the loop calls incoming.get(direction), because as far as the Java compiler knows, each call to get() could return a different object. We know it doesn't, but the compiler can't tell this. So, what we might want to rewrite the code like this:
Road greenLightRoad = incoming.get( direction );
for( int i = 1; i < greenLightRoad.waiting; i++ ) {
this.pickRoad().entryEvent( t );
}
greenLightRoad.waiting = 0;
This is only a start in the changes we should make if performance is an issue. The fact is, incoming.get(direction) is a constant in the sense that each time you call, for example, incoming.get(2) (or any other index value within the size of the list) you will get the same road because the list of incoming roads is a constant once initializaiton of the data structure is complete. The get(i) method on linked lists is not particularly fast. What we ought to do is use a different class here. Java's ArrayList class is particularly appealing because it supports all of the list operations we are using while making indexing cheap and insertion expensive. Doing expensive operations during initialization is far better than doing expensive operations during a large simulation.
We need to write the isBlocked method for class StopLight.