3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You use (reciprocal) distance cubed twice (forceA and forceB). Just weigh overhead and profit. Let Force Be With You. \$\endgroup\$ – Alex Kudryashev Jun 8 '16 at 23:54
  • 3
    \$\begingroup\$ This is Javascript and everything is possible ;) forceA = bodyB.mass * (dist = dist * dist * dist); forceB = bodyA.mass * dist; \$\endgroup\$ – Alex Kudryashev Jun 9 '16 at 0:13
  • 1
    \$\begingroup\$ My first inclination was to try Fast Inverse Square Root, but it probably won't help. \$\endgroup\$ – 200_success Jun 9 '16 at 2:51
  • 1
    \$\begingroup\$ Just to be sure: When you run this, I trust you've made sure it's only run once per unique pair of objects? I.e. it doesn't run on (earth, moon) and (moon, earth), does it? I assume you've done all that correctly, but just making sure \$\endgroup\$ – Flambino Jun 9 '16 at 9:34
  • 1
    \$\begingroup\$ @Flambino Yeah, I'm 100% sure this runs only one time for each pair. No duplicate calls. \$\endgroup\$ – Tiago Marinho Jun 9 '16 at 11:08
3
\$\begingroup\$

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);
            }

        }
    }
\$\endgroup\$
  • \$\begingroup\$ Reducing callbacks looks like the way to go. Also, I was optimizing this specific function because no one seems to answer my posts when I ask for an entire class review. I was probably going to ask for the PhysicsWorld class review later on. \$\endgroup\$ – Tiago Marinho Jun 17 '16 at 12:16
  • \$\begingroup\$ Good work on every aspect of your review. I'm pretty happy with the performance now. :) \$\endgroup\$ – Tiago Marinho Jun 17 '16 at 12:29
  • \$\begingroup\$ great, love the project! keep going! \$\endgroup\$ – Ross Jun 18 '16 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.