Can we fix the problem of time warping through planets?

[JonnyOThan]

When on a collision or aerobraking trajectory, it’s pretty easy to warp through a point where rails warp should have been disabled. Can we do anything about this? It shouldn’t be difficult to calculate a point on your orbit where you shouldn’t warp past.

[gotmachine]

shouldn’t be difficult

Famous last words :P

To describe the full problem, what is needed is a way to detect if a point moving along an arbitrary 3D ellipse is intersecting a sphere moving along another arbitrary ellipse between a time interval, where those two objects have an arbitrary and non linear velocity over time.

I don't think even the most cutting edge CCD stuff out there is capable of this, AFAIK they assume linear velocity between time steps, at best they account for angular velocity too. Maybe a 3D ellipse / ellipse analytical intersection test algorithm is possible, but that would likely be quite complex.

But lets simplify the problem a bit. Assume the vessel and bodies are moving in a straight line : the problem is now a relatively simple ray / capsule intersection check, which can be done by decomposing the check into two ray/sphere intersections and a ray/cylinder intersection.

But you have to consider that at the timesteps of the highest timewarp rates, a vessel or a body can move by a significant portion of a full orbit revolution, and in many cases, by more than a full revolution. If you just take the position of the vessel and of the body at the current fixed frame and at the next fixed frame to generate your ray and capsule respectively, that will generate garbage results.

To have the ray and capsule be an acceptable representation of the elliptical trajectories, you need to decompose the time step into smaller ones where both orbits curvature between the start and end times is small enough, said otherwise, where the angle between the normalized velocity vectors at times t and t+n is small enough. There are probably smart ways to find those points, but a naive bisection is gonna take a lot of iterations.

So, to summarize :

• For each vessel
• Discretize the next fixed time step into smaller steps approximating the orbit ellipse section into lines of acceptable error.
• For each body that it can potentially collide with
• Discretize its trajectory too
• For every vessel and body time pair, get their position and perform a ray/capsule intersection check.

Obviously, this would be quite computationally expensive, and definitely not compatible with decent frame rates if done naively using the KSP orbit stuff. There are maybe a few smart ways to early out of the full check and to make it faster, but I wouldn't qualify any of this as "not difficult".

Edit :
Ok, actually, stock does all of this already to find where an orbit patch encounter a SOI edge, which is a basically an arbitrary radius centered on a body. So it should be possible to adapt that code to check for encounters with the body itself.

[JonnyOThan]

Ah, yeah this isn’t a complex math problem at all. The game already knows where the SOI translations are. Even within a single SOI you can warp through the body or atmosphere. That’s a simple calculation to find the time at which you cross a certain altitude.

The hard part, I think, is making sure timewarp doesn’t go past that point.

[gotmachine]

That’s a simple calculation to find the time at which you cross a certain altitude

You're right, I was overthinking this as a need for a generalized method to find intersections with any body. But since KSP already discretize any potential intercept by splitting the trajectory into separate orbit patches for each encountered SOI, all we have to do is find when each orbit patch is crossing a specific altitude threshold.

The hard part, I think, is making sure timewarp doesn’t go past that point.

Once we have encounter UT for every patch, it's trivial : get the smallest one, and if current UT + next time step > smallest UT, stop (or lower) warp rate. Although we can make it a bit fancier by slowing warp progressively like stock does on SOI transitions (see TimeWarp.ClampRateToOrbitTransitions()).

All this should likely be done as additional logic in TimeWarp.getMaxOnRailsRateIdx() which is the code that is supposed to slow warp rate depending on the altitude thresholds / body intersect. Specifically, the part that isn't smart enough is the if (lookAhead...) part, which is testing the body and its altitude warp limits against the current UT + deltaT at current warp rate, failing to detect an intersection happening during that deltaT.

This being said, that (not very reliable) stock code is currently only checking the active vessel. I'd say ideally we would do this for every vessel, but then the perf overhead would start to be significant. The "next encounter UT" could be cached, more or less eliminating the issue, it doesn't need to be recomputed as long as the vessel is on rails and no new orbit patch is added, but that entails doing the caching somewhere, likely another "object extension" static dictionary.

Another question then becomes what should happen when a not-active vessel intersects a body. Having timewarp being stopped because a random debris at the other end of the system is about to crash into a moon doesn't feel like a good idea, I'd say for other vessels we should probably just treat this as a collision detection improvement and destroy it.

Anyway, quick and dirty test implementation here, seems to work well enough :

[KSPAddon(KSPAddon.Startup.Flight, false)]
public class FixWarpThroughBodies : MonoBehaviour
{
    private double nextEncounterUT;

