Barnes-Hut: Simulating a Galaxy Without Computing Every Pair

The N-body problem is a wall of pairs

Simulating gravity for n bodies the honest way means computing the force between every pair: n(n-1)/2 force evaluations per time step. Double the number of bodies and the work quadruples. This direct-summation approach is exact, and for a few thousand bodies on a modern GPU it is even practical — but for the tens of thousands to millions of particles in a galaxy simulation or a large gravitational cluster, O(n²) is a wall. Josh Barnes and Piet Hut published the algorithm that gets past it in 1986.

The insight: a distant cluster looks like a point

Newton showed centuries ago that a spherically symmetric mass distribution attracts external bodies exactly as if all its mass were concentrated at its center. Barnes-Hut leans on an approximate version of that same idea: from far enough away, a whole cluster of bodies is gravitationally indistinguishable from one point mass sitting at the cluster's center of mass. So instead of adding up the pull of every individual body in a distant cluster, sum them once in advance and treat the cluster as a single body for anything far away.

To decide what counts as "a cluster" and what counts as "far enough," Barnes-Hut builds a quadtree (an octree in 3D) over all the bodies at the start of every time step. Each node stores the total mass and center of mass of every body beneath it — computed bottom-up in a single pass once the tree is built.

The theta test

Computing the force on one body means walking the tree from the root and, at every node, applying one test: compare the node's physical size s to its distance d from the body being evaluated.

force(body, node):
    s = node.width               // size of the region this node covers
    d = distance(body, node.centerOfMass)
    if s / d < theta OR node is a leaf with one other body:
        return gravity(body, node.totalMass, node.centerOfMass)   // treat as 1 point
    else:
        return sum(force(body, child) for child in node.children) // look closer

If s/d is small — the node is small compared to how far away it is — the whole subtree is collapsed into a single point-mass interaction and the recursion stops there, however many thousands of bodies that node contains. If s/d is large, the node is either too close or too big to trust as one point, and the algorithm descends into its four children to get a more accurate answer. The threshold theta (θ) is the one dial that controls the whole trade-off: θ = 0 forces the algorithm all the way down to individual bodies for every interaction, recovering exact O(n²) summation; θ around 0.5 to 1.0 is the typical working range, trading a small, controllable amount of accuracy for a huge speedup.

Why this is O(n log n)

Building the tree over n bodies costs O(n log n), the same as any balanced spatial tree construction. Computing the force on a single body then touches, on average, O(log n) tree nodes: most of space is far away and gets summarized in one node each, while only the handful of genuinely nearby bodies force the recursion to go deep. Multiply O(log n) per body by n bodies and the total force computation for one time step is O(n log n) — the same asymptotic class as a comparison sort, and dramatically better than the O(n²) of direct summation once n reaches the tens of thousands.

What Barnes-Hut costs you

The speedup is not free. The center-of-mass approximation introduces a real force error whenever θ is greater than zero, and that error is largest for close encounters between clusters of similar size — exactly the situations, like a near-collision between two star clusters, where accuracy often matters most. Production astrophysics codes address this with a multipole expansion (adding the quadrupole moment and beyond, not just total mass and center of mass) to shrink the error at a given θ, and with adaptive θ that shrinks automatically near dense regions. The tree must also be fully rebuilt (or carefully updated) every time step as the bodies move, which is itself the dominant cost in many implementations — a good reason spatial-tree construction gets so much attention in N-body codebases.

Frequently asked questions

Try it live

Everything above runs in your browser — open Barnes-Hut N-body and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.