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: th-cam.com/play/PLj66_2EKS5gzXSiIR-WfXmVmrHfK7XW-S.html&si=mV_R8fxhRPbrlHBs
Code: github.com/DeadlockCode/barnes-hut
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