    void FixedUpdate()
    {
        TimeWarp timeWarp = TimeWarp.fetch;
        Vessel v = FlightGlobals.ActiveVessel;
        Orbit currentPatch = v.orbit;

        double patchEpoch = Planetarium.GetUniversalTime(); // first patch needs this
        nextEncounterUT = double.MaxValue;
        while (currentPatch != null)
        {
            double periapsis = currentPatch.PeR;
            double stopWarpRadius = currentPatch.referenceBody.Radius + currentPatch.referenceBody.atmosphereDepth;
            if (double.IsFinite(periapsis) && periapsis <= stopWarpRadius)
            {
                double encounterTA = currentPatch.TrueAnomalyAtRadiusSimple(stopWarpRadius);
                if (double.IsFinite(encounterTA)) // will be NaN if no intercept
                {
                    double encounter1DT = currentPatch.GetDTforTrueAnomaly(encounterTA, 0.0);
                    double encounter2DT = currentPatch.GetDTforTrueAnomaly(-encounterTA, 0.0);

                    double patchEncounterUT = patchEpoch + Math.Min(encounter1DT, encounter2DT);

                    if (patchEncounterUT < nextEncounterUT)
                        nextEncounterUT = patchEncounterUT;
                }
            }

            if (currentPatch.patchEndTransition == Orbit.PatchTransitionType.FINAL)
                break;

            currentPatch = currentPatch.nextPatch;
            patchEpoch = currentPatch.epoch;
        }

        if (nextEncounterUT == double.MaxValue)
            nextEncounterUT = double.NaN;
        else if (Planetarium.GetUniversalTime() + Time.fixedDeltaTime * timeWarp.warpRates[timeWarp.current_rate_index] >= nextEncounterUT)
            timeWarp.setRate(0, true, true, true, true);
    }

    void OnGUI()
    {
        GUI.Label(new Rect(50, 120, 400, 20), "Next encounter: " + KSPUtil.PrintDateDelta(nextEncounterUT - Planetarium.GetUniversalTime(), true, true));
    }
}

[JonnyOThan]

A vesselmodule would be a good place to cache "next UT" for unloaded vessels. I only really care about the active one though.

[gotmachine]

Adding a VesselModule for storing two values is totally overkill, I prefer the static dictionary approach.

[JonnyOThan]

Yeah, fair...if we have a VesselModule for other fixes we could combine some...although they might have different update requirements.

I missed this part though - sounds like a better solution anyway:

I'd say for other vessels we should probably just treat this as a collision detection improvement and destroy it.

The one wrinkle is non-loaded vessels that enter atmosphere but where the periapsis is above the auto-destruction threshold. I think you'd just have to ignore them because you can't simulate drag at that point anyway so there's no point in dropping out of timewarp. This seems pretty consistent with the timewarp behavior in the tracking station.

[gotmachine]

So, I've put a patch together in #252

However, I'm having a very hard time finding a way to reproduce the issue in the first place, at least with the stock bodies, even when increasing timewarp speed way past the max stock value.

The stock way of preventing that issue basically rely on the warp rate limits at predefined altitude thresholds, where each body is getting its own set of altitude thresholds (CelestialBody.timeWarpAltitudeLimits array, exposed through TimeWarp.GetMaxRateForAltitude() and TimeWarp.GetAltitudeLimit()).

The way these limits are used is that when, and only when the periapsis is lower than a safe value (atmo altitude and/or max terrain height), it's not possible to warp faster than defined in the thresholds for the current altitude, and stock actually does check what the altitude will be at next fixed frame, not just the current altitude.

There are, in theory, a few cases where that logic could fail, and that the patch in the PR should handle :

• Warping fast enough for going though the altitude threshold entirely in a single fixed step. This could happen either if the altitude thresholds are way too low (especially for the max warp rate), which I feel might be the case with many modded bodies, or if the timewarp rate is increased above stock max 100.000x through a plugin.
• The stock logic only check the current orbit/body, so when you go through a SOI transition, the warp rate limiting logic won't apply to the time step starting in the current SOI and ending in the next SOI. It's theoretically possible for that time step to end past the periapsis in the next SOI, or even past the entire SOI. I'm not sure if that is a problem in practice, I haven't tried to repro it.

So I feel a first step would be to actually find ways to reproduce the issue. I personally recall seeing that issue in the distant past, but I don't remember the exact situation, I have no idea what my planetary mod setup was (if any), and which version of KSP this was under. It's entirely possible there was, or still is a hole in stock logic, but I haven't been able to find it, be it by checking the code or by trying to reproduce it.

All this being said, the whole thing relying on per-body magic values isn't so great in the first place. I'm very skeptical planet modders are setting those values at all. And the values being hardcoded against the stock warp multipliers also isn't great, although it seems for stock they did put considerable margins, likely because there is also a gameplay dimension to that mechanism, as you usually want warp to stop way before a body encounter in order to do stuff to prepare your aerobraking, reentry or landing maneuver.

I think it should be possible to put together a generalized and automatic equivalent to the stock functionality, that wouldn't require any hardcoded values. But before even trying to do that, it would be best to first identify the current issues precisely.

[JonnyOThan]

There's a mod called WarpEverywhere that removes all warp altitude restrictions. While I'm pretty sure the bug can be triggered only in stock, using that mod should make it easy to repro.

[gotmachine]

Warp altitude restrictions are part of the stock mechanism for preventing warping through bodies.
If they are removed, or incorrectly set (which might be the case of modded bodies and greater than stock timewarp rate), the stock mechanism will indeed fail to work, especially on non-atmospheric bodies.

I've been trying various situation (various planets and moons, closed and escape trajectories...) at 1.000.000x warp (so 10x max stock warp) in stock and didn't manage to trigger the issue a single time. I'm pretty sure that I've seen that issue myself, but that was a long time ago (when I was actually playing :P). I'm starting to think that either this was fixed at some point, or this only happen under very specific conditions.

[JonnyOThan]

Could it maybe be caused by running multiple FixedUpdates in a frame? That might widen the window where it could happen.

[gotmachine]

The stock check is called from fixedupdate, so that shouldn't be a factor.

[JonnyOThan]

For the record: I’ve been unable to repro warping through a body when there isn’t an SOI transition involved, but it’s pretty easy to warp through a body on your next patch. This bug should address the problem of not slowing to 50x warp when it’s supposed to.