N-body physics

[sarbian]

Just now, sturmhauke said:

Space agencies also have access to supercomputers. Most of us don't, and we aren't running KSP on them anyway.

Supercomputers are not an excuse to use a slow method. They use the same advanced integration techniques because they were developed for them...

[Robdjee]

Perhaps i missed a page in this thread but i believe the following definitively rules out n-body physics.

 

[Superfluous J]

2 hours ago, Arugela said:

Why not do nbody and add more things to make the basic kerbal system work as it does under nbody. Basically, shoehorn it! How about an ort cloud or black holes or things not in the first game that are made to purposely allow it to work well. Then the new systems can be more nbody appropriate in a traditional way.

If your system is unstable adding a bunch of black holes will NOT help.

[Incarnation of Chaos]

I know this has likely been discussed before but wouldn't it just be possible to put the system "On Rails" during extreme timewarps? That way you wouldn't introduce the compounding errors via rounding you would get if they remained N-body during that same time. 

[Guest]

2 hours ago, Incarnation of Chaos said:

I know this has likely been discussed before but wouldn't it just be possible to put the system "On Rails" during extreme timewarps? That way you wouldn't introduce the compounding errors via rounding you would get if they remained N-body during that same time. 

That wouldn’t work either. If your orbit was materially different because of n-body (in a Lagrangian point, or in a binary system for example) then putting it on rails would get it to quickly diverge from that, and who knows what would happen when you came out of warp. If it wasn’t, then what’s the point of n-body in the first place?

I am curious to see how they’ll handle binary systems. It’s not going to be easy to find a system that’s approximately correct and behaves gracefully with time-skip.

Edited October 5, 2019 by Guest

[Incarnation of Chaos]

8 minutes ago, Brikoleur said:

That wouldn’t work either. If your orbit was materially different because of n-body (in a Lagrangian point, or in a binary system for example) then putting it on rails would get it to quickly diverge from that, and who knows what would happen when you came out of warp. If it wasn’t, then what’s the point of n-body in the first place?

I am curious to see how they’ll handle binary systems. It’s not going to be easy to find a system that’s approximately correct and behaves gracefully with time-skip.

Hmmmm, you're correct. The entire point of N-body is making the system accurate to RL; so if you're not replicating the chaotic behavior then you really defeat the point. Also they could just disable it near rask and rusk if they realize it causes issues.

[mcwaffles2003]

12 hours ago, DStaal said:

There are lots of tricky things you can do to help the math, however at the end of the day full N-Body is O(n^n) and recursive and patched conics can *most* of it in O(n).  If the developers wanted to spend the time and effort, they could probably get reasonable speed out of N-Body, for a reasonable amount of ships, by working hard and taking a lot of shortcuts...

Or they could use patched conics and spend that time and effort on other things.

Actually n-body is O(n^2) normally [n*n not n^n]

reference: http://www.cs.hut.fi/~ctl/NBody.pdf

Page 2: "The task of evaluating the function U(x0) for all N particles using (1) requires O(n) operations for each particle, resulting in a total complexity of O(n^2 ). In this paper we will see how this complexity can be reduced to O(n log n) or O(n) by using efficient methods to approximate the sum in the right hand term of (1), while still preserving such important physical properties as energy and momentum."

As stated earlier everyone is only thinking of utilizing euler or runge kutta approximations here, they're all I personally have ever worked on but there are far more sophisticated methods out there for working with good precision while being less taxing

13 hours ago, sarbian said:

This thread is running in circle, answers to those arguments were provided before.

You do not have to calculate each step like that. There are ways of lowering the amounts of steps without loosing precision. Principia uses integrator that are far more complex that an simple Euler and can compute the trajectories for a long time fast. 

N-Body is perfectly doable. It does not means it is a good idea.

"N-Body is perfectly doable. It does not means it is a good idea."

This is the one argument I can really understand as n-body would be difficult for new users to adapt to and understand, narrowing the player base.

That aside, I am hoping that with the approach star theory is developing KSP 2 that adding mods like principia will be easier and possibly be able to work better or present a better UI to help those interested in them to build intuition. My greatest hopes for this game lies in how well mods will be developed for it. Truly, I am hoping someone can implement a special relativity mod so that we may be able to interact with special relativistic phenomenon and build intuition of its workings, similar to how the based game accidentally teaches orbital mechanics and develops intuition for things like angular momentum. To be able to interact with black holes and special relativity would personally bring me a lot of joy.

