On Newtonian trajectories vs. patched conics

[Kerbart]

See my previous paragraph. Patched conics can be retained for low (and medium) orbits without losing anything interesting, so there need not be any concern about stations in low orbit or communication satellites in Kerbin-synchonous orbit drifting away from where you left them.

Sorry to keep nagging on this, but it's those pesky details that tend to ruin things. How would the transition from patched conics to non-patched take place? What would happen if you draw the line at, say, a 300km orbit, and you're at a 299 km orbit doing a rendez-vous with a vessel in a 301 km orbit? What if due to n-body interaction you actually do get below that threshold? What about highly elliptical orbits that are 1/2 the time underneath the magic altitude and the other half not?

I'm not expecting an answer to these questions, I just want to point out that things are likely not as simple as they seem, and potentially add a lot of unexpected (non-fun) behavior to the game. As somebody who has some experience with building models (albeit it not physical simulations like these), building a model on a hybrid engine based on some arbritary criteria seems to me like opening a Pandora's box of problems.

Numerical stability is not a problem. The trajectories have to be precomputed anyway to show them in map view. Simply store the trajectory (unless the player does something to cause the vessel to accelerate), and in time warp the vessel will follow that trajectory on a rail. The numerical integration should be done with an adaptive time step, where the time step is adjusted to keep the local error below a set limit anyway. Thus the player's use of time warp in the game would impact how much CPU time has to be devoted to computing the trajectories, but should have zero effect on their accuracy.

Ok, I'm really confused at this one. In patched conics, calculating position is basically a matter of plugging your numbers into a function. Y=x*x + 3*x so to say. A bit more complex maybe, but that's really what it comes down to. Which is why they allow stable acceleration at 100,000× warp or even more. Switch to n-body simulation and you don't have that luxury. You'll have to calculate all positions one timestep at a time.

The trajectories have to be precomputed anyway to show them in map view. Yes, that's where your first problems will start. Precomputing a trajectory in mapview will bring mapview to a standstill, as those trajectories have to be computed taking the entire Kerbol system into account. Now, assuming (and I have no clue how this is done, so forgive me for any wrong assumptions) that it takes 6 floats to store a position for an object in a timestep (three floats for the location, and three for the velocity), and let's assume 8 bytes per float (double precision, which is what the accuracy in the save files suggests).

That's 48 bytes per timestep per object. And let's be generous and assume 1s timesteps are good enough. That doesn't sound like a lot, but a transfer to Duna or Eve easily takes 50 days, right? That's 50×24×3600=4.32 million seconds, or 207 MB of data. For the trajectory of one object. And if you make the Kerbal system subject to n-body simulation, that's 16 objects right off the bat or 3.3 GB. And that's 3GB of data that needs to be recalculated every time you touch a node slider.

Thus the player's use of time warp in the game would impact how much CPU time has to be devoted to computing the trajectories, but should have zero effect on their accuracy. The problem is that you don't have the freedom to devote just any amount of CPU time to computing trajectories: you'll max out at 100%. While keeping local errors below a set limit then effectively means "setting a max to time accelleration". Now, we already have a pretty good preview of how that works (for one object at a time) -- it's called physical warp. Which gives you four steps of time acceleration if you're lucky (because on an underpowered machine like mine you don't even get that, as simulation "real time" goes slower than real-world time).

If you want to warp at, say, 100,000× then there's only two ways (and any compromise between the two, of course) of achieving that:

• Make 100,000× as many calculations as compared to no warp
  
• Start taking bigger time steps, introducing inaccuracies
  

I'm not saying these problems cannot be fixed. But at the same time don't lose track of the problem you're trying to fix ("lack of reality" in your universe of small little green men with heads half the size of their body who live on a planet about 50× as dense as earth) and the cost (gameplay, cpu time, unintended side effects) it brings with it.

[Mattasmack]

Sorry to keep nagging on this, but it's those pesky details that tend to ruin things. How would the transition from patched conics to non-patched take place? What would happen if you draw the line at, say, a 300km orbit, and you're at a 299 km orbit doing a rendez-vous with a vessel in a 301 km orbit? What if due to n-body interaction you actually do get below that threshold? What about highly elliptical orbits that are 1/2 the time underneath the magic altitude and the other half not?

