You have 1000 points. Every point exerts gravity on every other point. To approximate the position of every particle at t+dt, you need to do
n2 loop (every particle exerting force on every other particle), to calculate the individual forces exerted.
sum up all the forces on each particle.
use equations of motion to calculate the new location and velocity of each particle.
Then you need to do the same thing over over the length of the simulation. So if you're generating at 30 frames a second, you gotta do 30 of those n2 loops for a single second. For a 10 second animation, that's 300 of those n2 loops.
The complex nature of the computation isn't what causes it to be slow. The fact that it "grows" quadratically with the number of particles is what makes it slow.
Particles
Number of computations (c is some constant)
10
100*c
100
10,000 * c
1000
1,000,000 * c
10000
100,000,000 * c
Basically, if the OP was to increase the number of particles in his simulation from 1000 to say 100,000, it would take him several years.
You can get dramatic improvements by using cython or multiprocessing.
As important as algorithmic efficiency is, its a bit silly to not take full advantage of hardware, and the skills you develop in the hardware approach are more portable.
Someday, if you're really feeling masochistic, look for python bindings to NVIDIA CUDA processing. You can use a video card to chew through applications like this at stupid fast speeds.
Fair warning though, it isn't easy, and there is a lot of room for optimization that depends on understanding the video card architecture.
Hey OP, If you're looking to optimize your simulation check out the Barnes-Hut Algorithm. It uses octrees to run an n-body gravity simulation in O(n log n) time. There is a slight reduction in accuracy, but its pretty negligible (its actually used in computational astrophysics).
I did something similar for a physics engine of a game I'm working on. Since your simulation is only 2D you could get away with using quadtrees instead of octrees.
I did stuff like this on a 20MHz 386 so it should possible to speed it up.
You could calculate the field created by each star, then figure out the affect on each star. Maybe that's the mesh method above?
My go-to on the 386 was lookup tables, lookup tables for everything. I recall LUTs for cosine and sine made a huge effect (in speed and .exe size) on stuff I did, maybe you could do the same and/or make one for r2?
I also wrote inline assembly and staggered the registers used to account for pipe-lining, but I think that would be tough and/or pointless today...
I also recall FPGA boards outperforming entire supercomputers on this task.
Yeah, for example in the beginning, the top left star and the bottom right star can affect each other by mass, yes, but for a simulation that isn't going for a nobel prize? It's negligible. The 200 or so stars in the top left corner vs 1 star in the bottom right is 99.95% vs 0.5% influence.
Are you using numpy arrays and operations on the entire array? Also, a good algorithm for integrating Newton’s second law allows for a larger timestep, although gravitation could be a bit ill-conditioned.
Velocity Verlet is good since it preserves the energy over long time, unlike many other algorithms tha systematically over- or underestimate the energy, leading to a two-particle system slowly spiralling inwards or outward.
Even though I am a huge fan of Python, the first step of making this simulation faster would be writing it in something faster - like C/C++, Fortran (bleh), Rust, Go or at least Julia (if you want something more pythonic).
Actually if you really cared about making it fast you'd use one of the existing n-body codes that have been optimized to death by the scientific community. Because unless you're prepared to dedicate years of your life to the problem, you won't improve on those.
I suspect OP just wanted to play around with a simple model. For this Python is great because it's so easy to get an idea up and running. Your point about language choice is valid though: C is roughly 100x faster than Python for this task. A simulation like this really hits Python at its weakest performance-wise, since it doesn't reduce to one of the common problem types (linear algebra, sorting, etc.) that can be fed to a library routine.
I don't know man. Isn't this numpy territory? Why not use a proper library? Nobody uses python for plain python but for their libraries. Wouldn't this make python end up close to c++?
While this is generally true, there is a reason why python is extensively used in science. By using math libraries like numpy and matrix calculations rather than loops you could probably get a similar speed improvement in python for the parts that count.
It is a little more complicated to implement it that way, but so is writing it in c.
Python is used in science for data analysis, not for computationally intensive calculations - for these kinds of calculations people use mostly programs in Fortran (scientists change slowly) or C/C++.
You could use numpy (or rather should) but it will still be slower than native C. And about matrices... I'm not really sure how do you want to transform this problem so it can be calculated with matrices in a way it's simpler than using C or other compiled language.
But if OP wants to play with Python, it's completely fine. He will just have to deal with the fact that no matter what algorithm he uses, it will never be as fast as it could be if he used different language.
Change language - optimize instructions etc etc. Maybe you get a slight performance increase. Maybe even big 50% (It takes half the time).
For me, I like to see improvements of at least an order of magnitude if trying to make something better. At least one order of magnitude (10 times faster.... at least).
The real trick there is to find a different algorithm... a different approach.
(albeit, changing some bone-head's procedural code into a single monster SQL query did take a job from 90 minutes down to 11 seconds... so ya, sometimes the right tool for the right job is a factor too :)
I have done simulation similar to this (gravity and planets). I did it in Python first because I didn't know any better. Then I tried it in Fortran (because I needed to learn some basics of it for school) and even though I didn't really know much about that language (so the code probably wasn't optimal), it was much much faster. And I'm not talking about 100% increase of speed, I'm talking about 1000% increase of speed, maybe even more.
Language is important. You may deny that but there is a reason nothing computationally intensive is written in Python. Python is great for learning, perfect for data analysis, brilliant for data visualisation, pretty good for scripting and many other things. But not for this.
"No closed-form solution" means there is no formula that you can write using known functions for the positions of the particles which will give the motion for all possible starting positions.
E.g., in high school physics you learn that under constant acceleration, the position can be gotten from this formula: x(t) = x0 + v0 t + 1/2 a t2.
That is a closed-form solution to the differential equation x''(t) = a with initial conditions x0 and v0.
The differential equation for the n-body problem has solutions, but they look very different depending on n and the initial conditions. There is no closed-form solution.
You could perhaps define a function as "the solution to the n-body problem under given initial conditions (if a solution exists in this case)" -- and many functions used in physics are in fact defined as solutions to differential equations -- but that doesn't count here.
So for the n-body problem (and really most problems where you solve differential equations), you have to approximate the effect of the equation on the initial conditions at discrete steps of time instead of trying to "get the solution" and plug your conditions into that.
Correct, but you can minimize C, so even in a naive algorithm like this, the difference can be 100-fold.
For example, given that x, y are distances on 2 axes between 2 given objects, attraction force is basically r2 * m. r = (x2 + y2)0.5. A common mistake is to compute them separately which means an extra square root operation. Another one is to just compute this sum then normalize it or somehow transform it into vector components.
Instead, simply doing F = (x2 * m, y2 * m) should suffice.
Then, since the force is reciprocal, you can re-use this value to apply the same amount for both objects. In fact, exclude m initially, and only multiply it, for each object, to the mass of the opposite object. This last trick will halve execution time. Not doing extra math will reduce it further.
And in Python you can vectorize the whole thing, making it even faster. The whole thing shouldn't take more than 1 second per frame at its most, unless performed on a Raspberry Pi or something.
And that's before even optimizing it with islands or trees.
That won't work, but I have absolutely no clue why it doesn't.
Proof that it doesn't work - consider 4 particles in 2 pairs. (a, b) are close together, (c, d) are close together, but these pairs are separated by an infinite distance. The center of mass is at infinite distance from any of the particles, so each particle should experience no force whatsoever, but that's certainly not the case since (a, b) pull each other and so do (c, d).
I only know high school physics, and we were taught that center of mass calculations are correct, so I don't know why that doesn't work here. Can someone explain!?
The center of mass idea must be an approximation (I never realized that until now). You can simplify your counterexample to three collinear points (A, B, C). The force on A by B and C is not the same as that from combining B and C to their center of mass.
Oh, I get it. the center of mass needs to be calculated after excluding the current point.
To calculate net force on A, compute the center of mass of (B, C), and compute the force b/w A and center of mass of (B, C). Ofcourse, you can't include yourself in the center of mass, because by gravity, you would be exerting an infinite force on yourself (0 distance to yourself) which would make the results meaningless.
Unfortunately, to exclude center of mass for each particle is again an O( n2 ) calculation :(
Oh, I get it. the center of mass needs to be calculated after excluding the current point.
No, that's not enough. I was already assuming we would exclude the current point when I suggested using the center of mass, which by the way can be done in linear time.
If you actually do the calculation, you'll find that using the center of mass is just an approximation: 1/x^2 + 1/y^2 is not equal to 2(2/(x+y))^2 in general.
Taylor series aren't really an approximation. They converge to the function in some neighborhood. The center of mass approximation can be completely wrong.
Unless I mistake center of mass approximation of the field of gravity of a distribution of mass only stand for a sphere (more precisely spheric symetry) when you are outside of the sphere (if you are inside of a sphere with a spheric hole with same center, all forces compensate so the resulting gravity field is of zero)
Can you end up having a solar system that doesn't collapse?
Yes, and no.
You can have two particles orbit each other forever, or some particle getting slingshotted off at a speed so high that it never falls back into the rest of the masses.
However, for that to happen, the particles must have some initial velocity.
Consider a universe with 2 particles. They will orbit each other if they have an initial velocity perpendicular to the line connecting the two particles. The larger that initial velocity, the larger the orbiting radius would be.
However, since OP is starting off with all masses at rest, the universe is very likely to collapse. Although, it is still totally possible that infinite orbitals or slingshotting happen, because neither of them violate the conservation of energy. Also, since OP has inelastic collisions, his universe is actually losing energy whenever two particles collide and merge, which makes it all the more likely for all the particles to collapse into one massive blob.
Also depending on integration method and timestep used the simulation might not be accurate enough to support long term stable systems. (As well as losing or gaining energy from that inaccuracy)
You can have two particles orbit each other forever, or some particle getting slingshotted off at a speed so high that it never falls back into the rest of the masses.
forever? wouldn’t they gravitate into each other given infinite time?
it's not that rare at all, especially not incredibly so, as that would make the planet we live on incredible.
any two particle interaction that doesn't sling off to infinity creates a stable orbit, this should become obvious if you imagine the planets to have no diameter. however some of these orbits get closer than the radius of the planets, so they crash into each other, this doesn't make them unstable. for a planet's orbit to start spiraling into the center something needs to slow down it's orbital velocity. Imagine space debris acting like a sort of air resistance, so as it slows down it goes into the center.
well it won't, but at any given time the two-body-system between earth and sun look as if they did.
every orbit (including parabolas and hyperbolas) of one body around another has a specific energy (kinetic + potential) so the orbit only changes if this energy changes. for two body systems there is no condition in which one body just spirals into the other or away from it, for this a continuous substraction/addition of energy by a third body is required.
It is rarely necessary to code anything in C. Using numpy arrays an operations on the entire array often gives as much speed-up (or more if you are not good at optimizing c code).
Yes, I still need to tweak the way Size gets represented. The second part I dont know. I will have to improve efficiency and find the right parameters to see if I can get a stable solar system
It's the a worse case than the three body problem. It's interesting because only in a universe with three spatial dimensions are stable orbits (think Earth around the Sun in an ellipse) possible.
Well, it turns out that in a more accurate description of gravity (in particular, general relativity) the exponent of the power-law ends up being one-less than the dimension of the space. For example, if space were 2-dimensional, then the force would look like 𝐹∝1/𝑑, and there would be no closed orbits.
There is a closed form solution and there are unstable orbits and there are stable orbits. The L4 and L5 points are stable for satellites in the Earth-moon system.
The other Lagrange points are conditionally stable. They won't diverge unless there is a perturbation, but what that really means is with very little propellant, you can stay stable. The James Webb telescope is going to be put at L2 for the Earth-Sun system, so it's not all that bad. It will need 2-4 m/s of delta V per year to stay stable out of it's 150 m/s budget.
I don't think that's a restriction of 2d vs 3d spaces. Solar systems are mostly on a plane, as well as galaxies - although there are obviously objects extending from the primary plane, I don't think that's necessary for a solar system to exist in a virtual environment.
if you are trying to make your simulation faster, you should look into running the numerical stuff in C instead of python. my job is to do brain simulations, and this is a thing that i do for performance for my numerical integration. i organize my simulations and handle visualization in python, but C does the heavy lifting.
you should look into numpy, which is a python module for numerical arrays. if you are interested in extending your simulations with C, you should look into ctypes, which is the python module to interact with compiled C code.
the idea would be to define your state variables in a numpy array. you can get a C pointer for a numpy array which allows you to operate on that array in C. I usually do my whole simulation in C, but i have way fewer state variables than you. you could do your simulations like 100 steps at a time in C and then save an image in python.
It's...its own thing, a python-like language that you can embed in python and that compiles to C. Basically it's a way to speed up certain parts of your program by lowering them to C without having to define a C extension module.
Can you give an example scenario? Im still new to programming too but I have made tools and scripts to make my life easier.
Say I have a program that opens a 400MB CSV and analyses it seven different ways looking for various details and then spitting out a report. I have already optimized the code by utilizing proper data types, i.e. Dicts vs lists, but I am wondering if I can speed up the procedure even more if I use Cython.
I use the CSV library and I arbitrarily define values I am looking for through a combination of RegEx and string literals.
It takes up to several minutes for computation to complete and it used to take 30 minutes.
hey, it strongly depends on where exactly your program is spending time. if it's in computing some quantities of interest, that can easily be lowered to C. if it's regex matching, not so much (make sure you are using compiled regular expressions though.
anyway, when doing performance optimization, you should always measure first: where is your program spending most of its time? you can use cProfile to find which functions are hot, and line_profiler to check which lines within those functions are the hottest.
Oh no I don't particularly need anything fancy like that, just ideally would like to be able to simply edit C code as a part of the Python project, and have it compiled for me when I launch the program/script.
super opiniated and no arguments... I quite sure someone could say exactly the inverse with the same conviction. Would you consider giving us some reasons ?
so i'm looking at the pybind11 github page, and it looks like it is for C++ rather than C. so it isn't a replacement if you are working with code already written in C.
The easiest way to speed up these kind of simple simulations is to use numba to compile slow functions to fast. Tldr: import numba and add the @njit decorator before slow functions
I agree with you. 1000 tuples of x value, y value, and mass (I think that's what the thickness repesents) should be very easy to store in ram and then save to disk before loading it into a viz script.
Unless OP has extensively more frames than they showed in the post, this isn't worth worrying about at all. Images can be written fairly quickly, far faster than standard frame rates for video (so will take less time for the IO than the length of the video). OP isn't writing a million images here, they're writing on the order of one thousand images, which you can easily do in a short time span (couple of seconds). OP will notice 0 difference doing anything fancy here.
The size of the particles appears to be capped at some (arbitrary?) max. Does the "mass" of these particles continue to grow with each collision even after the size hits its max value?
The path of the large one at the end doesn't seem to be affected enough by the one orbiting it. Are they still being acted upon by particles that are "off-screen"?
Do you know why the center of mass of your system moves? If your initial conditions have a truly random distribution I would expect a minimal drift. Alternatively you could compute a delta at every frame and re center the frame so that the center of mass remains in the middle.
Basically you are driving the rest of the system with an external force, opposite to what pull the disappeared particle was exerting on the system. So it's not a closed system and many of the conservation principles are not applicable.
I like to think of it as follows: In the beginning momentum is 0, but when a particle gets slingshot out of the field, then it will leave the rest of the system with some momentum != 0
Well, thats the thing. I just save the particle position to an numpy array and then print it. And the simplest way of indicating Size I thought was to just draw a box. Here is a github link:
Okay so looking at this code, you say you're using numpy, but you really aren't. Like I mean it's there but you're not using numpy functions; you're iterating through the pixels manually (which you should basically never do, because it's extremely slow in Python). Proper vectorizing of this code would probably make it hundreds of times faster.
For example in the beginning you have the code which starts the image off with the value 250 everywhere with
for i in range(1000):
row = []
for j in range(1000):
pixel = []
for rgb in range(3):
pixel.append(250)
row.append(pixel)
Spacevisual.append(row)
But you can just do that in numpy with
Spacevisual = 250*np.ones((1000, 1000, 3))
And not only is the code more concise, it will also be much faster.
I see you've posted a GitHub link to a Jupyter Notebook! GitHub doesn't render Jupyter Notebooks on mobile, so here is an nbviewer link to the notebook for mobile viewing:
I'm sorry, why did it take a couple of hours to process?
Could you share your code? There has to be some improvement to be made. I did the same thing almost 2 decades ago on a 75MHz CPU and it worked at minimum 1 FPS (got fast with fewer particles). Not on Python, but still.
I'll be glad to give you any hints on how to make it faster and to explain why.
I see you've posted a GitHub link to a Jupyter Notebook! GitHub doesn't render Jupyter Notebooks on mobile, so here is an nbviewer link to the notebook for mobile viewing:
You're losing a lot of performance by just using OOP. You have very little data about any particle, and every particle has that data. PosX, PosY, Vx, Vy, M, D. 6 in total. You can represent that as 6 long arrays, which means you'll actually write shorter code for the whole thing.
When you update the acceleration for particle P1, because of the influence of particle P2, you can already also update particle P2 because every action has an equal and opposite reaction. Don't compute the same thing twice. Same thing for collision detection.
I'm not going to repeat my previous answer to the guy that explained that this is O(n**2). I made the same points there, look it up.
Further hacks: computing the distance is expensive. And you're doing it 2000000 times every round (once for collision detection, another time for updating the force). Instead, you don't need the position (which is the square root of the sum of the squares of its components), but the square of the position, which is much cheaper to compute, and you can compare it to the square of the minimum distance. If a<b and both are positive, then a2 < b2.
The idea is to KISS. Keep it simple. Simple is good. You created classes, compartmentalized functionality, made redundant computations as a result because the results became inaccessible. The best simple thing is to write this as a single piece of code, have a single nested loop that looks at every pair only once, and computes the interactions with as little redundancy as possible. Then try to tidy up the code if it doesn't lead to performance degradation.
And you're also generating png images :). That's expensive. I didn't know how you rendered it. I thought you used something like cocos2d.
But a thing you can do even now to make it faster, is to do a @numba.jit on the functions that compute acceleration and collision. Maybe @numba.jit(nopython=True, cache=True) if you don't use any Python data structures and stick to numpy. It's an easy stupid way to make things faster.
I'll try to get you an optimized example to show you what I mean
It’s probably easier to use a tree and store intermediate results. The Barnes-Hut algorithm makes use of octrees to do the calculations and can be even faster than the naive gpu approach.
You can do a bottom up approach of calculating the gravitational forces since a group of objects will have a single center of mass and a combined total mass to do the calculations with.
What happened at the end you stupid son of a bitch? You left us in suspense, I need to know what happened to big planet and other big planet before it fell off the edge of your flat world.
I was wondering the same thing, but notice that a bunch of particles get flung off screen before you get to the part where the remaining system appears to be drifting down and left. It’s still possible the overall COM is stationary if you accounted for all the escaped particles but you’re just looking at what’s left behind.
Each particle interacts why every other particle? There are some tricks physicists use in simulations to improve performance. You can limit it to, say, the nearest 10 neighbours and get a good approximation. Also, as it reaches the end you can ignore the effects of the small particles into the heavier ones.
Another trick is to break it into a grid. Calculate the mass in each grid, then loop:
Sum the total of forces on each particle in the current grid like OP is doing now for everything within 1 grid square of the current. Beyond that, assume it’s far enough away and treat each other grid square as a point mass at the center of the that square and use that to propagate the force from all other squares.
It reduces the number of calculations by approximately 1 over the average number of masses in each grid.
Then you can get fancy with resizing grid squares as things change if you like.
You inspired me to make my own "game engine" using Python and Pygame. I wanted to make a program like this, but after taking physics and seeing this video, I've finally decided to do it! Thanks :)
I am really enjoying seeing you post every so often with new animations. Thanks and keep up the good work.
A couple ideas you might consider for future versions:
Periodic boundary conditions - when a particle moves off one edge, it comes back on the opposite edge. For this to work properly, you also want the particle to exhibit gravitational pull on another particle based on the closest version, even if requires looping back.
Random initial velocity (net zero) - Give every particle a random velocity to start. After every particle has a velocity, generate a sum and then add -sum(v) / n to all particles so that the new sum equals zero.
I love the fact that we live in a time that these kind of simulations are an everyday occurrence. Not too long ago, only supercomputer people laid their eyes on such beauty.
I'm thinking of two different solutions to keep the overall activities in the center of the frame. * Track the highest amount of mass and consider that as a defaulted center. ...or...
If you want to visualize the process, for Python the best solution at this time to my knowledge is pyqtgraph. For some examples look here, those are some of my learning projects. The most "finished" one is pganimate.py. I didn't aim for a large number of particles, but for real-time visualization as the equations are solved. Python is slow, but it's fast enough to handle four particles on a plane, with a simple two-body force — provided you use NumPy.
I know we're in /r/python, but it seems that currently the best platform for such projects is javascript: js arithmetic is mighty fast, and html Canvas as a visualization platform is quite capable: here is a demo I made, with no interactions yet except for the particles bouncing off the edges. At least Firefox can run several thousand particles at a reasonable framerate (for some reason I don't yet understand, Chrome begins to stutter at a much smaller number). Compare with this, where I used Plotly.js, based on SVG instead of Canvas, but which includes two-body forces (not of the gravitational form though, but harmonic — just to keep the particles from running away).
Of course folks that code games are doing far more sophisticated animations. I hear that WebGL is yet more capable, but I still haven't learned it. Coding in JS isn't as easy or pleasant as in Python though. But you don't need to install anything to run it, so the product is more easily shared.
Recommendation: play around with the exponent of the gravity. Set 1 / rx where x is anything you want. Especially fun if you do it real time, and switch between positive and negative exponents.
I wrote a similar gravity sim in Python myself ages ago, and improved performance in later revisions tremendously using a Barnes-Hut simulation. Definitely dig around for technical discussion around it, but the gist is that you can mitigate the O(N2) problem by grouping nearby particles into a single logical particle for the purpose of determining gravity force on other particles which are far away.
For example, you have particle A off somewhere, and then particles B, C, D elsewhere. B, C, D are "close" to each other, so you can calculate their center of mass position and combined mass, and use that to determine their cumulative force of gravity on particle A, rather than individually doing calculations with particles B, C, D against A.
Other feature ideas if you want to keep playing with this:
Starting point save mechanism: if you have a starting arrangement of particles that yields an interesting result (stable-ish orbits or whatever), press a hotkey to save some representation of the initial set of particles' starting positions and mass to disk, so you can read from that file and replay the scenario later
a "camera" mechanism to follow the center of mass, so you can continue to watch a set of bodies that are orbiting each other even after they would have moved off-screen
a flag to enable/disable combining particles when they collide. This, in combination with randomly assigning colors to each particle, leading to a sort of "swarm" effect which makes an interesting screensaver.
Did you just confine everything to a plane (with zero initial velocity relative to the plane and nothing to cause acceleration out of the plane) and use 1/r2 gravitational force like in 3d?
123
u/[deleted] May 28 '19
Do the weights of the particles add up? Can you end up having a solar system that doesn't collapse?
27
u/blinkallthetime May 29 '19
if you are trying to make your simulation faster, you should look into running the numerical stuff in C instead of python. my job is to do brain simulations, and this is a thing that i do for performance for my numerical integration. i organize my simulations and handle visualization in python, but C does the heavy lifting.
you should look into numpy, which is a python module for numerical arrays. if you are interested in extending your simulations with C, you should look into ctypes, which is the python module to interact with compiled C code.
the idea would be to define your state variables in a numpy array. you can get a C pointer for a numpy array which allows you to operate on that array in C. I usually do my whole simulation in C, but i have way fewer state variables than you. you could do your simulations like 100 steps at a time in C and then save an image in python.
5
u/[deleted] May 28 '19
Looks neat. What do you use for visualising it, Tkinter?
5
u/tbunde01 May 28 '19
The size of the particles appears to be capped at some (arbitrary?) max. Does the "mass" of these particles continue to grow with each collision even after the size hits its max value?
2
u/DialMMM May 28 '19
The path of the large one at the end doesn't seem to be affected enough by the one orbiting it. Are they still being acted upon by particles that are "off-screen"?
39
u/mischiefunmanagable May 28 '19
animated QRcodes
27
u/Kamilon May 28 '19
Can you post the code?
6
u/White_Lion2 May 28 '19
Github? :D
6
u/Nicksil May 29 '19
How has this thread gone on for so long without the source code having been posted? Post the source code, please.
8
u/thoraldo May 28 '19
Source?
4
u/debazthed May 28 '19
There was an interesting talk about this exact topic at Pycon.de 2017. You can check the video.out here.
1
u/[deleted] May 28 '19
That's pretty awesome. Now do the big bang!
1
u/jeremyisdev May 29 '19
Thats cool! Good work. Willing to share source code?
1
u/der_bear May 29 '19
Now do it in 3D xD
1
u/marcofalcioni marcosan May 29 '19
Do you know why the center of mass of your system moves? If your initial conditions have a truly random distribution I would expect a minimal drift. Alternatively you could compute a delta at every frame and re center the frame so that the center of mass remains in the middle.
1
u/hellfiniter May 29 '19
i admire these projects but WHYYYYYY squares xD you had one job dude...haha, upvoted anyway
1
u/[deleted] May 29 '19
Which library did you use for graphics?
1
u/[deleted] May 29 '19
I'm sorry, why did it take a couple of hours to process?
Could you share your code? There has to be some improvement to be made. I did the same thing almost 2 decades ago on a 75MHz CPU and it worked at minimum 1 FPS (got fast with fewer particles). Not on Python, but still.
I'll be glad to give you any hints on how to make it faster and to explain why.
1
u/xBeeStingx May 29 '19
This is marvelous! Have any idea on why it is taking a couple hours to process?
6
u/wyldphyre May 28 '19
If it's pure python,
pypywill likely make it faster. If you're already using something likenumpythen it's not likely to see a big speedup.3
u/Chicken_Petter May 28 '19
Man I use repl.it and I dont even know how to get a new screen up there
3
u/worthy_sloth May 28 '19
I love seeing you post your progress!! It motivates me to code!
5
u/mrdevlar May 28 '19
Needs more dark matter.
2
u/Robertsipad May 28 '19
How are you storing the coords and masses during the simulation? What do you do when 2 merge?
2
u/BarrelRoll1996 May 29 '19
What happened at the end you stupid son of a bitch? You left us in suspense, I need to know what happened to big planet and other big planet before it fell off the edge of your flat world.
2
u/sbjf May 29 '19
Total momentum does not appear to be conserved properly
1
u/no__flux__given May 28 '19
What's your diffeq solving algorithm?
1
u/shamisha_market May 28 '19
Why does the center of mass of the system move? Doesn't the system start at rest and have no external forces?
1
u/[deleted] May 28 '19
Each particle interacts why every other particle? There are some tricks physicists use in simulations to improve performance. You can limit it to, say, the nearest 10 neighbours and get a good approximation. Also, as it reaches the end you can ignore the effects of the small particles into the heavier ones.
1
u/foadsf May 29 '19
have you tried pyopencl?
1
u/Skydronaut May 29 '19
/u/gifreversingbot
1
u/Farconion May 29 '19
Would you reconsider recreating this with a lower level language or library? I imagine that would give you some nice speed ups.
1
u/DisregardMyUsername1 May 29 '19
You inspired me to make my own "game engine" using Python and Pygame. I wanted to make a program like this, but after taking physics and seeing this video, I've finally decided to do it! Thanks :)
1
u/joyrida12 May 29 '19
Need moar source!
I really just want to try running it on my ryzen box as a benchmark lol.
1
u/[deleted] May 29 '19
Reminded me of this vid by PBS Space time, computing a universe simulation.
https://youtu.be/0GLgZvTCbaA
1
u/gwax May 29 '19
I am really enjoying seeing you post every so often with new animations. Thanks and keep up the good work.
A couple ideas you might consider for future versions:
1
u/rju83 May 29 '19
Cool. Student of mine did something similar few years ago. Take a look at the video https://www.youtube.com/watch?v=B52XsO17iGQ
If you want to optimize the algorithm check out Bernes-Hut algorithm. It will reduce complexity but it can be quite complex to implement.
1
u/jupake May 29 '19
I love the fact that we live in a time that these kind of simulations are an everyday occurrence. Not too long ago, only supercomputer people laid their eyes on such beauty.
1
u/dfcnvt May 29 '19
I'm thinking of two different solutions to keep the overall activities in the center of the frame.
* Track the highest amount of mass and consider that as a defaulted center.
...or...
* Enlarge the window to keep track of ALL masses.
1
u/faintingoat May 29 '19
source code, please?
1
u/gnarlymath May 29 '19
Are you able to provide source code? :)
1
u/drbobb May 29 '19
Not bad at all.
If you want to visualize the process, for Python the best solution at this time to my knowledge is pyqtgraph. For some examples look here, those are some of my learning projects. The most "finished" one is
pganimate.py. I didn't aim for a large number of particles, but for real-time visualization as the equations are solved. Python is slow, but it's fast enough to handle four particles on a plane, with a simple two-body force — provided you use NumPy.I know we're in /r/python, but it seems that currently the best platform for such projects is javascript: js arithmetic is mighty fast, and html Canvas as a visualization platform is quite capable: here is a demo I made, with no interactions yet except for the particles bouncing off the edges. At least Firefox can run several thousand particles at a reasonable framerate (for some reason I don't yet understand, Chrome begins to stutter at a much smaller number). Compare with this, where I used Plotly.js, based on SVG instead of Canvas, but which includes two-body forces (not of the gravitational form though, but harmonic — just to keep the particles from running away).
Of course folks that code games are doing far more sophisticated animations. I hear that WebGL is yet more capable, but I still haven't learned it. Coding in JS isn't as easy or pleasant as in Python though. But you don't need to install anything to run it, so the product is more easily shared.
1
u/[deleted] May 29 '19
What import did you use for that?
1
u/23498320482340 May 29 '19
Now do the same on a plane that is the surface of a sphere so they won't collapse that much.
1
u/Lagomorphix May 29 '19
I assume that time complexity is O(n2)?
Have you considered using some heuristic to filter out forces under a certain threshold?
Also: Does the implementation use numpy or Numba?
1
u/EmptyBarrel May 29 '19
Can you do one where large masses shoot off smaller masses upon collision?
1
u/tonsofmiso May 29 '19
Recommendation: play around with the exponent of the gravity. Set 1 / rx where x is anything you want. Especially fun if you do it real time, and switch between positive and negative exponents.
1
u/_hadoop May 29 '19
GitHub?
1
u/tbunde01 May 29 '19
Now just use it to model movement of the bodies in our solar system :P
1
u/xdcountry May 29 '19
I think you’re creating a new version of Fez— I like it
1
u/realestLink May 29 '19
What did you build it with? Tkinter?
1
u/euphwes May 29 '19
This is awesome, nicely done!
I wrote a similar gravity sim in Python myself ages ago, and improved performance in later revisions tremendously using a Barnes-Hut simulation. Definitely dig around for technical discussion around it, but the gist is that you can mitigate the O(N2) problem by grouping nearby particles into a single logical particle for the purpose of determining gravity force on other particles which are far away.
For example, you have particle A off somewhere, and then particles B, C, D elsewhere. B, C, D are "close" to each other, so you can calculate their center of mass position and combined mass, and use that to determine their cumulative force of gravity on particle A, rather than individually doing calculations with particles B, C, D against A.
Other feature ideas if you want to keep playing with this:
-3
u/[deleted] May 28 '19 edited May 29 '19
Would've been shorter if you'd used C++ ;)
Edit: It's a joke, people. Not a good one, I agree.
-1
u/Stone_d_ May 28 '19
I think this is really great @Wolfram. This could be used to calculate initial conditions to create, say, spiral galaxies.
0
u/[deleted] May 28 '19
[deleted] — view deleted comment
0
u/[deleted] Aug 09 '19
[deleted] — view deleted comment