Back

Quadtree N-body and the Barnes-Hut approximation

What you are seeing: a 2D gravity-bound disk of N test particles around a heavy central mass. The brown squares are the live quadtree partitioning that adapts to the moving distribution every step. The opening angle $\theta$ controls when a distant cluster of bodies is approximated as a single point at its centre of mass. Toggle the tree off to see direct $O(N^2)$ summation, and watch the per-step evaluation count in the rail.

Figure 1. Disk N-body system with live quadtree overlay. Method: kick-drift-kick leapfrog, Plummer-softened gravity, recursive quadtree with opening-angle criterion $s/d < \theta$.
N bodies500
opening θ0.70
algorithmtree
show tree

WHAT TO TRY

  • Switch the algorithm to direct $O(N^2)$ and watch evals/step jump in the rail.
  • Raise the opening angle $\theta$: the tree approximates more aggressively and evals/step drops.
  • Push N toward 1200 and compare the speedup of Barnes-Hut against direct summation.