I'm not expecting an answer to these questions, I just want to point out that things are likely not as simple as they seem, and potentially add a lot of unexpected (non-fun) behavior to the game. As somebody who has some experience with building models (albeit it not physical simulations like these), building a model on a hybrid engine based on some arbritary criteria seems to me like opening a Pandora's box of problems.

These are good questions. First, I anticipate putting the boundary between Keplerian and Newtonian trajectories higher, say around 5000 km for Kerbin. The idea is that the most commonly-used orbits (LKO or synchronous) would be below the transition altitude so that the situation you describe is not a common one. Second, it would be important to show a marker on the trajectory at the Kepler-Newtonian transition point. The player would need to see when he/she is in a situation where his/her vessel is in a guaranteed stable orbit, or not.

I guess my point is that, as long as the player is informed when an orbit is guaranteed to be stable and when it is not, and as long as the region of Keplerian mechanics is reasonably large, I just don't think the drift of orbits outside of that region is a problem. Yes, any orbit that has any portion of it computed with Newtonian mechanics will drift, to a greater or lesser extent depending on the situation. The trajectories can be precomputed so that what is shown in map view is accurate (see below for more), so plotting a rendevous with another vessel using the information in map view would still work the same way it does now. No nasty surprises for the player (as in, the vessel not going where the map said it would).

Ok, I'm really confused at this one. In patched conics, calculating position is basically a matter of plugging your numbers into a function. Y=x*x + 3*x so to say. A bit more complex maybe, but that's really what it comes down to. Which is why they allow stable acceleration at 100,000× warp or even more. Switch to n-body simulation and you don't have that luxury. You'll have to calculate all positions one timestep at a time.

The trajectories have to be precomputed anyway to show them in map view. Yes, that's where your first problems will start. Precomputing a trajectory in mapview will bring mapview to a standstill, as those trajectories have to be computed taking the entire Kerbol system into account. Now, assuming (and I have no clue how this is done, so forgive me for any wrong assumptions) that it takes 6 floats to store a position for an object in a timestep (three floats for the location, and three for the velocity), and let's assume 8 bytes per float (double precision, which is what the accuracy in the save files suggests).

That's 48 bytes per timestep per object. And let's be generous and assume 1s timesteps are good enough. That doesn't sound like a lot, but a transfer to Duna or Eve easily takes 50 days, right? That's 50×24×3600=4.32 million seconds, or 207 MB of data. For the trajectory of one object. And if you make the Kerbal system subject to n-body simulation, that's 16 objects right off the bat or 3.3 GB. And that's 3GB of data that needs to be recalculated every time you touch a node slider.

You are rather significantly overestimating the computational effort and storage required. By avoiding integrating low orbits and by using a moderate-order integration scheme, the time steps can be much larger. Using a 5th order Runge Kutta method, I found that time steps were between ~100s (for vessels just outside of where I would put the Newtonian-Keplerian transition above Kerbin) to millions and tens of millions of seconds for vessels in interplanetary space. Typically a few hundred to just over a thousand time steps are needed to compute a full orbit. These time steps are of course much larger than the time between frames, so intepolation can be used to accurately and quickly obtain a vessel's state at any point within a time step. Storing 1000 time steps with interpolation data requires about 200 kB. And (once again) it's not an n-body simulation -- the planetary bodies stay on their Keplerian trajectories, which also allows the time step used to integrate each vessel's trajectory to be independent of all the others'.

I realize it's very long-winded, but the article on my website (link in the original post) has many of these details about the computational effort required, magnitude of numerical inaccuracy, etc.. I am not just spouting off an idea, I did some homework first to check the feasibility of as many aspects of the idea as I could think of.

Thus the player's use of time warp in the game would impact how much CPU time has to be devoted to computing the trajectories, but should have zero effect on their accuracy. The problem is that you don't have the freedom to devote just any amount of CPU time to computing trajectories: you'll max out at 100%. While keeping local errors below a set limit then effectively means "setting a max to time accelleration". Now, we already have a pretty good preview of how that works (for one object at a time) -- it's called physical warp. Which gives you four steps of time acceleration if you're lucky (because on an underpowered machine like mine you don't even get that, as simulation "real time" goes slower than real-world time).

