[WIP][1.8.1, 1.9.1, 1.10.1, 1.11.0–2, 1.12.2–5] Principia—version ‎‎Kronecker, released 2024-11-01—n-Body and Extended Body Gravitation

[Garek]

1. mixed-mode C++/CLI does not conform to CLR specification and as such it is not given that it would work under Unity - I haven't actually tried that and was focusing on optimizing algorithm performance.

2. Unity is cross-platform and runs on MacOS and Linux. Again I'm not sure that mixed-mode would actually work on these platforms.

It's been a while since I last looked at mixed mode C++/CLI, but at the time it was only implemented by Visual Studio/Microsoft .NET. I don't now if any other CLR implementation supports it yet. Also, mixed mode C++/CLI has all the pitfalls of native C++ concerning cross-platform. You would have to provide separate binaries for each platform, also separate for 32 and 64-Bit, and make sure they all work properly. Actually, since everything is x86-based now, you could maybe get away with one binary for 32 and 64Bit each, IF Unity uses the same CLR implementation on every platform and you don't call any native library function.

EDIT: timmers, you're right, he doesn't have to support every platform. But it would be nice, and if he implements it now for a specific platform, and later decides to support more (mod popularity?), that would get really messy.

Edited February 5, 2014 by Garek

[Z-Man]

Yes. For fine timesteps, this actually is easier than propagating them on their Keplerian rails, because solving the Kepler equation (which involves a few iterations of Newton's method; the derivative of Kepler's function has a trigonometric function, which is a few hundred clock cycles compared with 10 or so for a division/square root) is pretty slow.

I see. Cool! I use Keplerian orbits with perturbations, so large timesteps are less of a problem (and possible).

It should be noted that even if you want to keep things in 2-body orbits, it is a good idea to really use the solution of the 2-body problem (2 bodies orbiting a barycenter) rather than the pretty poor Keplerian approximation (one body orbiting another).

Of course. My ideal goal would be, however, to keep as many parameters as possible equal to stock: Distance of Kerbin to the Mun, orbit period of the Mun (so launch windows stay; not really an issue with the Mun, but for interplanetary transfers), masses in sizes of bodies (so the difficulty stays the same and existing orbits in savegames still work). Which... is not possible. Thinking about it now, well, the distances shall be adapted.

[eggrobin]

Concerns about x87 being slower than SSE2 due to manipulating scalars

I'll have to experiment, but I'm not sure I will need that much of a speedup (going from CLR to native will already be nice). On the other hand, I'm not sure I need extended precision either (I certainly don't for stock, but it might be nice in RSS).

Concerns about interfacing with unmanaged code through C++/CLI

I hope it will work, otherwise I can just import the DLL myself and take care of the marshalling and other interesting details. That's quite tedious though.

Concerns about having lots of binaries

I'll worry about that (as well as the two issues above) when I get to using C++ anyway. I'll first get most of it working in C# and see how that goes, premature optimisation is the mother of all sins.

Of course. My ideal goal would be, however, to keep as many parameters as possible equal to stock: Distance of Kerbin to the Mun, orbit period of the Mun (so launch windows stay; not really an issue with the Mun, but for interplanetary transfers), masses in sizes of bodies (so the difficulty stays the same and existing orbits in savegames still work). Which... is not possible. Thinking about it now, well, the distances shall be adapted.

If Scott Manley's intuition proves right, things should be pretty stable (and thus stockalike) under N-body physics if you just interpret the stock orbital parameters as parameters of the orbits around the barycenter of the primary's system. I'll find out when I try to stabilise Vall.

[Porkjet]

Moddersâ„¢ - making things possible since 1961

Amazing! If you make this work, it will take KSP to a whole new level!

[timmers_uk]

It's been a while since I last looked at mixed mode C++/CLI, but at the time it was only implemented by Visual Studio/Microsoft .NET. I don't now if any other CLR implementation supports it yet. Also, mixed mode C++/CLI has all the pitfalls of native C++ concerning cross-platform. You would have to provide separate binaries for each platform, also separate for 32 and 64-Bit, and make sure they all work properly. Actually, since everything is x86-based now, you could maybe get away with one binary for 32 and 64Bit each, IF Unity uses the same CLR implementation on every platform and you don't call any native library function.

