(0,0) (1,0) (0,1) (1,1)

QUADTREE STRUCTURE

DEPTH 0

DEPTH 1

DEPTH 2+

EMPTY

BODY LEAF

NO TREE DATA

RUN THE FIELD SCAN FIRST

SWITCH TO FIELD VIEW → PRESS START

The Barnes-Hut algorithm is an N-body simulation method that uses quadtree spatial partitioning to approximate gravitational forces in O(n log n) time. This interactive visualizer lets you run gravitational simulations and inspect the quadtree structure in real time.

θ = 0.5

OPENING ANGLE

SPEED

BODIES8

NODES0

DEPTH0

SPLITS0

How It Works — 4 Steps

1. Build Quadtree

The field is recursively divided into 4 quadrants until each region contains at most 1 body. The colored lines in Field View show these divisions, depth-coded by color.

2. Compute Center of Mass

Each node stores the total mass and weighted-average position of all bodies inside it. This is the COM shown in the quadtree node tooltip.

3. Approximate Forces (θ criterion)

For each body, the tree is traversed. If a node is far enough away — its width s divided by distance d is less than θ (0.5) — the entire node is treated as a single mass at its COM instead of checking every body inside it.

4. Integrate Motion

Forces are converted to acceleration (F/mass), then used to update velocity (VX, VY) and position (X, Y) each time step. Bodies accelerate toward heavier masses.

Why O(n log n)?

Brute force — O(n²)

With 32 bodies, every body checks every other: 32 × 31 = 992 force calculations per step.

Barnes-Hut — O(n log n)

Distant clusters collapse into one calculation. With 32 bodies and θ=0.5, roughly 32 × 5 = ~160 calculations — ~6× fewer. Benefit grows massively with more bodies.

Body Types & Mass

              ◉ BLACK-HOLE  20  ·  ⬤ GIANT  10

              ✺ QUASAR      8  ·  ★ STAR    5

              ◎ PULSAR      5  ·  ✦ NEBULA  3

              ● DWARF       2  ·  ◆ ASTEROID 1

Mass determines gravitational pull strength. A black hole (20) pulls 20× harder than an asteroid (1) at the same distance.

Body Properties (hover in field)

MASS — gravitational mass

How strongly this body attracts others. Force = G × m₁ × m₂ / r².

VX / VY — velocity components

Speed along X (horizontal) and Y (vertical) axes. Positive VX = moving right; positive VY = moving down. Each step: VX += (Fx / mass) × dt.

SPEED = √(VX² + VY²)

Total speed in any direction. Increases as a body falls toward heavy masses; decreases as it climbs away.

Simulation Parameters

θ = 0.5 — opening angle

Lower θ = more accurate (fewer approximations) but slower. Higher θ = faster but less precise. θ=0.5 is the standard research value.

G = 0.001 — gravitational constant

Scales gravity strength across the whole simulation. Increase G to make bodies attract faster and form clusters sooner.

ε = 0.02 — softening length

Prevents infinite force at r=0. Uses r²+ε² in the denominator, capping max acceleration when bodies get very close.

dt = 0.005 — time step

Simulation time per physics sub-step. Speed slider controls how many sub-steps run per animation frame (1–5).

Quadtree Node (hover in diagram)

COM X / COM Y — center of mass

The mass-weighted average position of all bodies inside this node. This is the single point Barnes-Hut uses to approximate forces when s/d < θ.

MASS — total mass in node

Sum of all body masses in this quadrant. Used as m in F = G×m×body.mass/r² during the approximation step.

REGION — quadrant size (s)

Width × Height in normalised [0,1] space. This width is the s in the θ test: s/d < θ means "far enough to approximate".

DEPTH — tree level

Depth 0 = root (entire field). Each level splits into NW, NE, SW, SE. Deeper nodes = smaller regions with fewer bodies.