Gravitational Brute Force N-body Algorithm

Question

I've just started dabbling with code, and as a learning exercise I've written a simple algorithm for solving gravitational n-body problems numerically in JavaScript.

I would be very grateful for general feedback as far as the quality of the code goes (first time I'm asking somebody to review my code; I'm very shy about it!), and more specifically advise on how I could optimize it as when I implement the algorithm in THREE.js in the shape of a simulation of the solar system the simulation starts lagging when I include more than around 70 bodies in the simulation. I know n-body algorithms are computationally intensive by nature, especially those of the brute force variety, but I'm pretty sure I've missed out on some useful tricks that would push it a bit further.

Update: to see a working example of the code, check out the jsfiddle I have thrown together https://jsfiddle.net/e9t88dwh

function nBodyProblem(parameters) {

    this.g = parameters.g; //Gravitational constant
    this.law = parameters.law; //Force law, inverse-square in our universe
this.dt = parameters.dt; //Time step to be used
    this.masses = parameters.masses; //Object array with initial conditions for the bodiess to be simulated

}

nBodyProblem.prototype = {

constructor: nBodyProblem,

getDistance: function (m1, m2) {

    return Math.pow((m1.x - m2.x) * (m1.x - m2.x) + (m1.y - m2.y) * (m1.y - m2.y) + (m1.z - m2.z) * (m1.z - m2.z), this.law);

    },

    updatePositionVectors: function () {

        for (var i = 0, len = this.masses.length; i < len; i++) {

            this.masses[i].x += this.masses[i].vx * this.dt;
            this.masses[i].y += this.masses[i].vy * this.dt;
            this.masses[i].z += this.masses[i].vz * this.dt;
        }

        return this;

    },

    updateVelocityVectors: function () {

        var forceVectorX = 0;
        var forceVectorY = 0;
        var forceVectorZ = 0;

        for (var i = 0, ilen = this.masses.length; i < ilen; i++) {

            for (var j = 0, jlen = this.masses.length; j < jlen; j++) {

                //We don't want to calculate self gravity!!!!! 

                if (i !== j) {

                    forceVectorX += (this.g * this.masses[j].m) * (this.masses[j].x - this.masses[i].x) / this.getDistance(this.masses[i], this.masses[j]);
                    forceVectorY += (this.g * this.masses[j].m) * (this.masses[j].y - this.masses[i].y) / this.getDistance(this.masses[i], this.masses[j]);
                    forceVectorZ += (this.g * this.masses[j].m) * (this.masses[j].z - this.masses[i].z) / this.getDistance(this.masses[i], this.masses[j]);

                }

            }

            this.masses[i].vx += forceVectorX * this.dt;
            this.masses[i].vy += forceVectorY * this.dt;
            this.masses[i].vz += forceVectorZ * this.dt;

            forceVectorX = 0;
            forceVectorY = 0;
            forceVectorZ = 0;

        }

        return this;

    }

};

Answer 1

You didn't show the value you are using for parameters.law. Given that you used this in the function getDistance, I strongly suspect you are doing it wrong. You either shouldn't have called the function getDistance or you should have used a different equation. (The correct value for parameters.law given the expressions you are using is 1.5.)

What you should be using to compute the acceleration of a body due to gravitation is along the lines of

delta_x = this.masses[j].x - this.masses[i].x
delta_y = this.masses[j].y - this.masses[i].y
delta_z = this.masses[j].z - this.masses[i].z
distsq = delta_x*delta_x + delta_y*delta_y + delta_z* delta_z
dist_cubed = distsq * Math.sqrt(distsq)     # Note 1: Specialized to 3D space.
                                            # Note 2: No call to pow.
fact = this.masses[j].mu / dist_cubed       # Note 3: Only one division.
                                            # Note 4: Using mu rather than G*M
acceleration_x += delta_x * fact            # Note 5: Using previous calculations
                                            # Note 6: It's acceleration, not force.
acceleration_y += delta_y * fact
acceleration_z += delta_z * fact

I'm going to go over those noted comments above in detail.

1. Specialized to 3D space.
   Just as you can only tie your shoelaces in 3D space, gravity basically doesn't work in anything but 3+1 space (3 spatial dimensions, 1 time dimension).

2. No call to pow.
   Unless you are using Fortran, it's best to avoid pow. Some compilers such as gcc and clang know how to deal with pow(x,2). Javascript? No chance. And even gcc and clang don't know how to deal with x^3/2. Fortran compilers not only know how to efficiently compute x**2, x**3, they also know how to deal with things like x**(-2), x**(-3), and also x**(3/2).