EDIT: timmers, you're right, he doesn't have to support every platform. But it would be nice, and if he implements it now for a specific platform, and later decides to support more (mod popularity?), that would get really messy.

Agree 100%, but it'd be a pity if he got bogged down in the overhead of cross-platform support and having to go least common denominator (esp as it entails having access to linux mac and windows dev machines to build/test) ... if that's a problem perhaps someone else could help out with the ports

Oh, and I'd love to see this whole shizzle happen (though I have enough problems with comm sat corralling as it is and would need something to help me herd the little straying dudes).

Edited February 5, 2014 by timmers_uk

[rhoark]

Someone did an n-body simulation of the kerbol system awhile back

If a Joolian moon or two does strange things, I'd consider that a feature, though perhaps it could be placed in such a way to encourage it to become a Trojan.

Edited February 5, 2014 by rhoark

[thorfinn]

Wonderful. I'll watch this space carefully. Just wanted to add that having the new integrator even without N-body would be great: things like realistic nuclear-electric propulsion and more intelligent trajectory planning would be invaluable even in the 2-body approximation.

All in all, this will make flight quite a bit more difficult (we will really need a "charting table" more powerful than the current maneuver nodes to get around) but making realistic bi(tri/quater)nary star systems possible would be enough of a payoff? I'm leaning towards a "yes"

Edited February 5, 2014 by thorfinn

[lyndonguitar]

Wtf wowowowowowowowowowowow... Wow

[Itsdavyjones]

Looking forward to seeing this, looks fun.

*N-body sim link*

Well there goes the Joolian system as we know it.

[eggrobin]

Oh, and I'd love to see this whole shizzle happen (though I have enough problems with comm sat corralling as it is and would need something to help me herd the little straying dudes).

The ability to look at orbits in rotating reference frames might actually make commsat management easier.

Someone did an n-body simulation of the kerbol system awhile back

If a Joolian moon or two does strange things, I'd consider that a feature, though perhaps it could be placed in such a way to encourage it to become a Trojan.

Yes, the same Matt Roesle (Mattasmack) also did a simulation of the Alternis system (he's mentioned in the 'acknowledgements' section).

Scott Manley remarked that the system might be much more stable if the orbital parameters were read as barycentric, rather than Jool-centric. Experiments will be carried out in due time.

Wonderful. I'll watch this space carefully. Just wanted to add that having the new integrator even without N-body would be great: things like realistic nuclear-electric propulsion and more intelligent trajectory planning would be invaluable even in the 2-body approximation.

Or better numerical stability. The current 'look at your free return trajectory; now look at the SOI change; your free return trajectory is now a Mun collision' behaviour is irritating, as is the numerical wobbling of orbits when out of timewarp. This game really needs decent integrators, independently from the N-body problem.

All in all, this will make flight quite a bit more difficult (we will really need a "charting table" more powerful than the current maneuver nodes to get around) but making realistic bi(tri/quater)nary star systems possible would be enough of a payoff? I'm leaning towards a "yes"

The thing is, once you get used to how they work, 2-body orbital mechanics are pretty simple. This will hopefully provide an interesting challenge and new possibilities, while not fundamentally changing most of the game.

Edited February 5, 2014 by eggrobin

[czokletmuss]

Amazing. I will be following this thread closely!

[NathanKell]

This is great stuff eggrobin! And I'm not just saying that because it has an Abstract and a Bibliography.

Let me know if I can help with anything!

[eggrobin]

This is great stuff eggrobin! And I'm not just saying that because it has an Abstract and a Bibliography.

The acronym expansions are nice too.

Let me know if I can help with anything!

That's what the 'Open questions for the interested reader' are for. If you want I can notify you when new questions come up.

[Tsevion]

Speed will be further increased by rewriting the numerical integration in (unmanaged) C++, interfaced with C# through C++/CLI. The unmanaged C++ (compiled with clang) will use 80-bit extended precision 'long double' (64-bit mantissa instead of 53-bit) for added precision.

While this is not a bad idea, as unmanaged C++ can be considerably faster, care must be taken here.

You need to keep the number of managed/unmanaged boundary crossings (thunks) as low as possible. Ideally, you'll want a single call: FigureOutEverythingForThisTimespan. Crossing the boundary incurs a not insignificant perf hit (depending on setup and amount of data being marshaled, I've measured it between 0.1μs and 100μs). This is generally ignorable if you're doing a few dozen calls a frame, however if you start doing 1000 or more calls a frame, it can become significant and even dominant in your timing, eating all the perf gains you're getting from using unmanaged.

