N-Body Gravity Simulation & Barnes-Hut Algorithm

01/ What is the N-Body Problem?

In physics and astronomy, the $N$-body problem is the mathematical challenge of predicting the individual movements of a group of celestial objects that interact with one another gravitationally. Solving this problem is fundamental to understanding star cluster dynamics, galaxy formation, planetary system evolution, and cosmic structure.

For a system containing only two bodies ($N = 2$), the problem is completely solved. Sir Isaac Newton formulated the analytical solution using calculus, proving that two masses will orbit their common center of mass in stable, closed conic sections (ellipses, parabolas, or hyperbolas) as described by Kepler's laws of planetary motion.

However, as soon as a third body is introduced ($N \ge 3$), the equations of motion exhibit chaotic trajectories. In 1887, French mathematician Henri Poincaré proved that no general closed-form algebraic formula exists to solve the three-body problem. Instead, the orbits become highly chaotic and sensitive to initial conditions—making numerical integration necessary.

Without analytical formulas, physicists must use numerical simulations. Under Newtonian gravity, the force exerted on particle $i$ by particle $j$ is calculated as:

$$\vec{F}_{ij} = G \frac{m_i m_j}{|\vec{r}_{ij}|^2} \hat{r}_{ij}$$

Because gravity has an infinite range, every single particle exerts a force on every other particle. Calculating these forces directly requires evaluating all pairs of interactions, leading to a computational complexity of $\mathcal{O}(n^2)$. This quadratic complexity quickly becomes the primary bottleneck in large-scale physics simulations.

Interactive N-Body Sandbox

Live WebAssembly Render (Rust + Macroquad)

Initializing n-particles.wasm...

WASM Hardware Accelerated O(n log n) Barnes-Hut

Figure 1: The n-particles engine running live via WebAssembly. Watch particles orbit, collide, and merge!

02/ The Barnes-Hut Algorithm

To achieve real-time performance at scale, our engine implements the Barnes-Hut algorithm, reducing time complexity to $\mathcal{O}(n \log n)$. This is achieved by organizing the $2D$ simulation space into a QuadTree structure.

Instead of computing individual forces for distant particles, the algorithm groups them. If a cluster of particles is sufficiently far away from a reference particle, the algorithm treats that entire cluster as a single large mass located at its center of mass.

// Pseudo-code logic for Barnes-Hut force calculation

if (node_size / distance) < theta:

// Treat the node as a single point mass

F = G * (m_particle * m_node) / r²

else:

// Recursively calculate for all children

for child in node.children:

calculate_force(particle, child)

03/ Collision Handling

Gravity brings particles together, but what happens when they meet? In standard systems without softening, the force approaches infinity as the distance $r \to 0$. To handle this, we implemented dynamic collisions:

Merging: If particles cross the MERGE_THRESHOLD, they fuse into a single larger body. Momentum is strictly conserved during this inelastic collision.
Elastic Bounce: If they cross the MIN_DISTANCE but not the merge threshold, they bounce off each other, exchanging velocities.

// Conservation of Momentum upon Merging

m_new = m₁ + m₂

v_new = (m₁ × v₁ + m₂ × v₂) / m_new

pos_new = (m₁ × pos₁ + m₂ × pos₂) / m_new