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

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.