0:01

Now, look at an interesting application of priority queues that is actually

Â representative of whole family of a critically important applications in

Â applications of computing. It's called event driven simulation. And the idea is

Â we want to study some property of the natural world by simulating it. And that's

Â something that's very, very common in, in scientific inquiry nowadays. And this is a

Â very natural idea. And actually, the idea goes back to Einstein. So, we want to

Â simulate the motion of N moving particles that might collide with the priority.

Â This, this kind of stimulation is enabled by priority queues. And without something

Â like priority queues, you couldn't do this for a large number of particles because it

Â would require quadratic time and simply can't be afforded for a huge number of

Â particles. So, and let's take a look at how we can possibly make this happen. So

Â we use a simple scientific model called the hard disc model. And then, this is

Â just for simplicity to get this done and just part of a lecture. Clearly, these

Â things can be extended in many ways. So, we're going to have moving particles that

Â either collide with each other and with the walls. And each particle is a disc

Â that's got known position, velocity, mass, and radius. And there's no other forces

Â involved. It gets more complicated if there's more forces, like gravity

Â involved. And this point by itself is very significant. As I mentioned, it goes back

Â to the study of physics with [cough] the trying to understand the pressure and

Â temperature in Einstein's famous experiment on a pollen grain showing that

Â their motion was brownian and random. So whether it's individual atoms and

Â molecules or some bigger kinds of particles. It's a complex dynamic

Â situation that is better understood through computer simulation. And nowadays

Â that means priority queues. [cough] So, as a wa rm-up, here's code to implement

Â bouncing balls without the collisions. And this is an elementary programing exercise

Â that is the, the code at the left has the effects shown at the right. So, we have a

Â data type called ball that represents just one of the particles and has instance

Â variables that has the position and the velocity. So, that's why we make a bunch

Â of them and then we have a, a while loop which is just every 50 milliseconds clear

Â the, the whole drawing and then move the balls a little bit and then draw them in

Â their current position. And then the only to move [cough] operation does is to

Â update the position of the ball by the velocity, which is just another number and

Â then it does the bouncing off the walls. If it happens to hit the left of the wall

Â then you reflect the x-coordinate in the right wall, you reflect the x-coordinate

Â bottom to top, you do the same for the y-coordinate. So, this the is an easy

Â programming exercise given the right display primitives. And it's a good

Â exercise in object-oriented programming showing how just one implementation then

Â we can use that same implementation to simulate a number of instances. So, that's

Â our starting point in terms of the code. So this is the implementation of the ball

Â class. So, it's got position and velocity as I mentioned, and every ball has a, a

Â radius. And then there is a constructor and maybe we have a constructor that takes

Â arguments that would initialize the position and the velocity or maybe

Â initialize them to a random position if there's no arguments. And then, here's the

Â move method. And the move method again, most of the times, just takes the x and y

Â coordinates and adds the current velocity times the speed constant. The dt speed,

Â speed variable that's given as argument dt. And then these tests are for whether

Â it hits the walls in which case, you have to flip the x or y velocity. And then

Â draw, it's just using standard draw. Just draw the ball. So, that's all the code for

Â doing the bouncing ball simulation. Now, what's missing in this is what happens

Â when the balls collide with each other. And to cope with that we need to do both.

Â A little bit of high school Physics and a little bit of basic Computer Science. The

Â Physics problem is exactly what happens when two balls hit and they bounce off

Â each other according to some well-understood physical process, and

Â that's the high school Physics. And the CS problem is how and when to we exactly do

Â these computations for each of the balls. And how can we do it efficiently that is

Â in, in log N time versus quadratic time. Because if we have a computational process

Â that takes quadratic time, then it's not going to scale, we're not going to be able

Â to do large number of particles. Simulations in the real world, usually, we

Â wind up doing huge amounts of data and we cannot have a quadratic algorithm. This is

Â just first indication of that of why if you want to do this simulation, you better

Â know about some data structure like priority queues. If you try to do it

Â without it, you're not going to be successful. Alright, so, let's take a look

Â at what happens. So there's a number of things that you might consider trying. So,

Â one idea is the so-called time driven simulation. And we just say, we're going

Â to update everything every dt seconds. Then we go ahead and then we could check

Â if there's a collision, if the two balls, pieces of the two balls are occupying the

Â same space. And if there is, then we could roll back time just a little bit and I'll

Â try to figure out exactly, the moment of which they collided and then figure out

Â how the position and velocity should change accordingly and then continue the

Â simulation. But this has a huge problem. The first one is that you have t o check

Â all pairs of balls for overlap so that's quadratic, so it's going to be really,

