Quadtrees and The Barnes-Hut Algorithm: The Making of a Gravity Simulation

Have you ever been entranced by the beauty of gravity simulations? In this video, I explain the Barnes-Hut algorithm for quickly computing solutions to the n-body problem.

00:00 Intro
00:27 The physics of gravity
03:38 A naive approach
05:16 Quadtrees
10:00 Barnes-Hut
12:46 Time complexity analysis
14:02 Collisions!
16:25 Outtro

[sebasfavaron]

20fps for 1000 particles in Processing is actually not bad! Kudos to you. From here on the only optimization left would be to change languages I guess. This in C++ or Rust should be over 100fps for sure (considering I coded a worse implementation in Rust and it handles 4000 at 60fps)

[oystercatcher]

Thanks. This is fascinating as I'm building exactly this kind of simulation. I'm using Metal and the GPU (no collisions yet). Given the GPU I can do the brute force O(N^2) on 10, 000 bodies at 60 fps and I'm amazed its this good, but I'd like to do 100K or 1M bodies if possible. I tried rendering to an texture, and then generating mip-map with the idea you then sample mass in regular sized grids (just using the centre of the cell) at appropriate resolutions based on distance away. I haven't yet got this working well. Thanks for sharing Barnes-Hut. But doing stuff like this purely on the GPU is very difficult, so I'll probably continue playing around possible doing all close gravity calculations and random sub-sampling those further away. I'll share some videos some time. Good video. Keep it up!

[photonicsauce]

Hi just have a question. Since n-body problems (for n > 2) are known to be chaotic, isnt the barnes hut algorithm unsuitable for long time scales? The error accumulation may be significant right?

[menaced.]

Would be interesting to simulate relativistic gravity instead using like a vector field to represent the combined curvature of all the bodies gravitational forces, could be pretty efficient on a gpu using an image

[MVR_]

this idea is coherent as a lagrange point

[robbie_]

I think perhaps a 2d spatial hash would be a lot faster than a quadtree for this kind of thing, especially as it's 2d. Bonus you can effectively multithread most of hash generation and query/update, believe it or not. This is a big win once you get over a certain number of particles. Anyway nice sim.

[BleachWizz]

getting a result better than that it's beyond improving order of complexity. you'll need to get into parallelizing the code.

How was timings for tree building and traversing?

[exel]

that is nice. but i would just make some constant grid, calculate mass in each cell, and then i will be able to use this cell masses for distant points. at least it would be much easier to implement )

[jasonboyd]

This is very coherent explanation. However, at 10:40 you say that clustering bodies "approximates" the effects of their individual gravitational pulls. Isn't it literally the exact same effect? That is, combining their total mass and calculating pull towards their center of gravity ought to be identical to calculating all the individual gravitational vectors and summing them. No?

[tempdeltavalue]

03:09 it's not exactly true because you can remove similar pairs like "1 - 2" and "2 - 1" so you will get O(n^2 / 2)

[tgey]

Hey william, what program is it you use to run the code?

[dougsellner]

Cool - Q: Does this account gravity traveling at speed of light?

[TarkTheConlanger]

I feel really stupid for still not understanding how this works