Quickly applying gravity force between bodies

Question

I have a function for applying gravity forces between every possible pair of bodies on my game. It is the most used function, and can run more than 100k times per frame so every minor improvement on performance will make a HUGE difference here.

I replaced some divisions by multiplications and the general FPS increased from 5fps to 20fps with ~1000 bodies. This is how performance is affected by this function.

Precision can be decreased if it increases performance considerably. Just make sure you make it clear that a change will decrease precision in your review.

applyGravityBetween(bodyA, bodyB, collisionCallback) {
    var distX = bodyB.x - bodyA.x,
        distY = bodyB.y - bodyA.y,
        distSqr = distX * distX + distY * distY,
        forceA, forceB, dist;

    if (distSqr > (bodyA.radius + bodyB.radius) * (bodyA.radius + bodyB.radius)) {

        // ALERT: Radical actions were taken here to make faster code. Division was avoided at max.

        dist = 1 / Math.sqrt(distSqr); // Dividing one by the distance allows us to multiply instead of dividing later when setting actual velocities, which is more performant.
        forceA = bodyB.mass * dist * dist;
        forceB = bodyA.mass * dist * dist; // Instead of dividing by `distSqr` we can multiply by `dist` twice.

        bodyA.vx += forceA * distX * dist;
        bodyA.vy += forceA * distY * dist;

        bodyB.vx -= forceB * distX * dist;
        bodyB.vy -= forceB * distY * dist;
    } else if (typeof collisionCallback === "function" && bodyA.collidable && bodyB.collidable) collisionCallback(bodyA, bodyB);
}

EDIT:

Here's a benchmark for each separate piece from this function, so you can focus on what you're going to improve:

var declarations took 3.199ms on average to run. Collision check took 3.342ms. Math.sqrt() took 3.122ms.

This question is also related to this one, so if you're interested you can go there too and... Review.

Answer 1

Forward note: To benchmark I simply commented out //self.addCollision(bodyA, bodyB); in step(). Referencing your github code.

To optimize just this method without looking at anything else we can do the following. This gives a physics workload at ~22ms compared with the original ~27ms on my system.

applyGravityBetween(bodyA, bodyB, collisionCallback) {

    var dx = bodyB.x - bodyA.x,
    dy = bodyB.y - bodyA.y,
    r  = (bodyA.radius + bodyB.radius);

    if ( ( ( dx > r || -dx > r ) || ( dy > r || -dy > r ) ) || ( dx * dx + dy * dy > r * r ) ) {

            r = Math.sqrt(dx * dx + dy * dy);

            if( bodyB.mass == bodyA.mass ){

                r = bodyA.mass / (r * r * r);

                bodyA.vx += r * dx;
                bodyB.vx -= r * dx;

                bodyB.vy -= r * dy;
                bodyA.vy += r * dy; 

            }else{

                r = 1 / (r * r * r);

                bodyA.vx += bodyB.mass * r * dx;
                bodyB.vx -= bodyA.mass * r * dx;

                bodyB.vy -= bodyA.mass * r * dy;
                bodyA.vy += bodyB.mass * r * dy;    
            }

    } else if( typeof collisionCallback === "function") collisionCallback(bodyA, bodyB);

}

The above code improves by doing the following.

• simple bounding box collision check before using a more intensive distance check
• remove setting of variables as much as possible, i found in practice this is worth 2 or 3 multiplications in terms of cost. sometimes it's better to repeat the calculations.
• Use a comparison of the masses to speed up similar calculations - this is slightly faster where everything starts off with the same mass and could be useful for high N and similar mass simulations, otherwise I would take it out.

Areas for improvement;

1. This is not coded up but it is common in n-body simulations to group and approximate close,similar & far away masses by grouping them together as one. This can really help as N gets larger because it grows really fast.

2. Reduce Callbacks.

You only asked to optimise the gravity function so this is just an extra.. If you put the following directly into your step() method you can instantly double the speed of the simulation. I found a physics time of 8.8 ms on average - Incorporating all improvements that's almost a third of the original time.

    var i1, i2, bodyA, bodyB, dx, dy, r;

    for (i1 = 0; i1 < this.dynamicBodies.length; ++i1) {
        bodyA = this.dynamicBodies[i1];

        for (i2 = i1 + 1; i2 < this.dynamicBodies.length; ++i2) {
            bodyB = this.dynamicBodies[i2];

            dx = bodyB.x - bodyA.x;
            dy = bodyB.y - bodyA.y;
            r  = (bodyA.radius + bodyB.radius);

            if ( ( ( dx > r || -dx > r ) || ( dy > r || -dy > r ) ) || ( dx * dx + dy * dy > r * r ) ) {

                    r = Math.sqrt(dx * dx + dy * dy);


                    if( bodyB.mass == bodyA.mass ){

                        bodyA.vx += (r = bodyA.mass / (r * r * r)) * dx;
                        bodyB.vx -= r * dx;

                        bodyB.vy -= r * dy;
                        bodyA.vy += r * dy; 

                    }else{

                        bodyA.vx += bodyB.mass * (r = 1 / (r * r * r)) * dx;
                        bodyB.vx -= bodyA.mass * r * dx;

                        bodyB.vy -= bodyA.mass * r * dy;
                        bodyA.vy += bodyB.mass * r * dy;    
                    }

            } else {
                //this.addCollision(bodyA, bodyB);
            }

        }
    }