Barnes-Hut N-body Simulation in HTML/Javascript

A Barnes-Hut Simulation is an N-body simulation of gravitational interactions between point particles using the Barnes-Hut algorithm. A fun way to get a bit of practice with Javascript and HTML5 is to build a real-time N-body simulation using it. Turns out it's surprisingly fast as well.
Live demo: Try it out

Live demo screenshot
Live Demo UI showing speedup of BN Tree vs Brute Force

The simulator runs a simulation of the gravitational interactions between an arbitrary amount of bodies/points. Since we're in 2D the Barnes-Hut tree sub-divides the space into quadrants, providing a large speed-up by approximating particle interactions at long distances:

BN Tree image 1k bodies
Quad-tree decomposition of a 2D space full of particles
With Brute force : O(n^2) calculations (exactly (N-1)*N/2 actually), roughly 125k force calculations for N=500. With Barnes-Hut tree calcualtions, it'll be O(nlogn).

With a low number of bodies N < 50 or so, a slightly streamlined brute force is more efficient than a Barnes-Hut tree, but as N increases, the efficiency increases dramatically: Barnes Hut is an approximation which uses a variable theta to determine the ratio of distance to cell at which to use center of mass instead of step inside the cell. With a Theta = 0.5, we get roughly 50% gain for N < 500, 80% for N < 1000, reaching up to 90% beyond.

With 10k bodies it takes around 0.5~0.8 seconds to compute a step, and 0.1-0.3 seconds to display it on the canvas.

Brute-force calculation O(n^2) for all bodies. Real-time for roughly N < 500 Barnes-Hut calculation implemented and working. Real-time for N > 1k etc.

Efficiency information is shown in real-time to the right of the canvas.

Following examples testing with Theta=1 (not accurate) Example with 1,000 bodies.
# Bodies: 1000
# Force calculations per step: 32457
BN TREE - Depth: 11, # Nodes: 1544, # Leafs: 891
BN Tree O(nlogn) [32457]
Efficiency vs Brute Force O(n^2) [1000000] 96.75%
Efficiency vs Half Brute Force O(n^2) [499500] 93.50%
With 5,000 Bodies
Bodies: 5000
Force calculations per step: 623195
BN Tree Depth: 13
Nodes: 8681
Leafs: 4979
Number of Calculations
BN Tree: 623195
Brute Force: 12497500
Speedup : 95.01%
Time per step
Compute : 752ms
Display : 636ms
With 10,005 Bodies
# Bodies: 10005
# Force calculations per step: 383004
BN TREE - Depth: 13, # Nodes: 17368, # Leafs: 10005
BN Tree O(nlogn) [383004]
Efficiency vs Brute Force O(n^2) [100100025] 99.62%
Efficiency vs Half Brute Force O(n^2) [50045010] 99.23%
Time to compute step : 615ms
Time to display step : 156ms

Source code on Github

Popular posts from this blog

Building a PID hover controller for Kerbal Space Program with kOS and IPython Notebook

Learning TensorFlow #1 - Using Computer Vision to turn a Chessboard image into chess tiles

Learning TensorFlow #2 - Predicting chess pieces from images using a single-layer classifier