A potential way to solve the N-body problem.

[Spica]

Hey there forums!

Here is a possible way to solve the N-body problem, not that SQUAD must implement this though.

Since the equation for the combined gravitational force between 2 objects is Fg=(G*m1*m2)/r^2.

You could just sample that equation once for each body for each physics step, and in order to draw trajectories in the map view, you would sample that equation for all major celestial bodies on the kerbol system, therefore all planets if you are primarily bound to kerbol. In the case that you are orbiting jool, all of its moons will be calculated, as well as the major planets (including dres and eeloo), but not the major planets respective moons. One exception though, the gravitational forece from duna and ike will be averaged together first because of their relatively similar sizes. Once all the vectors for the gravitational attractions are averaged together, there is the gravity vector you apply to the space ship. This will be modeled for all ships with command pods, so calculations for debris will not bog down your CPU. Those said ships will then have their orbits calculated in advance in reasonable steps, such as every minute, in such a way as every hour, on the hour, the game calculates 60 new steps for the orbital path of non active vessels. Those trajectory points are them smoothed through a spline-like system to generate a smooth path. For time warps of higher than 1,000x, the calculation intervals will be spread out to one hour between each. Or faster if you have a better CPU (interval will be set in settings.cfg). Hopefully you will have understood that, and if not, send me a PM, or the same if you simply would like more info.

Just to clear up any confusion, I will NOT be trying to add this to the game in a mod, but if any more experienced modders (ferram4, NathanKell , and r4m0n in particular) want to try this, I am all for it.

Spica

[Vector]

One, this is not the N-body problem, because the planets and moons are not experiencing deflections from each other, and spaceships are not having gravitational attraction to each other. The interactions grow only linearly with the number of spacecraft, not quadratically as with the N-body problem, and even the full N-body problem is not difficult for small N.

Two, the compute time for these calculations is not the reason they are excluded from the game, so "optimizing" them gets you nowhere.

This has already been discussed in other threads. Here's one: http://forum.kerbalspaceprogram.com/threads/49121-On-Newtonian-trajectories-vs-patched-conics

[fatfluffycat]

What is N-body anyways?

[Lazro]

N-body is gravity acting on and from all bodies, not just from the one in your fictional "sphere of influence."

[FacticiusVir]

N bodies, where n is a number greater than 2. The N-body problem is that there is no equation for calculating the positions of more than 2 orbital bodies with interacting gravity, for any given point in time. We can only calculate the positions by iteratively updating in small steps from a given start point.

[Superfluous J]

What is N-body anyways?

N is a way to say "undefined number".

The "2-body problem" has been solved. The Moon orbits the Earth. The Earth orbits the Sun. If there are 2 bodies that are moving in such a way that they won't collide, and won't escape each other, they'll orbit.

The "3-body problem" is different. It hasn't been solved completely but there are multiple safe ways to represent it. The Earth orbits the Sun and the Moon orbits the Earth. The Sun is far enough away that you can almost ignore it and treat this 3-body problem like it's actually two 2-body problems. There are also special areas called Lagrange Points where 3 bodies that ARE close enough to each other can stay in harmony. Also, 2 bodies can orbit a host body in resonance (Like Io and Europa orbiting Jupiter) where they technically affect each other, but the effects cancel out over time.

Anything more than 3 bodies is generally called an "N-Body Problem" and these tend to be chaotic, unless they can be represented as distinct sets of 2- or 3- body problems. So our solar system is pretty stable even though there are dozens of bodies.

Anything not described above (unless I missed something) is chaos. You cannot predict what things will look like in the future. For this game, you need to be able to do that so they "solve" the problem by not having it. Everything is on rails and the planets don't actually affect each other. And, your ships are only affected by a single planet at a time, simplifying the prediction of them as well.

[Whackjob]

What is N-body anyways?

http://en.wikipedia.org/wiki/N-body_problem

[DMagic]

http://en.wikipedia.org/wiki/N-body_problem

What is the wikipedia you speak of and why have I never heard of it before.... ?

Anyway, I don't think the computational aspects of the N-body problem are what rule out their use in KSP. I think it's the gameplay implications of trying to account for the gravitational effects of multiple bodies that keep Squad from implementing some kind of numerical or otherwise simplified N-body solution.

[vexx32]

To be perfectly clear -- as far as I am currently aware, the PhysX coding is perfectly capable of doing an n-body solution (although, yes, if you have an excessive number of orbiting bodies, stuff will start to crumple). The real issue here is that one of the primary mechanics of KSP -- timewarp -- cannot be used in an n-body environment. There is where the calculations start to get ridiculously messy. Simulating n-body gravity is one thing. Simulating it for an indefinite period of time and a rate far higher than realtime just... breaks everything.