[Arugela]

I'm hoping they make nbody stock with the option of using it or the existing or similar method. I hate mods. I don't get why it can't just be stock with options for physics and other things.

I don't think it would lower the player base. People want to try things. They just need it done so they can enjoy it.

[GoldForest]

1 hour ago, Arugela said:

I'm hoping they make nbody stock...

I wouldn't hold your breath. Nate Simpson said they tried N-body physics and it didn't work well, so they abandoned it. 

[Delay]

Couldn't you handle a binary system using essentially a two-body solution instead of going full n-body?

The idea is the entire system of KSP 2 runs using the standard, one-body, Keplerian evolution we're used to, except for binaries, which are computed using two body systems. Inside that system, I presume an approximate SOI could be the sum of the masses of both planets/stars, a spacecraft would behave as if it were in an n-body simulation with two planets, that is it is affected by both planets at the same time.

Edited October 5, 2019 by Delay

[sarbian]

On 10/5/2019 at 1:30 AM, sturmhauke said:

Space agencies also have access to supercomputers. Most of us don't, and we aren't running KSP on them anyway.

Oh, I forgot to address this. 

Supercomputers are not magical tools. The CPU of modern  supercomputers are not that different from the CPU of our current PC. Sure they may have a few more instructions for high(er) precision math or specialised task  but each of those CPU are not faster than a consumer CPU. What makes a supercomputer fast is the number of CPU. And that makes them great at solving problems that can be divided in multiple parallel tasks. N-Body is not (AFAIK) that kind of problem since you can have at most 1 thread per object. 

[linuxgurugamer]

22 hours ago, Delay said:

Couldn't you handle a binary system using essentially a two-body solution instead of going full n-body?

The idea is the entire system of KSP 2 runs using the standard, one-body, Keplerian evolution we're used to, except for binaries, which are computed using two body systems. Inside that system, I presume an approximate SOI could be the sum of the masses of both planets/stars, a spacecraft would behave as if it were in an n-body simulation with two planets, that is it is affected by both planets at the same time.

You cant because the influence  each body will have on the spacecraft depends on the distance the spacecraft is from each body

1 hour ago, sarbian said:

Oh, I forgot to address this. 

Supercomputers are not magical tools. The CPU of modern  supercomputers are not that different from the CPU of our current PC. Sure they may have a few more instructions for high(er) precision math or specialised task  but each of those CPU are not faster than a consumer CPU. What makes a supercomputer fast is the number of CPU. And that makes them great at solving problems that can be divided in multiple parallel tasks. N-Body is not (AFAIK) that kind of problem since you can have at most 1 thread per object. 

Ill disagree here.  With clever programming N-Body can be split up into multiple threads.  The basic idea is this:

A master thread is assigned a vehicle. Using an assumption of 5 bodies, the master thread can start 5 more threads, each thread would do all the calculations for one specific body’s interaction with the spacecraft, ending up with a vector of the interaction.  When all the threads are completed, the master thread would then have to add all the results together to arrive with a final vectorto arrive with a single vector.  This will take more time than calculating for a single body, but not N times as long.

[Delay]

3 minutes ago, linuxgurugamer said:

You cant because the influence  each body will have on the spacecraft depends on the distance the spacecraft is from each body

I know that, and the path of the spacecraft would still need to be integrated, rather than being the result of a simple(-r) calculation.

My suggestion was keeping the entire KSP universe a bunch of one-body systems like it is now, and planetary or stellar systems that are supposed to be binary instead run on a restricted three-body problem, where two bodies (the planets/stars) are solved as a two-body system (there are equations for that, no integration needed just yet) and the third body (the spacecraft) follows a path influenced by only these two bodies without exerting any forces itself.

Technically it's still n-body with n = 3, but that would still be a lot faster than taking all planets and stars into account while solving the problem of binary systems in an otherwise patched-conics environment.

[sarbian]

22 minutes ago, linuxgurugamer said:

With clever programming N-Body can be split up into multiple threads.

Which is what I said.

[linuxgurugamer]

