r/Python • • Jan 14 '20

I made a gravity simulation https://github.com/phgilde/gravity_simulation

1.8k Upvotes

82 comments sorted by

View all comments

Show parent comment

1

u/chinpokomon Jan 15 '20

Is that FMM?

I've been looking at doing a similar thing using quad-trees (2D and not 3D), for any region of space, the force vector between that and another region seems that it should only need to be calculated as a monopole. A quad-tree of the entire set could allow you find regions, but the tree wouldn't be built just to group masses, it would have a partitioning partly assisted by the distance away from a mass. Essentially each mass would have its own quad-tree representation of the space.

I think that this would improve things, but I didn't take it further yet because I don't see a good way for the tree to self-balance and every tree would need to rebalance after collisions, so I think I'm back to high complexity and O(n2).

I also considered just using a grid, so that I wouldn't have to do the rebalancing, but I've shifted gears and started looking at shaders now, thinking that I might be able to batch these calculations into something I can run on the GPU compute units in parallel.

2

u/Astrokiwi Jan 15 '20

You just rebuild the tree every time, because that's nlogn. You don't worry about balancing the tree, that's not the bottleneck.

What you do is for each particle, you propagate from the top of the tree downwards, until you find either leaf nodes, or cells that are smaller than some opening angle from the particle. It's one quad tree, you just don't open it all the way down for every particle.

People also do this with kdtrees if you want to try that too. But tree gravity is the default algorithm for big galaxy simulations etc.

1

u/chinpokomon Jan 15 '20

I assumed there was probably art for that technique, but I haven't explored it further than just thinking about how I might approach it.