Sketch · 2026-09-07
Barnes-Hut, an N-body quadtree.
Eight hundred bodies attract each other under gravity. Doing this the naive way costs one force calculation per pair, so N squared in total. Barnes and Hut noticed that a distant clump of bodies pulls on you almost the same as a single body sitting at their centre of mass, and built a quadtree that lets you decide, at each level, whether the cell is far enough to collapse. That decision is the theta parameter below.
Grey squares are quadtree cells. Each body pulls only on cells it can no longer collapse.
How the tree gets walked
Every frame the code first rebuilds a quadtree: each body is inserted from the root, subdividing whichever cell it lands in until it sits alone. Then each internal cell records the total mass of its children and where their centre of mass falls. Now, for each body, the tree gets walked. At a cell of width s at distance d, the ratio s over d is compared with theta. Small ratio, the cell is far, its whole contents count as one lump at the centre of mass. Big ratio, the cell is near enough that its structure matters, so we recurse into the four children.
The counter labelled cell checks per body is what this buys you. On eight hundred bodies the naive sum is 799 pair checks per body. At theta 0.7 the tree walk usually settles around forty to sixty. Slide theta to zero and the tree stops collapsing anything, so the walk visits every leaf and the count climbs back up. Slide it past one and the count drops, the simulation runs faster, and bodies start drifting off trajectories that a stricter walk would have kept tight.
Softening
Point-mass gravity blows up at zero distance. The standard trick is a Plummer softening: replace r with the square root of r squared plus epsilon squared. This caps the force any two bodies can exert on each other and stops close encounters from launching either one to infinity between frames. It also means the disk stays a disk instead of shredding itself the first time two bodies pass through each other.
Sources
- Barnes, J. & Hut, P. (1986). A hierarchical O(N log N) force-calculation algorithm. Nature 324, 446-449. The original tree code.
- Plummer, H. C. (1911). On the problem of distribution in globular star clusters. Monthly Notices of the Royal Astronomical Society 71, 460-470. Where the softened potential comes from.
- Aarseth, S. J. (2003). Gravitational N-Body Simulations. Cambridge University Press. A working astronomer's reference for integrators, softening choices and tree walks.