r/Python • • Jan 14 '20

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

1.8k Upvotes

82 comments sorted by

33

u/[deleted] Jan 14 '20

15

u/hurix Jan 15 '20

Could you add rotation to everything? Like they all rotate around a random point around the center of the screen from the beginning. Without an impulse to another direction they are just nicely collapsing in the middle.

I would like to know what changes you need in this system to have moons get formed in stable orbits.

9

u/[deleted] Jan 15 '20

I actually implemented that! You can change m0mass in environment.py to whatever you want and enable DO_LOCK.

2

u/larsga Jan 15 '20

Without an impulse to another direction they are just nicely collapsing in the middle.

This is also partly because the collision detection seems to extend a bit beyond the edges of the actual object. Tweaking this aspect might make it more likely to end up with something like a solar system/galaxy without cheating.

2

u/[deleted] Jan 15 '20

Yeah there's a parameter collision_threshold for this in cnf.py

260

u/psharpep Jan 15 '20

Nice start here! I noticed you mentioned this sim took 3 hours to run - if you're interested in further improving this code, you can probably get 1000x faster performance on the same hardware. Consider looking into the following topics (you should be able to find more info on all of them with a Google search):

  • Vectorization. A specific example is getting rid of your for loop in simulate.py line 66 - this can be easily done with NumPy vectorization instead, which will make this much faster. Alternatively, you can at the very least give this a Numba @jit decorator by adding just a single line of code, which will move this for loop down to low-level code.

  • Better integration schemes. Your RK4 implementation is a great start! Adaptive RK4 schemes will be a lot faster, though, and symplectic schemes will be astronomically more accurate for an orbital dynamics simulation.

  • Fast Multipole Method interactions - this one's absolutely HUGE. Right now, your function to calculate acceleration due to gravity, a(x), is of computational complexity O(n2 ) - the time it takes to run is proportional to the number of particles squared. The fast multipole method ("FMM", often referred to as one of the top 10 most important algorithms of the 20th century), gives you an arbitrarily-precise solution to this problem that has complexity O(n log(n) ). This will literally get you a thousand-fold faster calculation right here alone.

  • Object-oriented methods. You have a ton of redundant calculations: for example, you recalculate the radius of each object at each timestep (simulate.py line 69), when you really only need to recalculate it after each collision - if there's no collision, the radius of the particle doesn't change.

Source: grad student whose research involves a lot of scientific computing

42

u/[deleted] Jan 15 '20

So I tried looking into fmm but didn't understand it really. Do you know some resources to get into it?

24

u/[deleted] Jan 15 '20

Wow thanks I will look into these things, when posting here I was hoping for comments like this one. What do you mean by object oriented methods? Implementing every particle as an object? But then I couldn't use numpys fast matrix multiplications?

16

u/lolfunctionspace Jan 15 '20