Edited February 6, 2014 by Tsevion

[eggrobin]

Ideally, you'll want a single call: FigureOutEverythingForThisTimespan.

This is what I intend to go for: most of the code in unmanaged C++, interacting with the C# part once per FixedUpdate (get the new positions/velocities etc., send an update for thrusts &c.). I'll have to see what integration out of timewarp ends up looking like, but I won't have more than a few thunks per FixedUpdate (the only way 1000 thunks per update could happen is if I computed the increments in the unmanaged part, but accumulated them in the managed part; this would just be insane from a conceptual standpoint, besides the performance costs).

[ferram4]

Some more thoughts:

Would drawing the gravitational potential in the current orbital plane (together with the centrifugal potential if orbits are drawn is a rotating reference frame) be useful?

Well, if you do something like this graph, or something based on it but with colored contours I think it would be very helpful for figuring out what is going on if it can be toggled on and off. I think that the best way to do that would be to draw it in the plane of the orbit only (to reduce confusion), and allowing the player to select which body to base the plane on as an advanced option. By default, set it to handle the "dominant" bodies in the situation, so by default around Kerbin it would work in the plane of Kerbin and the Mun, until the player gets closer to Minmus and Minmus' influence outweighs the Mun's. In a situation like the inner Joolian moons it should attempt to draw in some type of "local ecliptic" plane that attempts to do a mass average of the bodies involved to find the proper plane, but only do that once.

I'm not sure how you would handle the rotational potential for the Joolian moons, probably base it on the most massive body?

Whatever is done, if it's possible to mark the edges of a body's Hill Sphere that should be done to make the effects as clear as possible. We'll need that to be the new SOI type of effect.

Should long-term trajectory predictions for vessels under thrust be inaccurate, is there a good way of estimating the uncertainty (for instance, would predicting a few perturbed trajectories and plotting them all give a representative idea of what might happen)?

I have an idea here: once you start something under thrust, show the current trajectory (time t), the last calculated trajectory (time t-ÃŽâ€t), and the estimated trajectory based on the craft's instantaneous acceleration a slight bit in the future (time t + ÃŽâ€t). Make the last one a little less accurate than the others, since you'll throw it away; store the current trajectory and shift it over to the last calculated every time you recalculate things forward. Your ghost past and future trajectories now show the approximate error that will occur due to the player making a fraction-of-a-second error in the burn time. My only concern is that the less accurate future calculation might add a bit to the computational overhead, in which case you can simply use the old trajectory. Seems simple enough, especially if fainter colors are used for the ghost trajectories.

[Tsevion]

(the only way 1000 thunks per update could happen is if I computed the increments in the unmanaged part, but accumulated them in the managed part; this would just be insane from a conceptual standpoint, besides the performance costs).

You have no idea how much interop code I've seen written where people do things like this. Good to see you're in the right frame of mind on this... I tend to assume people will do something insane and idiotic until proven otherwise. If you need any help with interop, I've done quite a bit of it over the years (All on Windows though, so no clue on the Mono/Linux/Mac fronts): P/Invoke, COM, C++/CLI, using downright evil hooks to inject code from an outside process... so feel free to ask about any specifics you run into.

[eggrobin]

Well, if you do something like this graph, or something based on it but with colored contours I think it would be very helpful for figuring out what is going on if it can be toggled on and off. I think that the best way to do that would be to draw it in the plane of the orbit only (to reduce confusion), and allowing the player to select which body to base the plane on as an advanced option. By default, set it to handle the "dominant" bodies in the situation, so by default around Kerbin it would work in the plane of Kerbin and the Mun, until the player gets closer to Minmus and Minmus' influence outweighs the Mun's. In a situation like the inner Joolian moons it should attempt to draw in some type of "local ecliptic" plane that attempts to do a mass average of the bodies involved to find the proper plane, but only do that once.

That's what I was thinking about. Contours should be fairly trivial, I was wondering whether a mesh would be more readable though (it wouldn't be much harder, but some care would have to be taken in order to make the reference plane readable).

