Embassy of Time

Gravity systems?

36 posts in this topic

Posted (edited)

Okay, that's one solution indeed!  :-)   I guess it's important to remind yourself, what are you trying to achieve.  Are you trying to model the actual physics or make something that LOOKS real for gaming purposes?  If the latter, then tricks like this or softening which was mentioned earlier (which is used in many 'real' science/astro simulations btw), are perfectly valid.  Regarding the suggestion about adaptive timesteps, this is again something you would definitely do to follow the physics more accurately but then you have unpredictable rates since your simulation slows down whenever two stars get close and then speeds up again, all very jerky and unstable.  So a fixed timestep works fine if your not bothered about getting things right with close interactions.  But if you want to model the physics accurately (out of some scientific curiosity for instance) then definitely consider it.

Definitely going for "close enough"! I will no doubt go for something more advanced later on, but for now, something that is scientifically 'close', but not 'accuracy over usability'. 
 

The advantage is you get more accurate integration of the orbits (actually important for both scientifically accurate simulations and for making it look better) since leapfrog/mid-point gives second-order errors compared to Euler integration which is first-order.  A leapfrog integrator is also a special kind of integrator (called a symplectic scheme) which has wonderful conservation properties which amongst others preserves circular and elliptical orbits (e.g. planets or binaries) very well.  The thing is, all these schemes are as expensive as each other, just one force computation per timestep so in that case you would use the better one right? :-)

Decisions, decisions. But you do make it sound pretty good, although I will need to study it much closer! I am starting to think I need a mixture... 
 

I'm going to have to disappoint you on this one.  You are of course correct for two bodies.  This problem was solved by Sir Isaac Newton some 300+ years ago :-) .  And in the intermediate centuries, everybody and their cat has tried to add just one more body to solve the so-called 3-body problem.  But there is no general solution I'm afraid that can be used like you hope for.  There are various special so-called 'restricted' 3-body problems where the motion of 1 body is limited in some way so it becomes a 2-body problem again or has some special solution for some configuration.  But in general, and especially when this becomes 4, 5 ... N bodies, you have to do the numerical integration I'm afraid!  This is one of the step-ups from linear/soluable equations to non-linear equations.  All the 'geniuses' of yesteryear solved the 'easy' linear stuff :-D and left all the difficult non-linear stuff to our generation!  :-/   Oh well ...

I am starting to accept that. I am still holding out hope for something similar that is simply 'science-adjacent'. But that is a future thing, I am trying to keep my eyes on the ball for now...
 

Regarding the oct-tree, I'm still a little unsure if you really need it for gravity integration (for the reasons discussed earlier about the ~1000 body limit).  However, if you want to model some kind of larger Universe with large-scale structure and then 'zoom' into galaxies and further, then having a tree structure to organise this data hierarchically is obviously a good thing.  If you can combine it with helping to compute the gravity, then great but I'm still unsure if you'll get that much benefit while maintaining 30/60fps.

I am convinced that I will have to do a lot of weighing systems against each other, maybe mix and match. Who would have thought this would be difficult ;-p 
 

I really can't tell if you are trolling, at this point. I'll feed you a Wikipedia page about the subject: https://en.wikipedia.org/wiki/N-body_problem . No, you will not find an analytical solution to anything beyond n=3.

