When to discard events in discrete event simulation

Question

In most examples of DES I've seen an Event triggers a State change and possibly schedules some new Events in the future. However, if I simulate a Billiard game this is not the whole story.

In this case the Events of interest are the shots and the collisions of the balls with each other and with the cushion. The State consists of the position and velocity of each ball.

After a collision or a shot I will first recalculate a new State and from there I will calculate all possible future (first) collisions. The strange thing is that I will have to discard all Events which were scheduled previously as these describe collisions which were possible only before the state change.

So there seem to be two ways of doing DES.

• One, where the future Events are computed from the State and all Events scheduled in the past are discarded with each State change (as in the Billiard example), and
• another one, where each Event causes a state change and possibly schedules new Events, but where old Events are never discarded (as in most examples I've seen).

This is hard to believe.

The Billiard example also has the irritating property, that future events are calculated from the global state of the system. All Balls need to be considered, not just the ones which participated in a collision or a shot.

I wonder if my Billard example is different from classic DES. In any case, I am looking for the correct way to reason about such issues, i.e.

• How do I know which Events are to be discarded?
• How do I know what States to consider when scheduling future events
• It there a possible "safe" or "foolproof" way to compute future events (at the cost of performance)?

An obvious answer is "it all depends on your problem domain". A more precise answer or a pointer to literature would be much appreciated

Answer 1

Your example is not unique or different from other DES models.

There's a third option which you omitted, which is that when certain events occur, specific other events will be cancelled. For example, in an epidemic model you might schedule infection events. Each infection event subsequently schedules 1) the critical time for the patient beyond which death becomes inevitable, with some probability and some delay corresponding to the patient's demographics, mortality rate for that demographic, and rate of progression for the disease; or 2) the patient's recovery. If medical interventions get queued up according to some triage strategy, treatment may or may not occur prior to the critical time. If not, a death gets scheduled, otherwise cancel the critical time event and schedule a recovery event.

These sorts of event scheduling, event cancellation, and parameterizations so that you can identify which entities the scheduling/cancelling applies to can all be described by a notation called "event graphs," created by Lee Schruben. See 'Schruben, Lee 1983. Simulation modeling with event graphs. Communications of the ACM. 26: 957-963' for the original paper, or check out this tutorial from the 1996 Winter Simulation Conference which is freely available online.

You might also want to look at this paper titled "Simple Movement and Detection in Discrete Event Simulation", which appeared in the 2005 Winter Simulation Conference.

Answer 2

The State consists of the position and velocity of each ball.

Once you get that working, you'll need to add the spin and axis of rotation for each ball, since the proper use of spin is what differentiates the pros from the amateurs.

I will have to discard all Events which were scheduled previously

Yup, that's true, so don't bother scheduling them at all. See below.

So there seem to be two ways of doing DES _{(both involving the scheduling of events)}

Actually, there's a third way. Simply search the problem space to determine the time of the first future event, and then jump to that time. There is no need to schedule Events. You only care about the one Event that will occur first.

All Balls need to be considered

Yes, this is true. Start by considering one of the balls and determining the time of it's next collision. That time then puts an upper limit on how far the other balls can move. For example, imagine the first ball will collide after 0.1 seconds. Then the question for the second ball is, "Is it possible for the second ball to hit anything within 0.1 seconds?" If not, then move along to the third ball. If so, then reduce the time limit to the time it takes for the second ball to collide, and then move on to the third ball.

An obvious answer is "it all depends on your problem domain"

That's true. My comments apply only to your example of a billiards simulation. For other problem domains, different rules apply.