If you want to warp at, say, 100,000× then there's only two ways (and any compromise between the two, of course) of achieving that:

• Make 100,000× as many calculations as compared to no warp
  
• Start taking bigger time steps, introducing inaccuracies
  

I'm not saying these problems cannot be fixed. But at the same time don't lose track of the problem you're trying to fix ("lack of reality" in your universe of small little green men with heads half the size of their body who live on a planet about 50× as dense as earth) and the cost (gameplay, cpu time, unintended side effects) it brings with it.

Your overall point is valid; the computational effort of integrating Newtonian trajectories will indeed put a cap on time warp. But I don't think physics warp gives any sort of useful yardstick -- its speed limitation is part-to-part physics, which is a whole 'nother kettle of fish.

In my simulations, I found that I could compute 60,000 - 75,000 steps per second if I used precomputed interpolation functions for the planetary body locations (computing their locations from their Keplerian orbital elements was very costly, I think because of the several trig function calls required). This was for a thread running by itself on one core on my laptop, but with different levels of load on the other cores of the CPU (which accounts for the range 60k-75k). This isn't equivalent to running the simulations within KSP, but I believe it gives a rough estimate of what could be accomplished. In any case, taking the worst case of 100 s timesteps and assuming 50k steps calculated per second, the trajectories of fifty objects could be integrated at 100,000x time warp. And yes, any more than that would result in the time warp slowing down.

I am sympathetic to your final point; realism for the sake of realism probably isn't a good enough reason to implement something like this. I undertook my little study because I had seen a number of conversations about why it couldn't be done, but the reasons were usually given without justification and I wanted to see what the technical hurdles really were. I'm interested in trying it in a mod because I'm curious to see what it looks like in-game -- I think it will be interesting.

[Mattasmack]

If something like this were implemented, I think a 'stationkeeping' button would make sense to toggle patched conics/newtonian physics. For a number of reasons, it might also make sense to only enable newtonian physics on the active vessel.

Such a system would allow an interested player to toy with manuevers in newtonian physics than then toggle to patched conics when we just want something to stay put. This also means we wouldn't need to draw arbitrary boundaries between patched conic and newtonian space.

Of course, this system could easily be exploited to perform 'cheat' maneuvers in which, by toggling physics modes, could be exploited for infinite delta-v. But that's the player's issue (and it would probably make for a fun way to burn a few afternoons). Heck, you can still infiniglide, so it's not even without precedent.