Â really lot of overall texture you're not going to be able to do it for a huge, huge

Â value of N. But the other thing is even if N is small if you do a very small dt, then

Â you're just doing this calculation over and over again and there's just too much

Â computation moving the balls little bit at a time. On the other hand, if you try to

Â improve things by making dt too large you might completely miss a collision as shown

Â in the example at right. So figuring out the value of dt that would really work is

Â a huge problem for the time driven simulation. Instead, what we want to do is

Â called an event driven simulation. And this is a very general concept that's

Â useful in all kinds of context. And we are going to change things when something

Â happens. So, since the only thing that matters is collisions, we are going to

Â figure the particles move in a straight line, between collisions. And what we are

Â going to do is focus only on the times when the collisions are going to occur.

Â And the way we are going to that, is to maintain a priority queue and that

Â priority queue is going to have all the possible collisions that could happen in

Â the future and they're going to be prioritized by time. And when we remove

Â the minimum element from the priority queue, that's the next collision that we

Â have to deal with. And so we have two phases, we have prediction and resolution.

Â So, that's sometime t, we can take two particles. We know their position and

Â velocities shown at the bottom here and we can predict exactly the moment, which

Â they'll collide assuming that something else doesn't happen to them in between and

Â then so they will put that predicted collision time on the priority queue and

Â later on, when that time comes to pass we will be right at moment when they collide

Â and we can figure out what to do. Now, there is a possibly that something else

Â happened to t hem in between and we'll talk about that change, too. So, we have

Â to do collision prediction, which is given position, velocity, and radius when's it

Â going to hit with another particle or, or the wall. And then there's resolution

Â which is to figure out how to change the velocities of the particles according to

Â physical laws. Now this part I'm not going to talk about in that much detail right

Â now because it's high school Physics. And so, I think most students have had high

Â school Physics and will be able to do, do this Math or at least be convinced that

Â the code that does this Math is correct. So, if you know that you have a particle

Â that's at a certain position or x or y and has got a certain velocity, the x in the

Â x-direction and y in the y-direction, then you can from the distance to the pro,

Â vertical wall you can figure out how many seconds this is going to take until it

Â hits it. It's basically that distance divided by the by the velocity. And so

Â that's the prediction. And then, the resolution. When it hits the wall is, is

Â just going to change the velocity. So that's in, you know what the position is.

Â So that's just an example of collision, of collision prediction, when's it going to

Â hit the wall and resolution what do you do when it gets to the wall. When you have

Â two particles there's definitely more math. And again, this is high school

Â Physics. And we're not going to test on it or even go through the details. But it's

Â just a little bit of arithmetic with the velocities and positions to deal with what

Â happens when, when how to predict when a given particle is going to collide with

Â another given particle knowing their velocity and position. So, you have to

Â take both velocities and divide their distance by those and, and so forth. So

Â there's simple formulas to tell us what to do and we can also figure out the formulas

Â for what we do o nce they do collide. And again nobody's claiming that this is easy

Â but this is the Physics part and it's worked out and it comes from Newton's

Â Second Law. And, and, anybody taking high school Physics will, be able to deal with

Â these formulas and the rest of this may have to go to a reference book to get up

Â to speed on them. [cough] but once it's reduced to code we can be, it might have

Â some trouble debugging at first but at least we can be convinced that it works.

Â But now, let's look at the computer science code. So, this is just extending

Â our ball data type that we use for the bouncing balls that didn't collide to take

Â in, into account these extra things. So, ours will have mass, so there will be some

Â big heavy ones that make things more interesting. And there's also a variable

Â called count, which is the number of collisions of particles have been involved

Â in. And that's useful for a couple of purposes. So, we're going to need a bunch

Â of procedures which do the prediction and the collision resolution. I want, what's

Â the, given a particle what's the time till we hit that particle? What's the time till

Â we hit vertical horizontal wall? And the same thing is if we're at the point where

Â we're hitting a particle, what would we do, the, the same way with the vertical

Â and horizontal wall. So, that's the skeleton. We need those procedures that

Â implement those Physics rules for every particle. And, and this is what they look

Â like and again this is high school Physics so we're not going to do it in detail

Â other than to point out it's really not a huge amount of code. Lots of the xs and

Â the ys and the vs but really not a huge amount of code. And the other point is

Â we're going to return infinity if there's no collision at all so that it's going to

Â keep, keep that on the priority queue, that ran on the priority queue forever.

Â Okay, so that's the procedures that we need and then they're similar ones for the

Â horizontal and vertical walls. So now, let's look at the main loop for the event

Â driven simulation. So, the first thing is we're going to for every particle we're