3. Only one division.
   In fact, you can do even better than what I did. There's no reason to compute the relation between particles j and i when you've already computed the relation be particles i and j.

4. Using mu (μ) rather than G*M.
   We are taught in elementary physics that Newton's law of gravitation is F=GM₁M₂/R². This is correct, but it is also a lie to children. The masses of the Sun, the planets, and anything else to which we humans have sent a probe are computed by dividing the observed gravitational parameter for that object by G. There's a problem here: the Newtonian gravitational constant G is by far the one physical constant that physicists cannot measure very accurately. It's best to avoid G, and there is no reason to use it. Use gravitational parameters instead. (Or treat mass as a derived unit, with base units of length³/time². Same difference.)

5. Using previous calculations.
   Your code is doing a lot of repeated calculations, and they are very expensive calculations. When you're doing scientific programming, it's important to pay attention to look out for redundant calculations.

6. It's acceleration, not force.
   You made two key mistakes with regard to units. One was the calculation return Math.pow((m1.x - m2.x) * (m1.x - m2.x) + (m1.y - m2.y) * (m1.y - m2.y) + (m1.z - m2.z) * (m1.z - m2.z), this.law). You mislabeled this getDistance. This is not a distance function. The other is your calculation of force. Force has units of mass*acceleration. You are clearly using the quantity you calculated as acceleration. When you are doing scientific programming, it's extremely important to get your units right. While getting the units right does not guarantee that you have the physics right, getting the units wrong most certainly does guarantee that you have the physics wrong.

One last point: You did not mention how you are using updatePositionVectors and updateVelocityVectors. I'm assuming you used one of the following:

# Naive Euler integration.
updatePositionVectors()
updateVelocityVectors()

or

# Symplectic Euler integration.
updateVelocityVectors()
updatePositionVectors()

While neither one of these is a very good integrator, the latter choice is far better than the first. You should try the two variations and see what happens. Once you see that the second choice is far better, you might want to learn about more advanced integration techniques.

Answer 2

you did something in updateVelocityVectors that I couldn't quite figure out at first

updateVelocityVectors: function () {

    var forceVectorX = 0;
    var forceVectorY = 0;
    var forceVectorZ = 0;

    for (var i = 0, ilen = this.masses.length; i < ilen; i++) {

        for (var j = 0, jlen = this.masses.length; j < jlen; j++) {

            //We don't want to calculate self gravity!!!!! 

            if (i !== j) {

                forceVectorX += (this.g * this.masses[j].m) * (this.masses[j].x - this.masses[i].x) / this.getDistance(this.masses[i], this.masses[j]);
                forceVectorY += (this.g * this.masses[j].m) * (this.masses[j].y - this.masses[i].y) / this.getDistance(this.masses[i], this.masses[j]);
                forceVectorZ += (this.g * this.masses[j].m) * (this.masses[j].z - this.masses[i].z) / this.getDistance(this.masses[i], this.masses[j]);

            }

        }

        this.masses[i].vx += forceVectorX * this.dt;
        this.masses[i].vy += forceVectorY * this.dt;
        this.masses[i].vz += forceVectorZ * this.dt;

        forceVectorX = 0;
        forceVectorY = 0;
        forceVectorZ = 0;

    }

    return this;

}

in both of the for loops you added an extra variable to hold the length of this.masses, but never use it anywhere else in the loop. I think that you shouldn't declare the variable at all and just use this.masses.length in the declaration of both for loops like this

for (var j = 0, j < this.masses.length; j++) {

or an even better idea would be to assign the value to a variable outside of both loops so that you only call the length property of this.masses once, like this.

var massesLength = this.masses.length;
for (var i = 0; i < massesLength; i++) {
    for (var j = 0; j < massesLength; j++) {
    ...

Same thing here as well

updatePositionVectors: function () {

    for (var i = 0, len = this.masses.length; i < len; i++) {

        this.masses[i].x += this.masses[i].vx * this.dt;
        this.masses[i].y += this.masses[i].vy * this.dt;
        this.masses[i].z += this.masses[i].vz * this.dt;
    }

    return this;

},

and I would remove some of the vertical white space as well.

updatePositionVectors: function () {
    var massesLength = this.masses.length;
    for (var i = 0; i < massesLength; i++) {
        this.masses[i].x += this.masses[i].vx * this.dt;
        this.masses[i].y += this.masses[i].vy * this.dt;
        this.masses[i].z += this.masses[i].vz * this.dt;
    }
    return this;
},

@Ismael Miguel is correct, by using the length property inside the for declaration you would access that property every loop, which would make this loop very inefficient, so create the variable outside of the for loop.