Very nice! I wrote something similar to your sim, albeit mine is interactive and you make swarms by clicking ( https://mjsprengel.github.io/gravity/ )

Source code is here: https://github.com/mjsprengel/gravity?files=1

I used the Euler-Cromer integration method. Also known as Semi-implicit euler method. Just thought I'd drop by and share similar work

2

u/Fywq Jan 15 '20

Heh I played a bit with this. It's fairly simple to make some simple pseudo solar systems with elongated comet-like orbits that are stable on the order of minutes at least. Would be cool if field of view could be tied to a single particle so I could keep the "sun" in the center though.

5

u/Astrokiwi Jan 15 '20

For gravity n-body simulations, it's more common to use the Barnes-Hut algorithm - I haven't looked into FMM but it seems closely related. Here you clump distant particles together using an oct-tree or quad-tree, but gravity for the clumped cell is just calculated as a monopole.

The other thing is a particle-particle particle-mesh method, where you bin masses onto a grid and do some Fourier transforms to work out the large-scale forces, and then add a small n2 sum to calculate short-range forces.

1

u/[deleted] Jan 16 '20 edited Jan 16 '20

Interesting method, I'll try to implement it, but how do you make sure to not include the particle you want to calculate the force for in the tree? Wouldn't I have to re-calculate the tree for every particle, making the runtime N2 log N?

Do you choose theta so the particle can't be in an internal node and don't use the external node the particle is in

1

u/Astrokiwi Jan 16 '20

The opening angle criterion means that you go further down the tree for closer nodes. The particle's leaf node is always opened, and that means you can exclude it specifically without having to take into account that its mass is included in higher branches - you've already opened those nodes to get down to the leafs. The opening angle is basically cell-size/distance, and distance==0 for the cell you're in, so you're always bigger than the opening angle criterion.

Btw this is a very standard method, so there's lots of documentation on it, and lots of textbooks will spell it out better than I can in a reddit comment.

1

u/[deleted] Jan 16 '20

One more question: why is it inaccurate to use the center of mass and sum of mass of a group of bodies to calculate the force, compared to calculating the sum of the forces of each individual body?

2

u/Astrokiwi Jan 16 '20

Because gravity doesn't scale linearly with distance.

Gravitational acceleration is Gm/r2. A mass-weighted average of Gm/r2 isn't equal to the GM/<r>2, where <r> is the mass-weighted average of r.

For example, imagine three objects with the same mass, at a distance of r=1,r=2,r=3. What is the gravitational force that have on a test particle at r=0? (For simplicity, let G=m=1)

The full sum is 1/12+1/22+1/32 = 49/36 ≈ 1.36

The average distance would be (1+2+3)/3=2. So if you took the total mass (M=3) and the average distance, that's 3/22=3/4=0.75, which is very different!

On the other hand, imagine three objects at a distance of r=99,r=100,r=101. Then the full sum gives ≈0.00030006, but the radius-weighted centre-of-mass calculation gives 0.0003 exactly. So the approximation is very accurate in that limit.

Basically, force increases very rapidly as you get to small distances, so you're disproportionately dominated by nearby particles. So, while you can chunk things together into their centre-of-mass, this is only accurate for things that are close to each other and far away from you. For nearby objects, you're so sensitive to distance that you really need to do the full sum.

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.

5

u/timeforscience Jan 15 '20

This is awesome, I had no idea it was possible to exceed O(n2) for these calculations. Thanks for posting this.

1

u/jack-of-some Jan 16 '20

Speaking of a 1000x increase in speed ... I'll just ... leave this learning resource here.

https://www.youtube.com/watch?v=x58W9A2lnQc

41

u/BRENNEJM Jan 15 '20

r/gifsthatendtoosoon

I really wanted to see if those last couple particles remained in orbit.

10

u/[deleted] Jan 15 '20

If you like it, you can use the GitHub repository to simulate it yourself!

10

u/quantumwoooo Jan 14 '20

That's so amazing

It looks SO COOOOOLLLL

Imagine this as a screensaver, or, wallpaper

6

u/[deleted] Jan 15 '20

Well this took 3h to simulate so you would need a really beefy computer

8

u/nhillson Jan 15 '20

The functions a(x) and sim_runge_kutter(m, x, v, step) seem like prime candidates for speeding up using Numba.

1

u/[deleted] Jan 15 '20 edited Jan 15 '20

I tried by putting \@numba.njit before the function definition but now the program just stops when callingthe function

Edit: I figured out numba doesnt like it when i use varaibles that arent declared in the function

1

u/billsil Jan 15 '20

It’d honestly be better with numpy. Shorter code too.

1

u/nhillson Jan 15 '20

You only need to add the decorator @numba.njit. Numba is designed to accelerate numpy-based code.

1

u/billsil Jan 15 '20

In theory. In my experience, it slows things down if it's not pure python code and that's slower than the numpy version.

It's like cython in that if you're using it for the exact problem it's good at, it's great. If you're not (e.g., you have unicode in the function), it's much less good.

1

u/o11c Jan 15 '20

You could trim that a little by passing output arguments and finding a ufunc version of fused-multiply-add.

But really you want to do this on the GPU.

1

u/[deleted] Jan 15 '20

Ik but I have a Radeon gpu

7

u/quantumfoam435 Jan 15 '20

So I'm curious. Why a square and not a circle.

8

u/[deleted] Jan 15 '20

Idk how to draw circles in pygame

3

u/KamionBen Jan 15 '20

pygame.draw.circle lol

But IIRC, the circles are sometimes incompletes

6

u/tb33296 Jan 15 '20

Hey, OP, add rotation to the particles and update this please..

Liked it..

1

u/[deleted] Jan 15 '20

What do you mean by rotation?

2

u/billsil Jan 15 '20

He means a tangential velocity about some center point, so V x r.

2

u/Givingbacktoreddit Jan 15 '20

Was that a meteor at the end there? Anybody else see that?

3

u/[deleted] Jan 15 '20

Its a space ship xD I think you mean my mouse cursor

104

u/petdance Jan 14 '20

"First the Earth cooled. And then the dinosaurs came, but they got too big and fat, so they all died and they turned into oil. And then the Arabs came and they bought Mercedes Benzes."

14

u/TallCanadiano Jan 15 '20

And Prince Charles started wearing all of lady Di’s clothes.

9

u/TheRealMerlin Jan 15 '20

I like how a few of them started orbiting.

2

u/Moral_conundrum Jan 15 '20

Yea...I didn’t want it to end. The orbits were just starting to come together :(

2

u/DanelRahmani Jan 15 '20

I saw a :( so heres an :) hope your day is good

1

u/Moral_conundrum Jan 15 '20

Thanks friend!

4

u/[deleted] Jan 15 '20

And apparently a blackhole

1

u/socialistvegan Jan 15 '20

Sorry, I'm a bit of a noob. Tried to follow your instructions, changed the path to a folder within the directory I'm running this in, but I'm getting the following error message:

python3 simulate.py
Traceback (most recent call last):
  File "simulate.py", line 187, in <module>
    cProfile.run("main()", "restats")
  File "/Library/Frameworks/Python.framework/Versions/3.8/lib/python3.8/cProfile.py", line 16, in run
    return _pyprofile._Utils(Profile).run(statement, filename, sort)
  File "/Library/Frameworks/Python.framework/Versions/3.8/lib/python3.8/profile.py", line 53, in run
    prof.run(statement)
  File "/Library/Frameworks/Python.framework/Versions/3.8/lib/python3.8/cProfile.py", line 95, in run
    return self.runctx(cmd, dict, dict)
  File "/Library/Frameworks/Python.framework/Versions/3.8/lib/python3.8/cProfile.py", line 100, in runctx
    exec(cmd, globals, locals)
  File "<string>", line 1, in <module>
  File "simulate.py", line 31, in main
    conn = sqlite3.connect(path.format(now))
sqlite3.OperationalError: unable to open database file

Any ideas what I did wrong?

3

u/[deleted] Jan 15 '20

Have you added a path for the simulations? Like "C:/simulations/{}.db"?

2

u/socialistvegan Jan 15 '20

My bad, looks like despite changing the path in the file, I hadn't actually created the folder. Once I did, it launched without errors!

3

u/[deleted] Jan 15 '20

Great!

1

u/[deleted] Jan 15 '20

Nice job! But why did you go with a square and not a circle (unless I am missing something fundamental)

2

u/[deleted] Jan 15 '20

Nah you're right but I couldn't find out how to make cycles in numpy

1

u/selbstadt Jan 15 '20

I made once like this when I was a kid in Scratch (scratch.mit.edu)

Glad to see that this concept program is still alive :)

1

u/[deleted] Jan 15 '20

With how many particles? I don't even want to imagine what it would take to implement vector operations in scratch

3

u/[deleted] Jan 15 '20

Flat earthers beware

2

u/craltitasimovw Jan 15 '20

This simulation proofs that earth is not only flat, but also a square :O

2

u/jack-of-some Jan 16 '20

Hexagonal Earthers beware!

1

u/[deleted] Jan 15 '20

Wow what a clever way to decrease the number of objects without losing to much information :) Nice

