0:11

Hi, my name is Jean-Luc Falcone.

Â And I will introduce you to this seven-weeks lecture about

Â discrete event simulation.

Â Before defining more formally what they are, I prefer to start with a really

Â simple example that will motivate the use of such approach.

Â 0:31

Here is a really simple physic mechanic setting about a point particle, an ideal

Â point particle in a 2D infinite space without any forces and accelerations.

Â The movement can be explained by these two equations.

Â And the trajectory can be exactly computed at any point in time.

Â 0:54

We just need to know what is the position and

Â speed of the particle at the initial time.

Â For example, if the particle is located at position 4 and 5,

Â x equal 4 and y equal 5 at time zero, with the speed indicated here,

Â we can know after three minutes exactly where the particle would be located.

Â But if we make the setting a little bit more complicated, for example, here,

Â I think a square 2D box around the particle.

Â Here, the square from this example has a side of 16 meters.

Â We can now explain by simple equation again the movement, because the only thing

Â that will happen is that the particle will bounce with perfectly elastic collision.

Â Every time it will collide with one of the four boundaries.

Â However, any of these collision will have

Â a rather drastic effect on the speed of the particle.

Â It will flip the sign of the component

Â corresponding to the wall where the particle will bounce.

Â So now if we ask where the particle will be after three minutes,

Â the answer gets really complicated to get.

Â We can not find anymore a really simple equation that we can solve, and

Â we can have several approaches to this problem.

Â The most common, that I call here naive and brute force, is simply to

Â move the particle by successive small increments of time, delta t here,

Â and after each time step, we can check about collisions.

Â We can check to see if the particle is hitting one of the boundaries.

Â And then if it's the case we update velocities before computing the next

Â position.

Â 3:00

The problem in that approach is that this delta t interval is really important.

Â The system will be really sensitive about it because if this interval is too big,

Â the particle will move inside the hole before we can detect the collision.

Â And thus the movement, the trajectory, will be slightly off.

Â And since the particle will bounce on each wall, at each bounce of the particle,

Â this error will increase and will be amplified.

Â 3:55

We can exactly compute when, at which point in time,

Â the particle will hit one of the boundary, for example, here the north boundary.

Â The condition is that the position in y is equal to the side of the box,

Â called L here.

Â So we can find the time north, which is the time at which the particle,

Â given its initial speed and initial position, will hit the northern boundary.

Â We assume that all boundaries are infinite line here.

Â It's more simple to compute because we don't need to check any condition and

Â we can compute four times tn for the north boundary, ts for

Â the south boundary, te for the east boundary.

Â With our example, the times are there and we can see that's the particle

Â will collide with north boundary after 12 second,

Â roughly, with the east boundary after 6 second, and for the south boundary and

Â the west boundary, the particle will collide there in the past.

Â It means that if, perhaps if the collision did happen, we don't know,

Â but it did happen in the past.

Â So we know that the next thing that the particle will do is to hit the east wall,

Â because it's the closest time to now.

Â So what we could do is to move the particle with the really simple

Â laws that we have seen in the first slide to this east collision point.

Â And after that to update the velocity and compute the further collision.

Â So here is the example in an image.

Â 5:27

We have here a box with the particle at position 0, 0 in the middle,

Â at the position 4,5 in the middle, sorry, at time 0,

Â 0 and this trajectory is a straight line.

Â And you can see in red the four points of collision that we have computed.

Â And indeed the collision with this boundary will be next one.

Â So, we can analytically read easily, make the particle jump to the position,

Â flip the appropriate component of velocity, here x.

Â And then we can start the computation again and

Â compute the next collision time with the following boundaries.

Â Here I've just shown the, so the east boundary, we are there, so

Â we can ignore it.

Â The north boundary would be the next, and

Â without rebound the west boundary will be the last.

Â Of course, the collision with south boundary did happen in this

Â infinite fake trajectory in the past so we can ignore that.

Â And normally we make the particle move to the north boundary,

Â flip the y component of velocity and find again the next point.

Â 6:36

That's the result of applying this computation both methods.

Â So in black, it's the continuous approach,

Â the approach with a small delta t, that will increase.

Â And in red is the exact approach that I show you.

Â Which implies to compute the next relevant collision, the next relevant event.

Â And then modify the speed.

Â And the red circle here indicates the exact place where the rebound did happen.

Â And it's quite interesting to see that, with really similar trajectory,

Â the one with the continuous tag is off.

Â If we compare the results in numerical term,

Â interesting to see that with the setting I've chosen,

Â with the continuous approach, the approach with the small delta t here.

Â I use a delta t of one-hundredth of a second, which is not that small.

Â I need 18,000 iteration to find solution with n error which is below 4%.

Â On the other hand, the discrete approach that I showed you

Â where we will find the next event in time and they'll update appropriately.

Â This date needs only 34 iterations which is more than 500 speed up.

Â And the solution is exact.

Â