Discrete event simulation with continuous state variables?

Whilst there are likely many ways to write simulations, two approaches I understand are: Continuous Simulation and Discrete Event Simulation.

This post will attempt to describe an idea I've had for writing Discrete Event Simulations that model continuous state variables without necessarily resorting to continuous simulation. A form of optimisation, I suppose?

I don't know if this is a useful idea, or a novel one, but I don't know what to formally call it to find out - or who to ask!

Kinds of Simulation

First, a quick introduction to the two kinds of simulation mentioned before the break:

Continuous Simulation

This form of simulation is what games typically employ and has the following steps:

• Have some state initial state
• While the simulation/game isn't done:
• Update the state by looking at the previous state and any inputs

Discrete Event Simulation

These types of simulation are, for example, how VHDL is often simulated:

• Have some initial state
• Have a priority queue of events (sorted by event time)
• Populate the priority queue with any events known at start-up
• Until the simulation is done (typically: while there are any events in the queue):
• Pop the next event from the queue
• Set the current simulation time to the time of the popped event
• Update the simulation state based on the event
  (Possibly pushing new events to the queue!)

So What?

What's neat about discrete simulations is how the current simulation time jumps forward to when the next event is. Long periods of inactivity will be skipped instantly, compared to continuous simulations which have to simulate all the intervening steps - even though they do nothing!

Instantaneous State Changes

The wiki page for Discrete Event Simulation refers to events occurring "at a particular instant of time" and later implies the events can be instantaneous or have a duration (section: Event List). It never elaborates on how events with a duration are modelled, only that they can be approximated with multiple instantaneous events.

The problem with simulations is that sometimes there are things that change continuously, such as the position of a ball thrown through the air. A continuous simulation handles this elegantly: recalculating the state of the ball on each simulation step by modelling its velocity and the forces acting upon it.

What's interesting about the example of a thrown ball, though, is that it can be approximated with a curve (ballistic trajectory) that could be calculated analytically. Not everything is this neat and tidy, but this is the crux of my thought:

Can every state variable be modelled as a curve?

Curves?

Imagine that every state variable is now a line/curve of some sort, with the independent variable being time.

A constant property, such as the height of a ball sitting at rest on a the floor, is a graph with y=0 (assuming the floor is the origin!). A ball at rest on a shelf 10 metres from the floor has a y=10 metres.

A dynamic property, such as a thrown ball's height, is a graph with y=y0+ut+0.5at**2 (using the equations of motion). Notice the inclusion of the variable t for time, making this vary over time.

Now, in the discrete event simulation, consider events arriving that would trigger a series of continuous state variable changes. To continue the theme: a ball is initially at rest until an event indicates it has been thrown:

In a continuous simulation this would just involve the ball now having a non-zero velocity in subsequent simulation steps, causing it to calculate its ballistic trajectory.

In a discrete event simulation using curves, the ball's previously constant (x,y,z) position is now replaced with curves describing the new trajectory.

How Do Curves Help?

My understanding is that previously, attempting to model continuous state like a thrown ball's position would require a discrete event simulation to enter a hybrid mode where it either:

1. Completely throws its hands in the air and hands over control to, or works in conjunction with, a continuous simulation engine.
2. Turn the discrete event simulation into a form of continuous simulation by having the ball continuously send itself events that allow it to update its position every simulation step until it eventually comes to rest.

Both of these (potentially semantically identical) approaches throw away the neat property described earlier: the ability to rapidly skip through simulation faster than real-time by only calculating during events. They force the simulation to become continuous, processing each simulation step until the continuous state variables reach some kind of stable state - at which point discrete event simulation resumes.

I think that modelling state variables as curves might mitigate this risk in some cases. There are two ways this works: interpolation enabling the observable state to be correct "during curves" without necessarily calculating every intermediate simulation step; and interpolating or extrapolating curves to calculate the best future simulation time to inject an event. Each of these is described more below:

Interpolating Observable State

Suppose a simulation contains a thrown ball and a dog eager to catch the ball.

In a continuous simulation system the logic for the simulated dog can easily access the current position of the ball to decide how the dog will react, because the balls state is well defined in each simulation step - calculated from the previous step (or taken from the initial state).

In a discrete event system the ball would ideally only update its state when initially thrown and when it subsequently comes to rest (or is caught, etc.). What would this mean for the simulated dog if it were to sample the balls position in the intervening simulation steps?

Using curves to model state variables, such as the balls position, means that when the ball is thrown it sets its position to curves describing its trajectory. When the simulated dog tries to observe the balls position the curves can be interpolated to establish its position at the current simulation time, without necessarily calculating all intervening steps.

A question one might ask at this stage is: suppose the dog doesn't catch the ball, when does its trajectory end if it isn't continuously calculating whether it has - for example - hit the ground?

This leads nicely onto...

Calculating When To Inject Events

The thrown ball now has state, modelled as curves, which describes its trajectory having been thrown. It would be undesirable if external observers would occasionally sample its position and find that it happily followed the ballistic arc through the simulated ground and was never seen again. To mitigate this it should check for collision.

In a continuous simulation this is again handled on each simulation step where the step function models the path of the ball and ensures it has not intersected any obstacles, handling any collisions as appropriate by changing the balls velocity to bounce or halt, etc.

In a discrete event simulation using curves the balls movement was set on a ballistic trajectory at the moment of being thrown - no further processing is required. Where does collision detection fit into this? I believe that by interpolating (or possibly extrapolating) the curve of the balls position at the point of throwing it would be possible to determine the time at which it would intersect with the floor. More generally, this calculation could be performed whenever the balls position curves are changed. Once this time is known: the system could schedule a physics update at that time to handle that potential collision appropriately.

Conclusion

What this post describes is a method for mitigating the need for continuous simulation of continuous state variables when using discrete event simulations. This approach involves modelling state variables as curves, such that: their state to be sampled meaningfully between "controlling" simulation events using interpolation; and future reactions to continuous state variable changes can be intelligently "scheduled" later in the simulation by interpolating/extrapolating the state variable's curve.