Math of Universe Sandbox

[FGFG]

This discussion branched off the Nintendo DS concept post.
http://universesandbox.com/forum/index.php/topic,345.0.html
FGFG is discussing how many calculations Universe Sandbox does each second. - Dan

The fact that it is in 3D doesn't mean that the DS is capable of great calculations in order to support Universe Sandbox (even in 2D). A game such as that doesn't require much CPU because there are 2 guys fighting each other with the same movements pre-defined and stored in the memory of the game and not calculated every time. Universe Sandbox, instead, needs much more CPU because it has to calculate all the iteractions between an object and all the others, repeat the algorithm for every object and then repeat all of this again at least 20 times per second, so that it doesn't look too slow...

for example (i hope this is how US works, i'm not sure of it):

there is the famous formula F=G(m1*m2)/d^2 that can be applied to both m1 and m2 (so 1 calculation for every couple of objects ==> 5 bodys are 10 calculation, for 20 bodies are 190, for 100 bodies are 4950).

All the forces found for each body must become just 1 resultant (so n-1 vectorial sums, where n is the number of forces) again for each body; a vectorial sum is made basically with the 2 forces, and the angle between them. If you want i can explicit the formula later).
5 bodies: 15 calculations
20 bodies: 360 calculations
100 bodies: 9800 calculations

Then the Forces have to become accelerations... F=m*a so a = F/m (again for each body)