I do like this idea as a simple in-game (non-immersion-breaking) way to avoid all the complexities of Newtonian trajectories (or to stabilize an orbit that shouldn't really be stable) if the player wants to. You're right, I'm sure it would be exploitable, but it's not really a problem.

Quick idea to cut down on processing power. I'm not a genius when it comes to programming and backend wizardry, so forgive me if I'm making a really stupid suggestion. What if you kept the planets and non-focused ships on rails, and only ran newtonian calculations on the ship you have focused?

Celestial bodies really need to be on rails. If not, sooner or later something will go horribly amiss and the Kerbol system will find itself short a few moons. Plus, the effect of ships on these bodies is completely negligible.

Yeah, celestial bodies can just stay on the Keplerian rails they're on now. That's what I've been looking at so far. I'm ignoring gravitational interaction between the vessels themselves, too. In short, it's not an n-body simulation. That makes it possible to calculate each object's trajectory independently of all the others'.

TS has told me that he actually run full n-body simulation for the whole system, and all celestials were OK, except for Jool's moons. Looks like it was made artificially unstable. I wonder what would it take to stabilize them.

But let's not get ahead of ourselves and do vessels-only sim first and see what happens. So far results are encouraging.

I was just playing around with that the other day, and I'm waiting for some figures to render so I can show it on Youtube. For a time span of about 100 years (Earth years, not Kerbin years -- 3x10⁹ s) the planets' orbits are stable, but Jool loses two moons. Jool loses them so quickly, I think the only way to stabilize them would be to disable the gravitational interaction between some (or all) of Jool's moons. The other moons seem OK, although some of their orbits wobble a bit (especially Gilly). All this is orthogonal to the topic of this thread; it's just something I did for fun and because I had most of the code written already.

Only possibility for such thing if there any is by mod. SQUAD is, well, they will not make it . So it's better to just begin to make it, as Ferram did, or just to forget. Rather then arguing and reply to the same repetive nonsence there(iunless it is the aim of it, but OP looks like serious guy whow know things).

Yeah, trying to implement it in a mod is my intention. But this thread has been worthwhile; the feedback has been helpful in refining what any scheme using Newtonian mechanics should (and should not) do, I've gotten some good ideas out of it, and I've gotten in contact with people who are also interested in making it happen. (Also, I spent some of today helping relatives carry water-damaged stuff out of their basement (they live in Boulder, Colorado, which just got a freakishly large amount of rainfall; many homes there were flooded), and I can't think well enough to program but I can still write forum posts!)

[DAVIDESCOTT]

I do like this idea as a simple in-game (non-immersion-breaking) way to avoid all the complexities of Newtonian trajectories (or to stabilize an orbit that shouldn't really be stable) if the player wants to. You're right, I'm sure it would be exploitable, but it's not really a problem.

One way to break the exploitability of station-keeping would be to charge the ship a certain amount of RCS for station keeping. I think it would make for an interesting addition to include that charge everywhere (including within the Keplerian low orbit region). I was thinking of making a mod which every night iterated over all the ships and charged them a delta-v based on their average orbital altitude. The function would be something like alpha/(70-altitude) + beta*ln (altitude) to very roughly model the aerodynamic drag and the newtonian effects. If a ship (or debris) had no RCS I would adjust the orbit slightly to model that delta-v loss.

[csanders]

Hey, I just found an upgrade to give n-body calculations in a solar system identical to our own: http://orbit.medphys.ucl.ac.uk/

[NeilC]

When in orbit, your craft is constantly under acceleration, gravity. I can't confirm it but I'm pretty sure it's stuck in the same thread. Else n-body physics wouldn't be such an hassle to add to the game.

I think this is a misconception. It's important to realize that there are two different systems at place here:

1) The active craft and anything within a certain radius of it have their position/acceleration and all other properties calculated, on a part-by-part basis, using Unity's RigidBody system. This uses PhysX under the hood. It is limited to one thread and the code is not maintained by the KSP devs.

2) All non-active crafts or celestial bodies have their trajectories calculated by KSP's "on rails" Keplerian solver. This code is maintained by the devs, and they could do whatever multithreading they wanted to it.

If Mattasmack is proposing adding additional gravity forces from other bodies to the active craft only, this would be totally trivial - just add up all the grav forces at the current timestep and supply it to Unity as the built-in gravity vector, just like it's currently done. But in this case it's pointless to discuss alternate integration methods, adaptive timesteps, or anything else - you're gonna get Unity's implementation because it would be a crapton of work for the devs to build that whole system again.

But I think the OP is proposing substituting the on-rails solver for a better, quasi-N-body one. Which would be cool, and is possible (if difficult, lengthy and bug-inducing) for KSP to develop as it controls the code already.

What I don't understand, Mattasmack, after reading your more detailed website post (which was a great read by the way, kudos on some very detailed an well-presented work!) is how you can say:

For a time step of 10 s and 50k steps calculated per second, only five trajectories could be calculated at a timewarp of 100,000x. For a time step of 100 s, fifty objects could be tracked at that speed.

and then follow that up with

I believe any computer capable of running KSP could also calculate an acceptably large number of trajectories at 100,000x warp.

A practical limit of 10-50 craft in the game? I don't think that's very reasonable, especially since that limit is dependent on where those craft are orbiting. Remember that while you may not have the fastest i7, KSP still needs to run acceptably on Core2Duo-class laptops at lower clockspeeds. Your assumptions aren't particularly conservative for that case.

I'm also confused as to how you would implement your variable-timestep approach when the game is not running at 100,000x warp. 10-100s between position updates? That's a mighty low framerate!

How would you interpolate? Or would you just force an update at the current timestep, regardless of the optimum?

I'm very impressed by your rigorous comparison of integration methods and error analysis. However, I think you're a bit hand-wavey on the performance aspect. Because this approach was rejected by the KSP devs based on performance concerns, I suggest that addressing those concerns is where you should be focusing the lion's share of your effort.

Edited September 24, 2013 by NeilC

[Kasuha]

The main problem with full n-body simulation is maneuver planner. Here you don't need to calculate just one step for several orbiting bodies. You need to calculate all steps, many years into the future for all crafts (you need to calculate ship trajectory intersections/distances too) many times a second.

Or you just have to drop the planner.

[DAVIDESCOTT]

A practical limit of 10-50 craft in the game? I don't think that's very reasonable, especially since that limit is dependent on where those craft are orbiting. Remember that while you may not have the fastest i7, KSP still needs to run acceptably on Core2Duo-class laptops at lower clockspeeds. Your assumptions aren't particularly conservative for that case.

10-50 Newtonian craft. I think his proposal has most craft (inside KEO orbit) following Keplerian trajectories. Managing 10-50 craft on extraplanetary missions would seem reasonable. It would also be possible to forward compute some of these paths years into the future with idle CPU time and save them on the assumption that you aren't going to be messing with that communications relay at L4 anytime soon.

Also a comment on his L-point analysis. On a reddit thread someone suggested that the issue with L-points in this system is solved by doing a small adjustment. Instead of treating the area outside the Keplerian SOI of Kerbin as no-man's land continue to think of it as Kerbin's SOI, but apply a modified N-body integration. Compute the N-body acceleration for Kerbin wrt the Mun and Kerbol and compare that to the actual orbit of Kerbin. That difference is a correction vector that you would apply to the computed N-body acceleration of the vessel. Doing so reportedly gets you better behaved L-points.

[Vector]

I'm late to the conversation and most things have been said already, so I'll speak in terms of two gameplay elements:

1. The discontinuity at the SOI boundaries sometimes bothers me, most often because KSP is sometimes flaky about predicting whether I will intercept the SOI or not. The discontinuity means it matters a great deal whether I touch the SOI or not.

2. And this is tangentially related but has to do with rails vs. physics is that from a practical standpoint it would be really nice to be able to use ion engines with high time warp. If one were to ditch the patched conics for a model that uses numerous time-varying sources of acceleration, it would seem less of a big deal to allow an additional acceleration source. This would open up a whole new class of possible missions using ion engines that are currently infeasible.

Also, I did a thought experiment on your Lagrange points, and I think L4 and L5 do not exist because Kerbol does not orbit the mutual center of mass, as you suggested. Under real-life conditions, when the Sun orbits the center of mass, then when you look at the two components of Solar gravity and centrifugal force in a rotating frame, it's shaped like a ring that is slightly higher on one side. The Earth then punches a hole on the high side of the ring, leaving the two remaining peaks. In contrast, since Kerbol is concentric with the rotating frame, the ring would have exactly the same potential all the way around, and when Kerbin punches a hole, it would not leave adjacent high points. However, following this logic, the L3 point should be stable instead of unstable as in real life. I would be interested to see if your model would produce a stable orbit around L3.

[Tsuki]

I will probably get yelled at for thread necroing, but really noticed it only now and im very fascinated to how far you actually taken this proof of concept, at least mathematically and computation wise.

Sadly I am almost certain that squad will never implement this (won't go into ranting ), however maybe the idea to make it a mod is not that farfetched. IMO if there is still interest from

asmi and Mattasmack I might try to research the possibility how to replace the default conic simulation, if there is any. Since i think this might be the biggest problem of it.

I would so much love to see this model in KSP the patched conic orbits are soooo boooring.....

Also some people concerns about "game is hard as it is for newbies" IMO it was already nicely explained how it wouldn't affect them by much, inside new SOI(where orbits are calculated by conic patches) there would be no difference than it is now, as for the space outside sois... how many newbies would need stable out of SOI orbits -.- (you would not put your first station @ 5000km for god sake)