39 minutes ago, sarbian said:

Which is what I said.

Really?  I hate to disagree, but this is what I quoted:

3 hours ago, sarbian said:

And that makes them great at solving problems that can be divided in multiple parallel tasks. N-Body is not (AFAIK) that kind of problem since you can have at most 1 thread per object. 

What I was talking about was having N+1 threads per planetary object (the master thread and N child threads, one for each of the N).  For the purposes of the game I would ignore the microgravity that occurs between vessels, it's too small to matter in the game.

[Agustin]

Egg said that they were having plans in working on KSP2.

[sturmhauke]

5 hours ago, linuxgurugamer said:

What I was talking about was having N+1 threads per planetary object (the master thread and N child threads, one for each of the N).  For the purposes of the game I would ignore the microgravity that occurs between vessels, it's too small to matter in the game.

I found a paper on using a distributed supercomputer network for running an n-body simulation on dark matter particles. This is the abstract:

Quote

We report on the performance of our cold-dark matter cosmological N-body simulation which was carried out concurrently using supercomputers across the globe. We ran simulations on 60 to 750 cores distributed over a variety of supercomputers in Amsterdam (the Netherlands, Europe), in Tokyo (Japan, Asia), Edinburgh (UK, Europe) and Espoo (Finland, Europe). Regardless the network latency of 0.32 seconds and the communication over 30.000 km of optical network cable we are able to achieve about 87% of the performance compared to an equal number of cores on a single supercomputer. We argue that using widely distributed supercomputers in order to acquire more compute power is technically feasible, and that the largest obstacle is introduced by local scheduling and reservation policies.

They call it Simulating the Universe Structure formation on Heterogeneous Infrastructures, or SUSHI (yes, really). The PDF goes into more detail. They split the problem space into cells, using one algorithm to solve within a cell (short range) and another algorithm to solve between cells (long range). The cells are stored in a tree structure, parts of which are assigned to each supercomputer. At each step, the supercomputers run the short range calculations, communicate with their neighbors to update the cell boundaries and tree structure and balance the computing load, and then run the long range calculations.

This is quite a bit of overkill for KSP purposes, or probably even planning actual spaceflight missions in the real world. For the Kerbol system, n = 17, not counting asteroids and spacecraft. KSP2 might have an n of a few dozen at most. Our solar system has 150ish relatively large bodies (the Sun, planets, dwarf planets, moons), and while there are possibly millions of smaller objects, they can probably be mostly ignored for the purposes of sending a probe to Jupiter or whatever.

SUSHI, on the other hand, is meant for cosmological scale simulations, and has had its performance analyzed on an n of up to 2³⁹ (8192³, or 549,755,813,888). The overhead is very large, and is not worth it for small data sets like we'd be using here.

[OHara]

8 hours ago, Delay said:

My suggestion was keeping the entire KSP universe a bunch of one-body systems like it is now, and planetary or stellar systems that are supposed to be binary instead run on a restricted three-body problem [emphasis added], where two bodies (the planets/stars) are solved as a two-body system (there are equations for that, no integration needed just yet) and the third body (the spacecraft) follows a path influenced by only these two bodies without exerting any forces itself.

That would be consistent with what Star Theory has said about a 'custom solution' for their binary planets.  By "keeping the universe a bunch of one-body systems" I suppose you mean that all celestial bodies are 'on-rails' Keplerian orbits.  The two planets in a binary system could also move 'on-rails' following their Kepler orbits around their barycenter.  Then within a 'custom solution' SOI centered on that barycenter and enclosing both planets, craft are pulled by gravity from the two individual celestial bodies.

KerikBalm and others discussed this possibility (among many other possibilities) on the first few pages of this thread.

The restricted three-body problem requires numerical integration to find the path of a craft in SOIs with two celestial bodies, which could fit with the numerical integration Start Theory would need to handle craft under thrust during significant time-acceleration (and maybe also craft under thrust when not focused).  The restricted three-body problem is also complex enough to simulate Lagrange points --- all five points for binary systems where one body is heavier enough to create five --- for people who want that.   Systems that are not interesting enough to warrant the 'custom solution' can get a separate SOI around celestial body, so we can have the stable on-rails orbits when N-body physics would be a mere annoyance.