cmanny
commented
7 years ago This is interesting. At present, it's out of the scope of Dan's videos, but at some point he may do a series on creative algorithmics. So I'll attach some interest here
Open pelegs opened 7 years ago
cmanny
commented
7 years ago This is interesting. At present, it's out of the scope of Dan's videos, but at some point he may do a series on creative algorithmics. So I'll attach some interest here
You enjoy writing code that implement physical ideas, so I think the Barnes-Hut algorithm is a great idea.
In short, if we have a system of N particles, all of them interact with each other, than per iteration we would need to perform N^2 calculations, and the complexity would thus be O(N^2). The Barnes-Hut algorithm pushes this down to O(N*LogN), by constructing a quad-tree (or an oct-tree in 3D), each node of which represents a quadrant (or an octant) of the simulation area of the level above it. You sub-divide the simulation area recursively until you get only one particle per node, calculating the center-of-mass and total mass for every node, and then calculate the forces acting on each particle by reaching down the tree only to a certain point (such that far away objects are calculated as clusters, and only close enough objects are calculated one by one).
This allows you to simulate ten of thousands (if not millions) of particles in real-time! It's also how they make those galaxy simulations.
Read more about it here.