With the velocity of the body and his acceleration, we can finally calculate the position in the new frame (i don't know how this is calculated however)

the total sums of calculations for each frame is:
5 bodies: 31
20 bodies: 541
100 bodies: 14851

Assuming that you want 20 fps:
5 bodies: 620/s
20 bodies: 10820/s
100 bodies: 297020/s (!)

At last the programme has to translate all these data in an image with procedures that i don'r know.

I just hope MY calculations are correct  
Dan, does Universe Sandbox work this way?

[SuperNova]

The fact that it is in 3D doesn't mean that the DS is capable of great calculations in order to support Universe Sandbox (even in 2D).
...

its much and much more
you must fight against 1000 enemies at one's
its much more complicated

[FGFG]

I was just saying that it's a bit hard to make Universe Sandbox on a DS, not that it is a bad idea. Just look at my first post in the previous page... It just say what I say here again, but in a way much more concise.

And the finality of my previous post was also to ask Dan if Universe Sandbox works as I've imaginated. And even if I don't think so, it could work in a way much simplier so that it could run even on a DS with small changes.

And we aren't against you, we were just explaining you what you are going towards.

[Dan Dixon]

I just hope MY calculations are correct 
Dan, does Universe Sandbox work this way?

You're mostly right. Nice work.

How are you calculating these numbers?
5 bodies: 15 calculations
20 bodies: 360 calculations
100 bodies: 9800 calculations

Since each body compares itself to every other... The math should be:

5 bodies: 5x4 = 20 force calculations
20 bodies: 20x19 = 380 force calculations
100 bodies: 100x99 = 9900 force calculations

Here are the basic steps:
1 - Calculate the force between each body and every other.
2 - This force is converted into the corresponding X,Y,Z forces based on where the bodies are in space.
3 - The 3D acceleration is applied to each body resulting in a new velocity and position.
4 - There are also checks for collisions between every object.
5 - And the scene is redrawn.

[FGFG]

THIS IS A POST ABOUT THE MATH OF US, IF IT DOESN'T INTEREST YOU, JUST DON'T READ IT

How are you calculating these numbers?
5 bodies: 15 calculations
20 bodies: 360 calculations
100 bodies: 9800 calculations

Since each body compares itself to every other... The math should be:

5 bodies: 5x4 = 20 force calculations
20 bodies: 20x19 = 380 force calculations
100 bodies: 100x99 = 9900 force calculations

I thought that when you calculate the forces of the bodies you obtain n-1 (e.g. 5-1 = 4) forces for each body, (where n is the number of bodies), so you have n-1 (4) vectors that have to be sum in order to have 1 resultant (I think that this is the passage different, maybe just in the order), so you have to do n-2 ((n-1)-1) vectorial sum as, for example, to obtain a resultant from 4 vectors you have to do 3 sums... All of this for each body, so I obtained the equation c (calculations) = (n-2)*n

e.g. 5:  c = (5-2)*5 = 15
...and so on

Probably the passage different is the 2nd: i supposed that firstly US calculates all the forces for each body, and then it calculates the resultants before converting it to acceleration.

4 - There are also checks for collisions between every object.

I've forgot it... I think that US checks the radius of all the bodies and when 2 bodies are at a distance less than the sum of the radiuses there is a collision so, again, like for the gravity formula, there is a calculation per couple of bodies ==> for 5 bodies there are 10 calculation, 190 for 20, and so on...

Totally, without considering the calculation for the collisions themselves there would be:

5: 41 calculation per frame * 20 fps = 820 calculations per second
20: 731 cpf * 20 fps = 14620 cps
100: 19801 cpf * 20 fps = 396020 cps

Again, I hope they are correct.

Probably during a collision in combine mode, the mass is summed, the velocity is calculated, considering the kinetic energy and the quantity of mote for the module, and using another vectorial sum for the direction (however i'm not sure of this because at school we made only the collisions on a straight line).
In the bounce mode, when there is an elastic collision (so that the 2 bodies doesn't remain attached) it uses the same formulas, but it needs double calculation because the bodies remain separated (so 2 velocities to be calculated).

Other 2/4 calculation per collision.

What happens exctly when the 2 bodies, in the bounce mode, remain attached, escapes from my immagination and deduction...
Basically there is a collision per frame, but the position of the 2 bodies must be changed so that they don't "fall" into each other. Can't imagine the enormus amount of calculation where there are many bodies attached in a group (e.g. the systems "Moon - large/small cluster, flat disk" or even in "dice swarm" where the shape is cubic and not spherical). I cannot imagine the calculations for the velocities too...

Well i think, Dan, that you made an excellent work with this simulator 

[FGFG]

I made another post to make order in the calculation count (I cannot understand what I have written )

I did some mistakes in the previous calculations so these should be correct:


Calculation of the Forces between the bodies (gravity); 1 calculation every couple of bodies:
bodies:calculations (total)
n: ((n-1)/2)*n (try to draw a pentagon, as i did, to understand this...)
5: 10 (10)
20: 190 (190)
100: 4950 (4950)

Then, for each bodie you have to do the sum of the forces to obtain just 1 resultant:
n: (#OfForces - 1)*n ==> ((n-1)-1)*n) ==> (n-2)*n
5: 15 (25)
20: 360 (550)
100: 9800 (14750)

Then the resultants have to become accelerations (1 calculation per body):
n: n
5: 5 (30)
20: 20 (570)
100: 100 (14850)

The check for the collisions, a calculation per couple of bodies...
n: ((n-1)/2)*n
5: 10 (40)
20: 190 (760)
100: 4950 (19800)

Here there should be the calculations depending on how many collisions happened in the frame...

Total calculation per frame, without considering collisions:

c: [(n-1)/2]*n + (n-2)*n + n + [(n-1)/2]*n ==> 2*[(n-1)/2]*n + (n-2)*n + n ==> (n-1)*n + (n-2)*n + n ==>
==> (n-1 +n-2 + 1)*n ==> (2n - 2)*n ==> c = (n - 1)*2n

Total calculations per second (assuming that there are, at least, 20 frames per second):

n: c = (n - 1)*2n*frames

0 and 1: 0 (obviously)
5: 800
10: 3'600
20: 15'200
50: 98'000
100: 396'000
1000: 39'960'000

and so on...

EDIT (as always): I passed an hour making math and i came up with just this: c = (n - 1)*2n*f. It's incredible how much the world is ruled by simple lows, as the newton's one F=G(M*m)/d^2 or Einstain's E=mc^2...

[Chaotic Cow]

*Head explodes*

[Bla]

Okay... I won't start arguing about the power of the DS, since I don't know it, but it looks very unrealistic that it could handle more than 10 bodies with the same features as US on the computer.

But I just thought of a mini game inside the game!
There is one big body in the center. You have to launch smaller bodies against it, while zooming out from it and perhaps rotating around it, so it changes the place on your screen. Your bodies need to hit it, and each time they do, it becomes bigger. But as you zoom out it also becomes smaller. So the mass increases as you hit it more times, but if you don't hit it and it becomes so small that you can't see it on your screen, you lose and the mass is shown on a highscore list!
If the body becomes too big and fills more than a certain size of your screen, the camera just zooms out extra much for a short amount of time until it fills a size that is ok.

[Maccara]

I just hope MY calculations are correct  
Dan, does Universe Sandbox work this way?

You're mostly right. Nice work.

[...]

Since each body compares itself to every other... The math should be:

[...]

Here are the basic steps:
1 - Calculate the force between each body and every other.
2 - This force is converted into the corresponding X,Y,Z forces based on where the bodies are in space.
3 - The 3D acceleration is applied to each body resulting in a new velocity and position.
4 - There are also checks for collisions between every object.
5 - And the scene is redrawn.

Dan & FGFG,

You've discussed the basic math and flow diagram how this goes, but isn't this only a small part of what is _really_ important? Isn't integration of the timesteps the major part of the calculations?

I.e., Dan: What integration method does US use? I suspect Euler? (seeing how US behaves with different timesteps) That's fast but inaccurate (on larger timesteps).

Have you tried to implement other integration methods (I'm thinking of Runge-Kutta, f.e.)?

I would LOVE to try to implement RK4 n-body simulation on a GPU (once OpenCL is out). One AMD presentation about that method (Euler only, though) can be seen at http://ati.amd.com/developer/gdc/2007/Drone-Real-Time_Particles_Systems_on_the_GPU_in_Dynamic_Environments(Siggraph07).pdf.

Parker-Sochacki[1] method would also be interesting to study, but I haven't checked the math yet if that would be feasible for GPU acceleration.

I suspect .NET framework will support OpenCL directly at some point (not .Net 4 yet, I think) but I bet in the meanwhile there will be libraries to support that.

1. Joseph W. Rudmin, “Application of the Parker-Sochacki Method to Celestial Mechanics,” http://csma31.csm.jmu.edu/physics/rudmin/ParkerSochacki.htm.

Edit: references to CUDA changed to OpenCL (what was I thinking... .

[FGFG]

Dan & FGFG,

You've discussed the basic math and flow diagram how this goes, but isn't this only a small part of what is _really_ important? Isn't integration of the timesteps the major part of the calculations?

I.e., Dan: What integration method does US use? I suspect Euler? (seeing how US behaves with different timesteps) That's fast but inaccurate (on larger timesteps).
...

I don't know much of programming (quite nothing), so i was just asking Dan if those are the correct procedures.

About the timestep: I thought that the new positions of the bodies could be calculated using the speed found in the first frame, applied to it for the timestep so that you find the new position.

This method is very imprecise if the timestep become too large (What happens in US after all) as the larger is the timestep, the larger is the distance that the body travels every frame on a straight line.

[Maccara]

About the timestep: I thought that the new positions of the bodies could be calculated using the speed found in the first frame, applied to it for the timestep so that you find the new position.

This method is very imprecise if the timestep become too large (What happens in US after all) as the larger is the timestep, the larger is the distance that the body travels every frame on a straight line.

Ah, but that's the point of my question. Direct numerical (as there is no analytical solution to a n-body problem) linear regression (i.e. "straight line segments" as you describe above) is VERY inefficient and requires extremely small timestep to show results resembling anything close to reality - and I really hope US is not THAT simplistic.

You can only have "absolutely" accurate simulation when timestep approaches 0, which is impossible, of course, as then the required calculations per second of simulation would approach infinity. That's where the different integrators[2] come in.

For example:

Euler's method[1] is very fast (execution wise) but requires a small time step and accuracy deteriorates very fast when you increase the timestep.

Runge-Kutta[3] (several implementation possibilities, RK4 is very common), however, is a bit "heavier" (execution time / timestep), but is usually more accurate (compared to Euler's) when you increase the timestep.

The trick is to find the "optimum" method for a given problem - i.e. which is faster: small time step with inaccurate solver or large timestep with a complex solver? This depends on the size and nature of the problem. Dan might have tried different integrators and decided that for the given scope a certain method gave optimum results (or he has not tried, and therefore it might be a good thing to check).


1. “Euler method - Wikipedia, the free encyclopedia,” http://en.wikipedia.org/wiki/Euler%27s_method.

2. “Numerical ordinary differential equations - Wikipedia, the free encyclopedia,” http://en.wikipedia.org/wiki/Numerical_ordinary_differential_equations.

3. “Runge–Kutta methods - Wikipedia, the free encyclopedia,” http://en.wikipedia.org/wiki/Runge-Kutta.

[FGFG]

1. “Euler method - Wikipedia, the free encyclopedia,” http://en.wikipedia.org/wiki/Euler%27s_method.

2. “Numerical ordinary differential equations - Wikipedia, the free encyclopedia,” http://en.wikipedia.org/wiki/Numerical_ordinary_differential_equations.

3. “Runge–Kutta methods - Wikipedia, the free encyclopedia,” http://en.wikipedia.org/wiki/Runge-Kutta.

I had a look on the articles and there is math that I don't know yet. I've just finished the 3rd year of high school, and we will do the integrals in the 4th and / or the 5th one (don't remember).

[Maccara]

I had a look on the articles and there is math that I don't know yet. I've just finished the 3rd year of high school, and we will do the integrals in the 4th and / or the 5th one (don't remember).

Ok, just a quick explanation of the basics. (some terms I'm using may be a little wrong, as I haven't been educated formally in these either - I've learned them and how to apply them on my own)

Derivatives measure the "rate of change", for example 1st derivative of position is velocity and the the next is acceleration. Integrals basically give you the reverse, f.e. when you want to get the position from acceleration.

A good illustration of this http://hyperphysics.phy-astr.gsu.edu/Hbase/acons.html#c2

These are of course paramount if you want to describe motion of a particle for all but the most simplistic cases (constant acceleration etc). Unfortunately, there's no analytical solution for a n-body problem (that would be fantastic - timestep of 1 billion years accurately , and that's why we need numerical solutions and to choose a sufficient timestep to solve those equations at.

This is where the different methods come in. They approximate the solutions to the differential equations with a given timestep (usually) giving better approximations than linear regression of for example f=ma would at the same timestep.

This allows us to have a reasonably fast simulation with sufficient accuracy.

[FGFG]

ok, now it sounds clearer. However i will totally understand this (and maybe try to find the right formulas myself) in 1 or 2 years

[Maccara]

ok, now it sounds clearer. However i will totally understand this (and maybe try to find the right formulas myself) in 1 or 2 years

Yes, this will become painfully obvious (that you need calculus to solve the motion problems) as soon as you encounter the problem "I have time dependent acceleration a(t), so what will the position x(t) be at t=5 minutes from now", as is the case in US, for example. Pure number crunching for all variables is not a very efficient way to solve the problem.

Word of caution: in school they will teach "sanitized" integration (easy & nice solutions proportionally shown much more often) and many students are "shocked" in the real world that there actually often are not any easy solutions to the equations.

I'm not sure, but I think it actually is _proven_ there is no general solution for the n-body problem (Dan probably knows more about this than me), so if you manage to find the right formulas (i.e. invent the needed math) be ready for the eventual invitation as a guest of honor to the Nobel Prize gala.

[Dan Dixon]

What happens exctly when the 2 bodies, in the bounce mode, remain attached, escapes from my immagination and deduction...

When objects get near each other then I spawn a localized physics simulation using Newton Game Dynamics (a physics library) to handle their interaction.
http://www.newtondynamics.com/

Total calculations per second (assuming that there are, at least, 20 frames per second):
5: 800
10: 3'600
20: 15'200
50: 98'000
100: 396'000
1000: 39'960'000

Awesome. Since every body (with mass) effects every other body, it becomes clear why adding more bodies makes Universe Sandbox slower and slower. This is the very nature of n-body problems.
http://en.wikipedia.org/wiki/N-body

At the same time, there's all kinds of crazy calculations going on under the hood that aren't considered. Even simple stuff like checking what buttons are under the mouse cursor is a shocking number of calculations. I'm amazed at how fast computers can do all the things we ask of them.

*Head explodes*

That would have been awesome to see in slow motion.

But I just thought of a mini game inside the game!

I like that idea. Someday I may add a mini-game mode to Universe Sandbox. This one would be fun.

You've discussed the basic math and flow diagram how this goes, but isn't this only a small part of what is _really_ important? Isn't integration of the timesteps the major part of the calculations?

Yes. Integration is very important. In my overly simplistic 5 step list, integration was basically steps 1-3.

I.e., Dan: What integration method does US use? I suspect Euler? (seeing how US behaves with different timesteps) That's fast but inaccurate (on larger timesteps).

You're right. It's the simple, fast, and inaccurate Euler (pronounced 'oiler').

Have you tried to implement other integration methods (I'm thinking of Runge-Kutta, f.e.)?

As it turns out... Last weekend I spent about 4 hours adding Runge-Kutta 4 as a switchable option along side the existing Euler method. It seems to be generally working, but some of the bodies seem to drift either in or out from their 'parent'. I suspect that I've done something wrong. Since this isn't a critical issue, the worst case is that I'll release Universe Sandbox with the ability to switch to this new mode (Runge-Kutta 4) as an Advanced/Experimental option and the current method will be the default. Best case is that I fix it before the release, I like how it's working, and it becomes the new default.

This method [Euler] is very imprecise if the timestep become too large (What happens in US after all) as the larger is the timestep, the larger is the distance that the body travels every frame on a straight line.

Correct.

and I really hope US is not THAT simplistic.

I'm working on it.

The trick is to find the "optimum" method for a given problem - i.e. which is faster: small time step with inaccurate solver or large time step with a complex solver?

It's my understanding that RK4 will take about 4 times as long to do the calculations, but that you should be able to crank the time step up by more than 4 and get more accurate results. I have yet to verify this.

I had a look on the articles and there is math that I don't know yet. I've just finished the 3rd year of high school, and we will do the integrals in the 4th and / or the 5th one (don't remember).

This article was very helpful to me. It might help it make more sense to you:
http://gafferongames.com/game-physics/integration-basics/

Although this example is dealing with motion on a single axis and acceleration that is based on a specific time. Universe Sandbox is 3 axis and the acceleration is based on the positions of other bodies over time.

Word of caution: in school they will teach "sanitized" integration

My experience in high school was retrospective disappointment at how calculus and physics weren't integrated into a single class. They should be taught together, at least for part of them.

It's so amazing how position, velocity, and acceleration are simply the derivatives of each other. When I first understood this, it was a WOW moment for me.

I'm not sure, but I think it actually is _proven_ there is no general solution for the n-body problem...

I'm not sure either, but that sounds about right.

[Chaotic Cow]

That would have been awesome to see in slow motion.

Warning...Gruesome.

http://i4.photobucket.com/albums/y110/protestwarriors/ScannersExplodingHead.gif

On another note.

I will never be good in math. xD

[Maccara]

As it turns out... Last weekend I spent about 4 hours adding Runge-Kutta 4 as a switchable option along side the existing Euler method. It seems to be generally working, but some of the bodies seem to drift either in or out from their 'parent'. I suspect that I've done something wrong. Since this isn't a critical issue, the worst case is that I'll release Universe Sandbox with the ability to switch to this new mode (Runge-Kutta 4) as an Advanced/Experimental option and the current method will be the default. Best case is that I fix it before the release, I like how it's working, and it becomes the new default.

Sounds great! I'm looking forward to see different methods implemented.

Hmm... Have you considered, that RK4 does not conserve energy over long periods of time? That will "drift"[1], and may be what you noticed... You might want to check out if there exists symplectic[2] correction for RK4 (I don't know). However, Euler's method is not a symplectic integrator either.

...but it shouldn't be too noticeable unless there is a big timestep or simulation is run for a long period, so error in implementation is of course a possibility too worth checking for...

Did you take a look at the Parker-Sochacki method I posted earlier? It is an extension (faster) of Picard method (which is supposed to be much more accurate than RK4, but very expensive as the number of bodies grow) and even includes some code (for the Taylor expansion) for a n-body problem. It would be great to test that too at some point (I understand you need to prioritize matters, of course, so I am not expecting anything ).

It's my understanding that RK4 will take about 4 times as long to do the calculations, but that you should be able to crank the time step up by more than 4 and get more accurate results. I have yet to verify this.

Yes, this is my understanding too. However, there are situations where the simpler Euler is indeed faster (metric being same accuracy over some pre-defined period of time) and needs to be verified for the given problem.

So you would need to find desired accuracy (or simply minimize error and test how big a timestep you can crank to retain that) over some definite period of time (100 years, for example?) and check how fast each method converges to the desired accuracy. May require quite a few simulations...

Also, due to the energy conservation issue, you have to limit the maximum timestep (or use a higher order integrator) if you want to retain a stable system over long periods of time. (But you knew that already, of course.)


1. “Energy drift - Wikipedia, the free encyclopedia,” http://en.wikipedia.org/wiki/Energy_drift.

2. “Symplectic integrator - Wikipedia, the free encyclopedia,” http://en.wikipedia.org/wiki/Symplectic_integrator.

[atommo999]

aarrgghh i'm no good at maths

[Dan Dixon]

Have you considered, that RK4 does not conserve energy over long periods of time?

That's probably exactly what's going on. I'll likely add some advanced global statistics info to track energy loss across time. Thanks.

Did you take a look at the Parker-Sochacki method I posted earlier?

I read a little about it. It looks like this works with a few bodies, but doesn't work very well when the number becomes too high. Good suggestion.

Also, due to the energy conservation issue, you have to limit the maximum timestep (or use a higher order integrator) if you want to retain a stable system over long periods of time. (But you knew that already, of course.)

I always appreciate the reminder.

aarrgghh i'm no good at maths

Practice and time will solve this.

[Maccara]

I forgot to add earlier, for anyone interested, a good primer for orbital mechanics: http://www.braeunig.us/space/orbmech.htm.

Excellent reference if you're planning to create your own systems (and if US were to incorporate more orbital parameters in the UI at some point).

Root of that (http://www.braeunig.us/space/) also has other interesting stuff for all who are interested in space flight in general.

[transavt]

I too was engaged in programming of a gravitational simulator and did it by other iterative method.
Movement is represented as number X=Xo+Vot+Ao (t^2)/2+Bo (t^3)/6+Co (t^4)/24 +... And so on.
Factors Ao, Bo, Co... Are calculated consistently in each iteration.
Method difficult, but he allows to take enough big timestep. And as a result speed of calculation appears such as at you, but accuracy essentially above.
Sorry for my English is a translator.