[MUSIC] 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. 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. 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. 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. So this approach is simple but it work only with small delta t, and with size small delta t means that's the, we need a large number of iteration to have something accurate. But, we could use a strategy which is almost as simple but more accurate. 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. 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. 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. In the next module, I will explain how to generalize this method to other kind of discrete events. [MUSIC]