Regarding the choice of plane, how about the Keplerian orbital plane? That makes things usable for inclined orbits, and it will pretty much do what you want in the CR3BP (I guess there will always be some edge cases, but if things work well in both the 2-body limit and the CR3BP I'll be happy for now).

I'm not sure how you would handle the rotational potential for the Joolian moons, probably base it on the most massive body?

The centrifugal potential is arises from the choice of a rotating reference frame, it's not a property of the system. So that's pretty easy, I'll just add the centrifugal potential for whatever reference frame I'm drawing the orbits in.

Whatever is done, if it's possible to mark the edges of a body's Hill Sphere that should be done to make the effects as clear as possible. We'll need that to be the new SOI type of effect.

If I draw the potential, you'll get something more useful than the Hill sphere (and you'll see something that looks like the Hill sphere as one of the contours).

I have an idea here: once you start something under thrust, show the current trajectory (time t), the last calculated trajectory (time t-ÃŽâ€t), and the estimated trajectory based on the craft's instantaneous acceleration a slight bit in the future (time t + ÃŽâ€t). Make the last one a little less accurate than the others, since you'll throw it away; store the current trajectory and shift it over to the last calculated every time you recalculate things forward. Your ghost past and future trajectories now show the approximate error that will occur due to the player making a fraction-of-a-second error in the burn time. My only concern is that the less accurate future calculation might add a bit to the computational overhead, in which case you can simply use the old trajectory. Seems simple enough, especially if fainter colors are used for the ghost trajectories.

This sounds like a very good idea, it would help with visualising complicated transfers. It would only double the performance cost of dynamic integration, so that should not be too much of a problem.

You have no idea how much interop code I've seen written where people do things like this. Good to see you're in the right frame of mind on this... I tend to assume people will do something insane and idiotic until proven otherwise.

This is sadly a fairly good assumption in general.

If you need any help with interop, I've done quite a bit of it over the years (All on Windows though, so no clue on the Mono/Linux/Mac fronts): P/Invoke, COM, C++/CLI, using downright evil hooks to inject code from an outside process... so feel free to ask about any specifics you run into.

I won't refrain from expanding the list of open questions as new ones come up.

[ferram4]

That's what I was thinking about. Contours should be fairly trivial, I was wondering whether a mesh would be more readable though (it wouldn't be much harder, but some care would have to be taken in order to make the reference plane readable).

I'd be afraid of the mesh being difficult to read due to the fact that we're dealing with 3D visualizations, which might make the location of particular dips and rises difficult to pinpoint. Contours could be projected onto a plane, removing that issue completely.

Regarding the choice of plane, how about the Keplerian orbital plane? That makes things usable for inclined orbits, and it will pretty much do what you want in the CR3BP (I guess there will always be some edge cases, but if things work well in both the 2-body limit and the CR3BP I'll be happy for now).

Yeah, guess I'm kinda over-complicating things. Fortunately, no one has a system that includes lots of bodies close together with high relative inclinations.

If I draw the potential, you'll get something more useful than the Hill sphere (and you'll see something that looks like the Hill sphere as one of the contours).

I mean as a subtle kind of highlighting or darkening of the contour. Not enough for it to jump out and scream "THIS IS A HILL SPHERE," but enough that it grabs the player's eye, marking it as important, even if it's only subconsciously. Subtleties can go a long way towards making things clearer with no one even realizing that it's there.

[Faark]

No code available yet to peek into?

And just to save you some googling time in case you don't already know (since i had to deal with it recently): 2010 and newer version of Visual Studio do not support targeting .net frameworks below 4.0 for c++/cli assemblies, so you might want to use the vs2008/v90 platform toolset.

Edited February 6, 2014 by Faark

[eggrobin]

No code available yet to peek into?

Expect a slow development cycle, due to a combination of laziness, exams, and this actually being a complicated project.

I'll put the source on GitHub as soon as I can clean things up a bit (there are quite a few traces that were too hastily implemented for my taste). This might take a few days, see above.

The 'exams' thing will last until 2014-02-14 (only to come back in six months, and be replaced by 'studying' in the meantime). The other two reasons are here to stay.

And just to save you some googling time in case you don't already know (since i had to deal with it recently): 2010 and newer version of Visual Studio do not support targeting .net frameworks below 4.0 for c++/cli assemblies, so you might want to use the vs2008/v90 platform toolset.

