Fogetti

← back to the blog


Event Driven Modelling in Javascript - Part II

Posted on July 9th, 2016 in html5, canvas, priority queue, particle, collision system

In the first part of this blog entry I introduced the idea of even driven modeling and outlined the basic concept of the algorithm to predict the physical interaction of the particles in our collision system.

We also took a look at the physical concepts behind the simulation and we saw the mathematical analysis of those physical concepts.

We also found out how to model those mathematical operations in our code and provided code samples to perform the calculations in our system.

Now that we know the basics and understand the reasoning why this simulation works, it's time to focus on the practical side of the problem and build the system by using some simple abstractions.

We will build everything in client-side javascript, and for this reason we will use special browser specific objects in our code to display the result of the computation. The good news is that HTML5 supports our goals so we can write portable code which will run fine in all the modern browsers out there today. Nevertheless we have to understand which part of the code is native to the browser, and which part of the code is portable to other programming languages, so I will point this out when it's necessary.

So our system will have 5 major components. The main entry point to start our simulation is a simple HTML page, where we will construct an HTML5 canvas to fit the screen and show the particles interacting with each other.

The next element of our model is the controller called the collision system which holds references to all the interacting particles, events of collisions and the priority queue where the events are waiting to be processed.

The next important thing is the priority queue. The basic idea here is that we make all events comparable to each other and we build on this feature in the queue, which will prioritize the events by calling the compareTo() method of the given events pairwise. But it's important to notice that this priority queue does not know anything about events and it will work perfectly fine with any other data type which supports compareTo(). The contract of compareTo() is that it returns less than 0 when the first argument is smaller, more than 0 when the first argument is bigger and returns 0 when the first arguments equals with the second argument.

Then we will also encapsulate the particle specific code (the physics calculation) into a class called Particle. We will extend this class with a method to create a given number of particle objects of itself which all have a random velocity and color. So we can generate a given number of participating particle by a single line of code.

Finally we we will use an Event class to hold the next time when collisions are assumed to happen. This class will also implement the above discussed compareTo() method by comparing the time of different events. We will also apply a neat trick here: it might happen that two particles are predicted to collide in the feature. But it might also happen that those 2 particles interact with other particles in an earlier time which cancels out the latter interaction. So to avoid this situation, we will simply keep a counter in each particle, and when we arrive to the time of the event we compare the count of those particles. If the counts mismatch, than the event must be canceled.

That's it. To start the simulation we just have to initialize each particle's starting position, and put the initial event in the priority queue.

CollisionSystem.prototype.simulate = function() {
    var self = this;

    // initialize PQ with collision events and redraw event
    for (var i = 0; i < this.particles.length; i++) {
        this.predict(this.particles[i]);
    }
    this.pq.insert(new Event(0, null, null));        // redraw event

    self.move();
};

When this is done, our simulation is running and moving the particles when a new event arrives.

CollisionSystem.prototype.move = function() {
    var self = this;

    // the main event-driven simulation loop
    while (!self.pq.isEmpty()) {
        // get impending event, discard if invalidated
        var e = self.pq.delMin();
        if (e.isValid()) {
            var a = e.a;
            var b = e.b;

            // physical collision, so update positions, and then simulation clock
            for (var i = 0; i < self.particles.length; i++) {
                self.particles[i].move(e.time - self.t);
            }
            self.t = e.time;

            // process event
            if      (a != null && b != null) a.bounceOff(b);              // particle-particle collision
            else if (a != null && b == null) a.bounceOffVerticalWall();   // particle-wall collision
            else if (a == null && b != null) b.bounceOffHorizontalWall(); // particle-wall collision
            else if (a == null && b == null) self.redraw();               // redraw event

            // update the priority queue with new collisions involving a or b
            self.predict(a);
            self.predict(b);
        }
    }

};

Notice here the last two instructions: self.predict(a); and self.predict(b);. This is the prediction part where we calculate the time of the next collision then we create new events based on those times and we put those events into the priority queue.

And now all that left is to draw the moved particles on the canvas:

CollisionSystem.prototype.redraw = function() {
    this.c.clearRect(0, 0, this.c.canvas.width, this.c.canvas.height);

    for (var i = 0; i < this.particles.length; i++) {
        this.particles[i].draw(this.c);
    }

    this.c.fillStyle = "rgba(0,0,0,0.08)";
    this.c.fillRect(0, 0, this.c.canvas.width, this.c.canvas.height);
    this.c.drawImage(this.c.canvas, 0, 0);

    if (this.t < this.limit) this.pq.insert(new Event(this.t + 1.0 / this.hz, null, null));
};

If everything goes well we will see the following:

See the Pen Event Driven Collision by Gergely Nagy (@fogetti) on CodePen.

Make sure to checkout the code from my repo: event-driven-part-1

Sweet! Isn't it! But there is a huge issue here. The animation looks jerky. What's going on? How can we fix this?

Stay tuned, because I will talk about this among other things in the coming blog post.