Â going to compute the next time that it might hit every horizontal and vertical

Â wall. Well, actually if it's going away from a wall, it's not going to hit it so

Â that would be infinity. But if it's going towards a wall, then we'll compute the

Â time. And then that's a time in the future and we'll put that event on the priority

Â queue with that time as the key. And then, we'll do the same thing for all pairs of

Â particles. So, we do have a quadratic initialization phase that we perform just

Â once to get the priority queue filled up. Now, all collisions are, might not happen

Â so we might have two particles that are on a collision course that and we're going to

Â predict that point for both of those particles, you know, even right at the

Â beginning. But it might be the case that there's a third particle that knocks one

Â of those out before that thing happens and that event would be invalidated. So, the

Â simulation has to be careful to take that into account. But that's not difficult to

Â do. So, here's what the main loop is. So, we're going to take the next event from

Â the priority queue. That's the next collision that's going to happen from all

Â our calculations. There's one collision that's going to happen next. Then, we test

Â whether that event has been invalidated. And we do that by using that count field

Â in the particle. So, then that tells us what time it's going to be next. So, then

Â we have to go through all the particles and change their positions on a straight

Â line trajectory, where would they'll be after that much time? Then we have to take

Â the two particles that collide and change their velocity. They bounce off one

Â another. Now those two particles' velocities have changed , essentially that

Â invalidates the future collisions involving those. And then we, what we have

Â to do is for those two particles is go through and predict the future collisions

Â with any walls and collisions with any other particles. And put all those new

Â events on to the priority queue. But that's it. You got two particles, change

Â your velocities figure out the future collision of those particles with the wall

Â and update the priority queue and then the main loop is take the next thing off the

Â priority queue and keep going. That's the code that we'll look at next. So we have

Â a, a, a bunch of conventions just to reduce the code. And if we this the, the

Â thing called event which involves it says between two particles, something is going

Â to happen at a certain time and we're going to adopt the conventions that, if,

Â 17:02

neither particle is null then we're talking about two particles. If one of the

Â particles is null then we're talking about a wall, a vertical or horizontal wall. And

Â if both particles are null we're saying we just want to redraw things. That's a bit

Â of a hack, but it cuts down on a lot of code. Our compared to is by time. And then

Â again, we need an, is valid to check about intervening collision. And then here's the

Â skeleton of what's going to happen with the collision system which is the key

Â thing is this prediction method that takes a particle as argument, and adds to the

Â priority queue, all the possible collisions involving this particle. So,

Â it's going to go through every particle and call the time to hit method for that

Â particle. And then, it'll put an event on the priority queue for that time, this

Â particle with that particle. And then, it'll also put an event for the vertical

Â wall and the horizontal wall, again, using this null convention to say that the event

Â second argument null is vertical. First argument null is horizontal. So that's a

Â key method t hat gets used in the simulation for each of the two particles

Â that are going to collide. So, now we can look finally at the main event driven

Â simulation loop. So there's build a priority queue. There's do this prediction

Â for every one of the particles. And then, also we're going to put as the first thing

Â that happened always a, an event that says redraw everything. So that's just a, a way

Â of make suring that the simulation keeps proceeding. It's an easy way to get things

Â drawn. Okay. So, now the main loop is while the priority queue is not empty

Â we're going to pull off an event. We're going to test whether it's valid. And

Â that's just checker if anything happened with those two particles. We're going to

Â pull off the two particles and then we're going to all, we're going to move all

Â particles by the amount of time that has elapsed since the last event. And then,

Â we're going to test which of the four types of events that it is. It's either

Â redraw, bounce, B of A or, or bounce off a vertical wall or, or a horizontal wall.

Â And then we'll go ahead and do the predictions of each of those particles, A

Â and B, against all other particles. That's the pretty much all the code for the

Â simulation. So this is data driven code. So, one thing we can do is just run it for

Â a 100 balls in random position at random velocity. But what's nice about data

Â driven code is now that the code's working and again we, we're not saying that this

Â is a trivial code to write but it's definitely manageable. And it's enabled by

Â priority queues. Without priority queues, it would be quite a bit more complicated

Â to figure out how to do this. And also, it wouldn't be reasonably efficient at all

Â for large data sets. So, that's a, a simple simulation to just generate random

Â positions. People might be interested in this one. Now this isn't exactly precisely

Â wh at would happen in the real world mainly because we didn't put in the

Â simulation what happens when three particles are touching or there's two

Â touching in another one hits them. And also nobody racks up a, a set of billiard

Â balls such that all fifteen are touching in all places. So life can be complicating

Â when you try to simulate the natural world. This is a little bit about

Â