I seem to recall Harv saying (a long time ago, back before 0.15 IIRC) something along the lines of... the PhysX code can compute n-body at a maximum of 100x warp, and this would be the Physical warp. The ship-breakingly-unstable-at-4x physical warp. You cannot do on-rails warp (or at least, it has not been figured out yet) with an n-body system. Every orbiting body would constantly be changing and shifting about, thus the rails system can never work. And I'm sure none of us want to even attempt getting to Dres with only 100x warp that is 99.999% guaranteed to break your vessel every time.

[Vector]

Seriously? The math for rails is not that hard or compute-intensive. (But then, neither is the math for SOI transitions...)

Timewarp cannot be used in an n-body environment? Can never work on rails? You're just making stuff up.

Whether it's a good idea in that it changes gameplay in a positive way, now that's a different question. I would say station keeping would be not at all fun.

[boomerdog2000]

Seriously? The math for rails is not that hard or compute-intensive. (But then, neither is the math for SOI transitions...)

Timewarp cannot be used in an n-body environment? Can never work on rails? You're just making stuff up.

Exactly, on-rails warp is easy because there are basically no physics. With n-body there are always physics, which are always changing. Changing accelerations is the limitation of the on-rails warp. Besides he didn't say timewarp wouldn't work. Physical timewarp works fine, but if you want to go ahead and try using 100X physical timewarp be my guest. Personally I'm happy with what we have.

[Kasuha]

The real issue here is that one of the primary mechanics of KSP -- timewarp -- cannot be used in an n-body environment.

That's one part of a problem. Maneuver nodes setup, where you need to do the simulation many times a second all over from scratch is another.

[vexx32]

Well, yeah. The ability to timewarp is a core mechanic of KSP, though, so seeing as n-body effectively makes it impossible, it's a bit of a deal breaker xD

[Sirrobert]

Seriously? The math for rails is not that hard or compute-intensive. (But then, neither is the math for SOI transitions...)

Timewarp cannot be used in an n-body environment? Can never work on rails? You're just making stuff up.

Whether it's a good idea in that it changes gameplay in a positive way, now that's a different question. I would say station keeping would be not at all fun.

I may be weird, but when a dev claims something can't be done in the game he is developing, I'm inclined to believe that

[Kasuha]

Well, yeah. The ability to timewarp is a core mechanic of KSP, though, so seeing as n-body effectively makes it impossible, it's a bit of a deal breaker xD

To be honest, if I take into account that there are programs out there capable of doing n-body gravitation simulation with tens of thousands bodies and compare it to hundred or two ships pulled around some twenty planets and moons in KSP I believe it should be possible to run even at decent time warp. What i see as biggest problem is probably that many currently stable orbits would become unstable and few players would be happy to realize their keostationary satellite crashed to Mun while they were warping towards Eeloo.

Regardless if it can be done or not, I believe the current implementation is good and there's no need to change it.

[vexx32]

Harvester had addressed this a few times before. 'Twas some time before the last forum crash, so it should still be about, if you dig deeply enough. If you get to Harvester's profile and trawl through his posts, you might find it reasonably quickly.

Kasuha, maybe that is so, but to be quite frank, my head splits looking at an n-body solution. Even with ~20 planets, the n-body calculations for every step of physics is insane. Try to do that a thousand times a second, and it'll almost certainly bring a computer to its knees.

[Kasuha]

Kasuha, maybe that is so, but to be quite frank, my head splits looking at an n-body solution. Even with ~20 planets, the n-body calculations for every step of physics is insane. Try to do that a thousand times a second, and it'll almost certainly bring a computer to its knees.

I was doing these simulations 30 years ago and nothing changed on their maths since then, just computers became thousand times faster. You don't need to calculate physics on the ship, you don't even need to take its weight into account because it is negligible. You have its center of mass, it's at cetain position and traveling along certain vector. You calculate gravity influence from each planet in the system (no magic, just vector sum) and update the speed and position accordingly. If you're smart, you can even estimate how long time step you can do next without introducing serious errors.

[vexx32]

Something tells me that it's going to be glitchy as all hell, but it certainly sounds worth a shot.

[Kasuha]

Something tells me that it's going to be glitchy as all hell, but it certainly sounds worth a shot.

I don't think so. I think the current implementation is better than full physics. Assuming they'll fix all bugs such as SOI intersects not showing up, SOI transitions at high time warp etc etc. The "deterministic" part is good not just for the game but for players, too.

[Grumman]

I don't think we'd need a full N-body implementation anyway. Just increasing the number of gravitational sources from one to two would be sufficient to give us Lagrange points, and that's the main thing we're really likely to notice, right?

[AngelLestat]

