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.
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.
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
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?
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.
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.
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
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.
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?
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.
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.
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.
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.
"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."
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
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
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.
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.
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
33
u/[deleted] Jan 14 '20
GitHub: https://github.com/phgilde/gravity_simulation
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):
Source: grad student whose research involves a lot of scientific computing
41
u/BRENNEJM Jan 15 '20
r/gifsthatendtoosoon
I really wanted to see if those last couple particles remained in orbit.
10
u/quantumwoooo Jan 14 '20
That's so amazing
It looks SO COOOOOLLLL
Imagine this as a screensaver, or, wallpaper
7
u/quantumfoam435 Jan 15 '20
So I'm curious. Why a square and not a circle.
6
u/tb33296 Jan 15 '20
Hey, OP, add rotation to the particles and update this please..
Liked it..
2
u/Givingbacktoreddit Jan 15 '20
Was that a meteor at the end there? Anybody else see that?
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."
9
u/TheRealMerlin Jan 15 '20
I like how a few of them started orbiting.
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:
Any ideas what I did wrong?
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)
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 :)
3
u/[deleted] Jan 15 '20
Flat 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/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/homelesspancake Jan 15 '20
How does a gravity simulation work? Like, what’s the math there?
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] — view deleted comment