This is my implementation of the Barnes-Hut algorithm for calculating the mutual gravitational forces of N bodies in time complexity O(N log N). The video starts with a quick introduction to the problem and then gives the key insights that allow the algorithm to work. I then show how I implemented it in code and I also point to how you can improve the algorithm beyond what was defined in the original paper.
This is the third video in a playlist on gravity simulations which you can find here:
Code: (I still have to clean up the code but as soon as I’m done, you’ll find the link here.)
Chapters:
0:00 – Intro
0:18 – Problem
0:46 – Solution
2:28 – Quadtree
4:09 – Construction
4:59 – Propagation
6:04 – Acceleration
7:23 – Improvements
8:58 – Collisions
9:15 – Outro