I also thing that something like n-body physsics can be possible to implement, how? is a different question.

So if someone knows a way to implement this (at least with 3 bodys so we can have lagrange points) consuming the same process time it will be welcome.

But it does not help said that it can be done and ask to devs to solve it.

If you have an idea how to do it... post it..

With formules and full detail.

Of course I dont see the point to simul real planets orbits with n-body physsics. The planets can still have their fixed elliptic orbit.

So this will influence only crafts.

PD EDIT: I was thinking, how KSP deals with craft orbits in timewarp mode.

If they calculate movement and gravity in timewarp mode (when you have an elliptic orbit) is a waste of process time.

If you have an elliptic orbit you can take that elliptic shape and move the craft using those elliptic parameters until you have an encounter with another body. So there is no need to calculate the gravity effect all the time.

In case this is not the current way to do it, I really suggest to do it.

This will help a lot when we have many crafts orbiting.

Edited November 5, 2013 by AngelLestat

[tetryds]

i don't see a reason to include all objects into a possible multiple body physics

the simpler solution would be apply it only as several 3-body physics

what im talking about is basically making mun SOIs bigger and adding a 3-Body physics to the object its orbiting

so at Kerbin you feel Kerbol gravity, at Mün SOI you feel Kerbin gravity, etc.

if you make these SOI's big enough you can probably keep the gravitational field error mark low

it's not 8 or 80, there is always a simple and fair implementation

[Spica]

Hello guys, I see this discussion has really taken off, so to clarify some misconceptions: One, I did not know that the calculations would be so easy on a computer, so therefore the trajectory calculations could be done more frequently. Two, I decided to keep the planets on rails because as we can see in our own solar system, planetary orbits do not change much over the course of a typical long-duration mission (10 years), or even in a lifetime.

[Meithan]

Doing N-body simulations for KSP is perfectly possible. Astronomers do them with literally billions of particles to simulate galaxy interactions. Sure, on supercomputers, and they take a couple months to run. But if you have a small numbers of bodies (say less than 100) it can be done very quickly. It's not really complicated physics. I don't know why people think it's this hugely complicated, CPU-killing problem. It's only very computation intensive when you simulate large (as in, more than a few millions) number of particles.

Timewarp is not really a problem either if the number of bodies is not too large. Matt Roesle already did an

. The video shows about 80 years of KSP game time. I don't know how much time the simulation required to compute, but in my experience with N-body codes with small numbers of bodies, I bet it's small enough that it could be computed in real time at high timewarp.

User Mattasmack analyzed this issue in great detail some time ago. He actually wrote and tried several numerical algorithms for N-body simulation and investigated what is needed in terms of computing power to accurately compute planetary positions. He concluded that N-body simulations at high timewarp are most likely possible even on modest hardware. Quoting from his website post:

These estimates are based on conservative assumptions, and so I believe any computer capable of running KSP could also calculate an acceptably large number of trajectories at 100,000x warp.

So why isn't it done? There are many reasons that I can think of.

First, if you look at

, you'll see that Vall is ejected from the Jool system very quickly. In other words, with full N-body simulation some planetary orbits will become unstable. Those that aren't unstable can still wobble and precess noticeably. This would make interplanetary rendezvous much more difficult.

Second, think of the consequences on orbits of spacecraft around massive bodies with moons. Perturbations from the moons could likely render spacecraft orbits unstable too. You won't be able to timewarp without knowing if your huge space station will remain in orbit. In his experiments, Mattasmack found that circular orbits higher than about 7.3 Mm around Kerbin (the Mun's orbit is 12 Mm in radius) were indeed unstable. Even if the orbit is stable, it will be perturbed and thus not follow an easily predictable path, which makes planning orbital rendezvous much more difficult.

In my opinion, the patched conics approach is a very good middle ground between having no realistic orbital physics and a full-physics simulator. It makes things stable enough that you can timewarp safely and reduces the game's difficulty to make it enjoyable. It's still much more realistic than most space games out there.

Edited November 5, 2013 by Meithan

[Kasuha]

Adding realistic all-body gravitational effects would add a few things the game is missing now, such as lagrange points. Needless to say, most Lagrange points are unstable and bodies in them are repelled from them rather than kept in by gravitational forces. Earth probes are kept in them by applying periodical corrections.

On the other hand, there would be a lot of issues with orbit stability, especially in crowded systems like Jool, Duna, or Kerbin. No more you can leave a probe in orbit and return to it after 1000 years of doing other missions, all your ships would require more or less constant attention. Also preparing interplanetary transits would become much more frustrating and unpredictable due to all kinds of effects. I don't think it would add fun to the game. 2-body orbital mechanics are complex enough for most players to grasp.