1

u/[deleted] Jan 15 '20

I'm not sure what you mean?

2

u/[deleted] Jan 15 '20

There is an 'aggregation' when 2 objects encounters

1

u/[deleted] Jan 15 '20

Oh you mean the collisions

1

u/[deleted] Jan 15 '20

Yes, very clever

2

u/[deleted] Jan 15 '20

What?

1

u/kabooozie Jan 15 '20

This is a great segue into thinking about just how isotropic the early universe must have been in order for everything to not just collapse into one giant object. Everything almost perfectly uniform

1

u/[deleted] Jan 15 '20

To simulate the big bang I would probably have to implement the other forces too

1

u/homelesspancake Jan 15 '20

How does a gravity simulation work? Like, what’s the math there?

8

u/[deleted] Jan 15 '20

For every particle, you calculate the vector sum of the gravitational Forces to every other particle. That is your acceleration in the next time step. Add this acceleration to the particles current speed and move the particle by this speed.

2

u/Daredhevil Jan 14 '20

Very cool man!

2

u/chris17453 Jan 15 '20

impressive

1

u/pranabus Jan 15 '20

Also needs an expansion of the entire area (universe) and then we can simulate the big bang, as well as explore forever expanding, steady state and contracting scenarios.

1

u/bayney08 Jan 15 '20

You can do this in after effects too! It's super simple but so fascinating

1

u/[deleted] Jan 15 '20

Fantastic work!

1

u/tothemoon2k19 Jan 15 '20

This is great dude. Amazing work!

1

u/ionezation Jan 15 '20

Any easy to understand this Algo?

1

u/cgw3737 Jan 15 '20

Noice. I made one of these a few weeks back, inspired by this sub since they seem to be popular.

1

u/foadsf Jan 15 '20

it would be awsome if you could implement this in OpenCL, for example with pyopencl.

0

u/kaskoosek Jan 15 '20

They should be circles instead of squares though based on rotation.

0

u/Killshot30 Jan 15 '20

Sorry I know this isn't the place to ask but where can I start learning things like this in python?

0

u/[deleted] Jan 15 '20

[deleted]

2

u/[deleted] Jan 15 '20

When 2 particles are close together (the threshold is calculated with the mass) they merge. The velocity is the average of the previous velocities, weighted by mass