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
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:
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.
Live demo: Try it out
 |
| 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:
 |
| Quad-tree decomposition of a 2D space full of particles |
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.
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%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# 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
