Recently, I entered starputt.com in the Dev Unplugged competition at http://contest.beautyoftheweb.com. The game depends on a quick calculation of all the gravitational forces acting on each object. Basically, a simple implementation for a single object would be:

for every other object in scene :

acceleration = acceleration + Calculate gravitational force between the two objects.

end

This becomes problematic with a large number of objects and I was set on having thousands of objects flying around. I especially wanted the tails of the comets to be affected as well. Each tail could have around 50 – 90 particles at a time. Looking up for some solutions on the net, I found out that the n-body problem actually is not easily solvable. Great.

So I came up with the plan of pre-rendering the gravitational field as a height-map and moving that around the plane. It wouldn’t be 100% accurate, but it would be much faster because:

• The calculation would be done once and cached. This is done before the game starts and remains the same throughout the game.
• The object only has to do one check instead of n checks.

The actual gravitational computation was done using an ASP.net MVC action that renders the image to disk and returns a FileResult.

        public ActionResult Map(int mass)
        {
            if (mass == 0)
            {
                return new EmptyResult();
            }

            // 1000 = 1 Solar mass
            // Scaling:
            float solarMass = mass / 1000.0f;

            // Create the bitmap.
            string filePath = Server.MapPath(String.Format("/Content/img/Generated/massMap_{0}.png", mass));

            var diameter = (int)Math.Ceiling(Math.Sqrt(GravitionalConstantInSolarMasses * solarMass / 0.01) * PixelsInParsec * 2);

            using (var destinationBitmap = new Bitmap(Math.Min(1000, diameter), Math.Min(1000, diameter)))
            {
               var centerPoint = new PointF(destinationBitmap.Width / 2.0f, destinationBitmap.Height / 2.0f);

                for (int y = 0; y < destinationBitmap.Height; y++)
                {
                    for (int x = 0; x < destinationBitmap.Width; x++)
                    {
                          destinationBitmap.SetPixel(x, y, DetermineHeightBySolarMass(x, y, solarMass, centerPoint));
                    }
                }

                destinationBitmap.Save(filePath);
            }

            return new FilePathResult(filePath, "image/png");
        }

Calling on that would return an image like this:

Gravity Height Map for mass 1000

Next was to overlay them together. This was done with context.drawImage() using a context.globalCompositionMethod = “lighter”. This offloaded all the work to the graphics card as these operations are implemented in hardware in the newer browsers.

So a couple of objects near each other would look something like this:

Many objects close together

The rings occur because I’m encoding a height in the colours from blue to red. So height = 255 would be RGB(0,0,255) and height =256 would be RGB(0,1,0) which is the black ring.

The only thing left to do was determine the direction of the slope. This was done by sample the heights at 1 pixel left (x -1, y) and 1 pixel right  (x+1, y) of the current location. I did the same to get the vertical slope using 1 pixel above and below. (I actually ended up using the points 5 pixels away from the location, because Internet Explorer did a bit more anti-aliasing when drawing the image).

You could probably do a more accurate calculation of the gravity using some collision detection against the height map. I basically just used the direction and some small factor to keep the calculations down.

Here’s the javascript:

function setSlope(sprite) {
    if (sprite.x < 0
            || sprite.y < 0
            || sprite.x > width 
            || sprite.y > height) {
        return;
    }

    var x = Math.round(sprite.x);
    var y = Math.round(sprite.y);

     var cx1 = translateTo1DArrayCoords(x - 5, y);
    var cx2 = translateTo1DArrayCoords(x + 5, y);
    var cy1 = translateTo1DArrayCoords(x, y - 5);
    var cy2 = translateTo1DArrayCoords(x, y + 5);

    directionVector.x = getHeightFromColorArray(colorBlock, cx2) - getHeightFromColorArray(colorBlock, cx1)
    directionVector.y = getHeightFromColorArray(colorBlock, cy2) - getHeightFromColorArray(colorBlock, cy1)
    directionVector.z = 0;

    if (distanceSquared(directionVector) == 0) {
        sprite.aX = 0;
        sprite.aY = 0;
        return;
    }

    // Normalize, but without the intensive sqrt. Not accurate, but fast.
     var d = distanceSquared(directionVector);

    normalized.x = directionVector.x / d;
    normalized.y = directionVector.y / d;

    // Some fudge factors to convert from space measurements to screen.
    var a = Math.min(3, 0.8 + distanceSquared(directionVector) / 10.0);

    sprite.aX = normalized.x * a;
    sprite.aY = normalized.y * a;

}