Why would I want to target .NET Framework assemblies below 4.0? I will only be using the C++/CLI part for easier interfacing with the unmanaged C++ part (probably compiled with clang due to clang's interpretation of long double). Anyway, I'm not downgrading this project to VS2008 (though I have it somewhere), bad things would be likely to happen. I'd rather do the marshaling myself if the C++/CLI scheme doesn't work out.

Rewriting stuff in C++ is not my first priority at the moment though; a tremendous speedup will already come from using a better integrator.

The expected order of development can be seen in the 'further modding' section (though neat visualisations, such as drawing gravitational potentials, are fun to write and make for great screenshots, so I might implement those sooner than I should).

One of my first tasks will therefore be to find out a way to grab the acceleration of the vessel (not due to gravity) and plug that in my integrator.

Edited February 6, 2014 by eggrobin

[asmi]

No code available yet to peek into?

And just to save you some googling time in case you don't already know (since i had to deal with it recently): 2010 and newer version of Visual Studio do not support targeting .net frameworks below 4.0 for c++/cli assemblies, so you might want to use the vs2008/v90 platform toolset.

That is not true. I use vs2012 for my mod projects without any issues.

[timmers_uk]

Why would I want to target .NET Framework assemblies below 4.0? I will only be using the C++/CLI part for easier interfacing with the unmanaged C++ part (probably compiled with clang due to clang's interpretation of long double). Anyway, I'm not downgrading this project to VS2008 (though I have it somewhere), bad things would be likely to happen. I'd rather do the marshaling myself if the C++/CLI scheme doesn't work out.

I think the comment is because the Mono ontop of which Unity's built, on top of which KSP is built (why am I now imagining a very wobbly pile of wobbly things) ... is equivalent to .net 3.5 assemblies - ISTR I got bitten by that but only once I started including reflection code or something - quite possibly you'll get similar issues in the managed/unmanaged boundary if your building to 4.0+ dlls and then try to use them with KSP?

edit to add : @asmi - I think the problem may come with vs2010+ when you mix C++ and C# in your assembly and then try to target .net 3.5

[asmi]

I have an idea here: once you start something under thrust, show the current trajectory (time t), the last calculated trajectory (time t-ÃŽâ€t), and the estimated trajectory based on the craft's instantaneous acceleration a slight bit in the future (time t + ÃŽâ€t). Make the last one a little less accurate than the others, since you'll throw it away; store the current trajectory and shift it over to the last calculated every time you recalculate things forward. Your ghost past and future trajectories now show the approximate error that will occur due to the player making a fraction-of-a-second error in the burn time. My only concern is that the less accurate future calculation might add a bit to the computational overhead, in which case you can simply use the old trajectory. Seems simple enough, especially if fainter colors are used for the ghost trajectories.

That might not work for performance reasons. The best I've managed to get 100k steps of RK5(4) executed is in about 1 second if my memory serves me - that it's on powerful i7 3930K CPU with significant portions of code written manually on SSE2/3 intrinsics (=assembly).

And in your case it will have to be done in addition to regular updates calculations. You could probably run it for t and (t+dt) in parallel on separate cores if you write the code carefully not to use any shared state, but experience with my mod (which is heavily parallel and extensively uses all available cores) indicates that there are enough users here with relatively weak 2-core or even 1-core CPUs.

[Faark]

That is not true. I use vs2012 for my mod projects without any issues.

Well, its an official statement from MS regarding cli/c++ assemblies on vs2010+ that target <net4, so you might want to check out your assembly in ILSpy or sth similar. You will most likely find a "Runtime: .NET 4.0" and reference of mscorlib and System.dll to both version 2.0 and 4.0, like this:

Ofc that might not be a problem and Unity-Mono simply ignores those references to non-existent librarys... until you accidentally use any feature that requires .NET 4.0 and you just don't get whats wrong, especially since it compiles just fine. Thats the same reason we frequently tell newer modders to target a framework lower than 4.0 that is more compatible with Ksp's Unity-Mono.

I found about about those CLI/C++ limitation when i tried to use my library in a C# project that properly targeted a pure .NET 2 runtime. But hey, if it works for you, no one will force you to change anything. And in case you experience "crazy" issues you now know an additional possible source.