No, not trolling, why would I? I am just hoping that there is something I am ignorant of, but hope is failing me on that particular account... :(

I see octrees already mentioned, but in case you don't know about it, there's a name for this technique used for this specific purpose: Barnes-Hut. You can trade accuracy for efficiency.

Some links that explain more:

https://en.wikipedia.org/wiki/Barnes-Hut

http://www.cs.princeton.edu/courses/archive/fall04/cos126/assignments/barnes-hut.html

Thanks! I am shopping around for good stuff, didn't know the Princeton one! Edited by Embassy of Time
0

Share this post


Link to post
Share on other sites

Posted (edited)


 

This is the  eternal issue, isn't it. What bothers me is that my brain keeps telling me that there should be a way to compress all the forces into a single equation (possibly one per particle) and find the position of the particle as a function of time.

I'm going to have to disappoint you on this one.  You are of course correct for two bodies.  This problem was solved by Sir Isaac Newton some 300+ years ago :-) .

 

 
Kepler doesn't get the respect he deserves  :P
But yes, you are correct. This is an inherently hard problem and there is no analytical solution.  Only numerical ones.  And lots of trickery and faking-it, as is always the case in game programming.
 

Not sure I fully understand the advantage of the leapfrog or midpoint? I mean, the implementation seems easy enough, but what do I get out of it?

 
Better stability in general.  Honestly, though, it's probably not worth implementing until you identify a need for it.

https://codepen.io/kemick/pen/YQpepN

Wrote a quick comparison.  The particles fall (using a constant gravity force) and then bounce back up using a spring force.  The blue lines indicate the starting point and the floor.  The red lines indicate the maximum bounds that the particle has moved.

The leftmost box integrates with a bad version of euler. It also explodes very quickly at the given timestep.

 (newPos, newVel) += (oldVel, oldForce)

 
The middle box integrates with symplectic euler integration.  It gains and loses some energy.  At the very least, you should be using this form.

(newPos, newVel) += (oldVel, newForce) 

 
The right box integrates using leapfrog. See the source for details since it's a bit longer.

So as you can see, for the given timestep the leapfrog method conserves its energy very well.  However, it may not be necessary depending on your accuracy requirements. 
 

Edited by Kem7
1

Share this post


Link to post
Share on other sites

This is the  eternal issue, isn't it. What bothers me is that my brain keeps telling me that there should be a way to compress all the forces into a single equation (possibly one per particle) and find the position of the particle as a function of time.

I'm going to have to disappoint you on this one.  You are of course correct for two bodies.  This problem was solved by Sir Isaac Newton some 300+ years ago :-) .

 
Kepler doesn't get the respect he deserves  :P
But yes, you are correct. This is an inherently hard problem and there is no analytical solution.  Only numerical ones.  And lots of trickery and faking-it, as is always the case in game programming.
 

Not sure I fully understand the advantage of the leapfrog or midpoint? I mean, the implementation seems easy enough, but what do I get out of it?

 
Better stability in general.  Honestly, though, it's probably not worth implementing until you identify a need for it.
https://codepen.io/kemick/pen/YQpepN
Wrote a quick comparison.  The particles fall (using a constant gravity force) and then bounce back up using a spring force.  The blue lines indicate the starting point and the floor.  The red lines indicate the maximum bounds that the particle has moved.
The leftmost box integrates with a bad version of euler. It also explodes very quickly at the given timestep.
 (newPos, newVel) += (oldVel, oldForce)
 
The middle box integrates with symplectic euler integration.  It gains and loses some energy.  At the very least, you should be using this form.
(newPos, newVel) += (oldVel, newForce) 
 
The right box integrates using leapfrog. See the source for details since it's a bit longer.
So as you can see, for the given timestep the leapfrog method conserves its energy very well.  However, it may not be necessary depending on your accuracy requirements.

Thanks, I needed that kind of more 'tangible' thing. I think you're right, leapfrog may be a bit better in some ways, but it would take an immense effort to rewrtie for it (including learning an dunderstanding it), so that will be for a possible future version.
It still feels utterly bizarre that there is no conversion-to-static-equation solution. But something tells me others have said the same as me, and then lost decades to finding an answer. The bold should beware, I guess :-o
0

Share this post


Link to post
Share on other sites

Posted (edited)

It still feels utterly bizarre that there is no conversion-to-static-equation solution.


The 2-body solution utilizes conic sections (ellipses, in the case of a stable orbit) to approximate the movement of a body.  If you wanted, you could model 8 planets orbiting the sun with reasonable accuracy because, with a few exceptions, our planets have stable elliptical orbits.  So the issue is not with the number of bodies, but instead how hard their movements are to model.

This becomes more obvious if you look at it from the opposite direction. Instead of looking at the interaction, look at the result.

A single body's trajectory (with no forces applied) can be described by a line. The line only ever needs position/velocity.  The velocity is constant.

The trajectories of two bodies can be modeled using conic sections. In the case of stable orbits, that would be an ellipse. An ellipse only ever needs major and minor axes and position/velocity.  The velocity changes, but is cyclical and so it repeats.

Now, how would you model the trajectories of three arbitrary bodies doing whatever?  In the previous two cases, there was a single equation that you found the parameters to. Here, the velocity can do whatever and so the equation will be some wacky polynomial whose form changes depending on the state of the system. There can be no general equation that you just plug numbers into.  And any specific equation that you could generate would grow larger and more wacky as the system progressed, whereas the previous two examples remain constant.

As I've said, this is an inherently hard problem.  There are no clever answers to be found, only clever approximations.

Edited by Kem7
1

Share this post


Link to post
Share on other sites
On 16/6/2017 at 8:46 PM, Kem7 said:

Now, how would you model the trajectories of three arbitrary bodies doing whatever?

Trust me, I have been trying to figure something, anything, out, but I understand the difficulty / impossibility of it. For 3-body, what comes to mind is a shifting barycenter, calculated as a point all its own, according to masses around it. But I am just spitballing, I have no actual idea...

On 16/6/2017 at 9:54 PM, taby said:

You may also want to try the Range Kutta 4 (RK4) for integration: http://gafferongames.com/game-physics/integration-basics/

RK4 is slower than Euler integration or leapfrog, but it is more precise.

RK4 has been mentioned before. It seems versatile, but I have to read up on it. Thanks!

0

Share this post


Link to post
Share on other sites
On 6/19/2017 at 11:11 AM, Embassy of Time said:

Trust me, I have been trying to figure something, anything, out, but I understand the difficulty / impossibility of it. For 3-body, what comes to mind is a shifting barycenter, calculated as a point all its own, according to masses around it. But I am just spitballing, I have no actual idea...

RK4 has been mentioned before. It seems versatile, but I have to read up on it. Thanks!

It's about the quantity of information involved.  You can model two orbiting bodies an arbitrary amount of time into the future.  No matter how far you go into the future, bodies' path take up a constant amount of storage space because they travel the perimeter of the ellipse.  

Three bodies, all applying meaningful force to each other, do not follow any particular pattern.  Particular configurations of three bodies may, but not arbitrary configurations.  You might be able to model their trajectories, but those paths would take up an increasingly large amount of storage space, limited only by how long the simulation is run.  And you'd probably need numerical integration to compute those paths to begin with.

 

That said, the advantage of such a solution is that, if you can simplify the orbits into repeating patterns, you can calculate a year into the future as easily as you can calculate a second.  Three bodies can be simulated as long as their trajectories are are easy to represent and the error introduced by simplifying their trajectories is acceptable.  

As I mentioned, the 8 planets can be modeled using ellipses.  You can also model the earth-moon system orbiting the sun (3 bodies).

The disadvantage of such a solution is, of course, that calculating a second into the future is as expensive as calculating a year in the future.  And in the case of ellipses it's gonna look something like: 

meanAnomaly = meanMotion * (time - this.t) ;
		
eccAnomaly = meanAnomaly + this.e * Math.sin(meanAnomaly) * (1 + this.e*Math.cos(meanAnomaly));
		
var oa = 0;
do {
	oa = eccAnomaly;
	eccAnomaly = oa - (oa - this.e*Math.sin(oa) - meanAnomaly) / (1 - this.e*Math.cos(oa));	
} while (Math.abs(eccAnomaly - oa) > 1.0e-6);					

trueAnomaly = 2*Math.atan(Math.sqrt((1+this.e)/(1-this.e)) * Math.tan(eccAnomaly/2));		
distanceNow = this.a * ( 1 - this.e * Math.cos(eccAnomaly));

var positionX = Math.cos(trueAnomaly)
var positionY = Math.sin(trueAnomaly);

This is the bulk of converting kepler elements to cartesian coordinates. It's not fast. Even an optimized version, for a large number of objects, would be more expensive than just doing numerical integration.  And this is just for an ellipse.  This kind of solution is wonderfully suited for situations where you need to be able to skip forward (or backward) arbitrary amounts of time, but not well suited for real-time evaluation. Unless you are able to limit yourself to 2-bodies at a time and ellipses, parabola, and hyperbola to model trajectories (while also needing the ability to skip forward or backward), stick with numerical integration.

Edited by Kem7
0

Share this post


Link to post
Share on other sites

I cannot help thinking that a game that needs accurate simulation of star clusters or galaxies must be very peculiar: on scales of many light years, stars take at least decades to move a significant amount relative to the distance to their nearest neighbours, so concrete effects on characters in a game are going to be noticeable only at extreme time scales.

In a game that simulates a few years of space adventures moving stars at all, let alone in a correct gravity simulation, is an unnecessary luxury.

Realistic simulations might be desired for procedural generation purposes, but even in this case they offer no advantage over randomly generating the contemporary state according to realistic constraints and random distributions.

1

Share this post


Link to post
Share on other sites
16 hours ago, Kem7 said:

It's about the quantity of information involved.  You can model two orbiting bodies an arbitrary amount of time into the future.  No matter how far you go into the future, bodies' path take up a constant amount of storage space because they travel the perimeter of the ellipse. 

Yeah, I do seem to be staring at a brick wall here. I've spent the last week or so really reconsidering what I need compared to what I am doing, and maybe this isn't the hill I should choose to die on. I think some approximation will be used from here on in. As long as there is a sense of the progression of time. But right now, I feel a bit burned out by the brick wall :(

10 hours ago, LorenzoGatti said:

I cannot help thinking that a game that needs accurate simulation of star clusters or galaxies must be very peculiar: on scales of many light years, stars take at least decades to move a significant amount relative to the distance to their nearest neighbours, so concrete effects on characters in a game are going to be noticeable only at extreme time scales.

In a game that simulates a few years of space adventures moving stars at all, let alone in a correct gravity simulation, is an unnecessary luxury.

Realistic simulations might be desired for procedural generation purposes, but even in this case they offer no advantage over randomly generating the contemporary state according to realistic constraints and random distributions.

It's a time travel game. I really don't need this level of detail, but something just went a bit out of control. What I want is a full universe that ages and evolves, and although the focus is intended mostly on planets evolving, the astronomy part is important, too. It sets up the big stage's depth, so to speak. But yeah, as mentioned above, I have started to reevaluate what is needed and what is just me being nitpicky, because I seem to be stuck at the N-body problem....

0

Share this post


Link to post
Share on other sites

How much time passes between consecutive featured periods and between the earliest and latest period? Many approximations seem possible.

  • No star movement at all
  • Simple interpolation between random states
  • A different random state in each time period

 

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now