We be burnin'

[asmi]

7 hours ago, Gotmachine said:

In KSP 2, however, they made the (ambitious) choice of expanding the active vessel game logic to all vessels, essentially reducing the loaded/unloaded distinction to just "affected/unaffected by rigidbody physics". The primary motivation was very likely to provide the "thrust under warp / in the background" feature, but I'm not sure they realized how huge a can of worms they opened... This mean that all those timewarp issues will now have a much more impactful and visible effect (not to mention the performance implications). Personally, this has been my main concern about KSP 2 since they first announced that it would have an interstellar scope (meaning there will need to allow a huge timewarp max speed) and the "thrust under warp" feature (meaning they need to simulate everything coherently at any timewarp speed).

As someone who attempted to implement a mod for KSP1 which would do something like that to inactive vessels, I absolutely concur. I had to make a lot of simplifying assumptions (though to be fair some of those were caused by the way KSP1 handles inactive vessels), and yet still I had a virtually endless list of edge cases I had to handle somehow. If KSP2 is going to use the same data structures to hold all vessels (active and inactive, remember that everything in KSP1 was a "vessel"), this might make implementing such things somewhat easier, but the fundamental problem is this - a lot of physical processes don't have analytical solution f(dt) (which would make implementing timewarp trivial as you can simply pass large dt and get an end result), but instead rely on iterative algorithms, and this is a serious problem because if you make timestep too large, you begin missing certain events. Simple example to demonstrate the problem - imagine you have two vessels 100 meters apart flying at a speed of 100 m/s directly towards each other. If you have a timestep of 0.5 sec or less, you will realize that they are going to collide 0.5 seconds later, but if your time step is larger than that, you will not see a collision at all - instead vessels with simply appear to fly away from each other after a single time step. This might sound very familiar to those of us who were playing earlier alpha versions of KSP1.

[K^2]

8 minutes ago, asmi said:

If you have a timestep of 0.5 sec or less, you will realize that they are going to collide 0.5 seconds later, but if your time step is larger than that, you will not see a collision at all - instead vessels with simply appear to fly away from each other after a single time step.

This is solved with continuous collisions. And it kind of illustrates how you deal with these problems in general. You take a coarse step and you check to see if a catastrophe, in a chaos theory sense, took place in between. If not, you can just take that giant leap and keep going. If it has, you interpolate to the boundary point, and handle it there. The default case should be dropping out of warp. That solves collisions, SoI changes for active vessel, and maybe you can even do that for planetary shadows if you're using ions. Though, simply adjusting solar flux to zero in umbra and continuing with the simulation is probably a better fix. Point is, you have a default way of handling a problem, and if you can avoid dropping out of warp for special cases, that's cherry on top.

You sort of end up with three categories of ships this way. You have your active ship that's being fully simulated, unless you're in a warp factor above something like 5 or 10; you have your semi-active ships that are traveling with an engine burn and will need coarse step updates for resources and fine step updates for velocity and position; and you have your inactive ships, which you probably still want to do coarse resource updates for just because that's an option now, but you don't do fine simulation, because they're on rails. All of the ships will still need checks for collisions (at least with planetary bodies) and SoI changes, but only the active and semi-active ones need to drop you out of Warp. Inactive ships can cross SoI safely, and you just have to do the rail-to-rail transfer math when that happens. Again, you don't leave the transfer moment down to your coarse simulation step, but you look for the actual intersect point by doing a continuous collision check.

With this approach, you can have hundreds of ships with hundreds of parts doing their thing at 1M warp. It's a fun challenge, and it's a lot of work to cover all the edge cases, as you point out, but there is nothing impossible there. And while Intercept might not have resources to do the cleanest version of this, with all the bells and whistles, they kind of have to get at least a version of this working, because that's critical to the game. You have to be able to do coarse resource updates with accounting for the fact that a resource availability can change in the middle of the time tick. That's absolutely a requirement here.

[asmi]

45 minutes ago, K^2 said:

This is solved with continuous collisions. And it kind of illustrates how you deal with these problems in general. You take a coarse step and you check to see if a catastrophe, in a chaos theory sense, took place in between.

That's the problem - often you can't find this out unless you do subsamples. I gave the very simplistic example to demonstrate the kind of problems which can occur, in reality most physical phenomena are not linear, and so you can't use simplistic approach "it was in front, now it's behind - therefore a collision is possible, so need to do subsampling" because you end up subsampling all the time.

[PDCWolf]

I've been eyeing over the conversation, and it seems most are working with the assumption that burns are integrated into the normal way we do warps, as just "warping with throttle control" and everything will be simulated in real/warp time.

From an actual game design/coding perspective, Occam's razor suggest they'd just add an "execute burn" button or something of that sort, as a way to "commit" gameplay wise into a burn maneuver. This way you really wouldn't need to properly simulate stuff along the entire thing and can calculate everything in one go, in exchange for taking a bit of control away. You could visually control the speed of the maneuver, or just go do something else, and only be able to take back control once the maneuver you committed to is done.

Player creates the maneuver node >>> fuel, energy consumption, thermals and other consumables are calculated once, for the entire maneuver (since we'll have all the data for that already) >>> player clicks "commit" >>> the spaceship is no longer interactive, the player can accelerate or decrease time visually, or go back to SC/TS but this doesn't affect the simulation.

This of course can be used for in-system and interstellar, and you always have the option of 4x phys warp for in-system if you don't want to "commit". This also is probably the fastest, most reliable way to tie this entire mechanic into multiplayer where you can jump timelines to sync with other players, since we wouldn't really need to simulate crap and the player can't "uncommit".

 

[shdwlrd]

13 minutes ago, asmi said:

That's the problem - often you can't find this out unless you do subsamples. I gave the very simplistic example to demonstrate the kind of problems which can occur, in reality most physical phenomena are not linear, and so you can't use simplistic approach "it was in front, now it's behind - therefore a collision is possible, so need to do subsampling" because you end up subsampling all the time.

But Intercept has already solved the collision under warp issue. So that example is moot for KSP2. Yes, it applies to KSP1, but was solved for KSP2.

[asmi]

1 minute ago, shdwlrd said:

But Intercept has already solved the collision under warp issue. So that example is moot for KSP2. Yes, it applies to KSP1, but was solved for KSP2.

There is a reason I said it's just an example. Now remove word "collision" and substitute "possibly ran out of resource", "solar panels might enter shadow", "possible comms blackout", and so on, and so forth. Also remember than space is three-dimensional, and not one, like it was in my example, or possibly four-dimensional once you add multiplayer with it's separate timelines - and the solution becomes significantly more involved, and perhaps even impossible unless you hand-wave away most problematic parts.

[K^2]

38 minutes ago, asmi said:

That's the problem - often you can't find this out unless you do subsamples.

You don't have to be able to do this without subsamples for every possible situation. You just have to be able to avoid subsamples most of the time. Lets look at a ship-ship collision test as a concrete example.

My coarse simulation runs between positions t₀ and t₁ where I test the collisions. First, imagine that I have no forces acting on these ships. What do I do? Well, I can go into the coordinate system where one of these ships is at rest and at the origin. The second ship starts at some position p₀ and ends up at the position p₁ = p₀ + v (t₁ - t₀). Furthermore, I can draw a maximum extend radius around each ship's origin. Call them R₁ and R₂. Instead of colliding two spheres, I can do a test between a sphere of radius R = R₁ + R₂ located at the origin against the line segment (p₀, p₁). This intersection time can be done without iterating. You'll take a square root, but a square root operation on modern hardware is done in a fixed number of CPU ticks. If the line segment does not clip the sphere, I have no need to do further tests, and therefore, no need for iterations. And this will be the outcome on nearly every time step. In the few cases where I detected an intersection between the sphere and a line segment, I'll have to do finer test, which will involve iterations.

So now, lets account for acceleration. Each of the ships is firing their engine, providing a fixed acceleration, and are pulled by a nearby planet. We know the maximum pull of gravity between these two steps, so call it g. We also have a₁ and a₂ due to the engines. So the furthest ship 1 could have gotten from origin in our chosen coordinate system is 0.5 * (a₁ + g) (t₁ - t₀)². Ditto for maximum distance ship 2 could have gotten from the line we've traced. What do we do? Simple, we inflate the feasibility region, which is our sphere. R = R₁ + R₂ + 0.5 * (a₁ + a₂ + 2g) (t₁ - t₀)².

And we're done. Our simulation now no longer requires sub-steps except when the two ships pass within what will in practice be a few hundred meters of each other. And even when they do, the iterative refinement is going to be done in fixed steps until the two extent spheres touch. Only then will we have to go to a full BVH on BVH refinement, which is still a fixed number of steps. And only if we find BVH overlaps, do we have to start testing individual primitives. Which might or might not involve iterations depending on primitive types.

Space is big. Interesting things happen rarely. If you test for them on every frame, you're wasting a lot of CPU time. If you figure out how to discard any chance of something interesting early, you can skip an overwhelming majority of the computation.

P.S. Do I expect the above to be implemented for ship-ship collisions in the entire space? No, absolutely not. Intercept has one physics engineer, and I suspect she has her hands full. But it does illustrate the concept, and this is how you'd implement it if you wanted a high fidelity. In reality, I suspect ship-ship collisions to be skipped during warp. But something similar to above is likely going to have to be implemented for the SoI changes and planet collisions. Given how short-staffed Intercept is, in general, I suspect the simulation during warp to be very basic. We might not get solar flux occlusion checks, etc. We are going to get something extremely forgiving the moment you go into warp. But it's something they can work on post-ship to refine the simulation. And maybe, one day, you'll have situations where you've dropped out of warp, because you crashed into some space debris during your escape burn, following a one in billions chance collision.

Edited May 11, 2023 by K^2

[asmi]

4 hours ago, K^2 said:

Each of the ships is firing their engine, providing a fixed acceleration,

That's not how rocket engines work. They provide fixed thrust (==force), but acceleration is always changing because vessel's mass always decreases

 

4 hours ago, K^2 said:

We know the maximum pull of gravity between these two steps

We can't know it because we don't know what the trajectory is going to look like as the burn is underway. Also imagine if there is an SOI change somewhere during the burn?

4 hours ago, K^2 said:

We also have a₁ and a₂ due to the engines. So the furthest ship 1 could have gotten from origin in our chosen coordinate system is 0.5 * (a₁ + g) (t₁ - t₀)². Ditto for maximum distance ship 2 could have gotten from the line we've traced. What do we do? Simple, we inflate the feasibility region, which is our sphere. R = R₁ + R₂ + 0.5 * (a₁ + a₂ + 2g) (t₁ - t₀)².

That is also absolutely wrong because, remember, ships are moving along orbits, and not just in straight lines. And orbital motion presumes that there is always a non-zero acceleration.

-------

I'm not trying to pick on your, what I'm trying to demonstrate is that things are a lot more complicated than they seem to someone who never actually done such things before, and intuitive solutions turn out to be totally wrong. And this is not even considering that in reality there is always more than one celectial body affecting the orbital motion of vessels. Something for which there is no analytical solution at all (at least as of this moment), and the only way to faithfully simulate that reality is by doing many, many, MANY iterations. There is a lot of academic research on that topic, and there are ,any clever solutions, but all of them are based on iterations, and are not analytical (meaning there is no function which would allow calculating position of a vessel at arbitrary point in time based on certain initial conditions (position vector, velocity vector).

[Haustvindr]

I'm hijacking a bit, and I'm not really good at physics but... as far as I've understood:

2 hours ago, asmi said:

That's not how rocket engines work. They provide fixed thrust (==force), but acceleration is always changing because vessel's mass always decreases

I think it's safe to assume that the acceleration will be fixed for the duration of the physics tick. In the next tick, it will take the new mass and TWR and calculate the new acceleration. Even in big time warps where you could "advance" a lot of space after your fuel runs off, it still does make sense, since in space there's nothing to slow you down once you accelerate to speed and therefore the difference would be probably acceptable. Even then, you could handle this as a special condition (engine without thrust) and make a second calculation to fix that difference or something along those lines.

And in celestial bodies the maximum warp is much smaller on purpose, which means forces such as atmospheric drag and tighter gravity are updated more frequently, making it much more accurate.

2 hours ago, asmi said:

That is also absolutely wrong because, remember, ships are moving along orbits, and not just in straight lines. And orbital motion presumes that there is always a non-zero acceleration.

As I've said, I'm not really good at physics, but I think the collision probability area is just a bubble with the center in the vessel current position and with a radius of the maximum distance the ship can do in the physics tick. Meaning, it doesn't matter the direction nor if it is not moving in a straight line, the ship can only end the tick whithin that bubble.

And if I'm getting it right, that means it is not a "perfect" solution because there are also some weird edge cases where there are wasted cycles due to not having the direction in the formula, but I guess it's fine since they would be discarded in the second pass. E.g. if a ship is coasting perfectly parallel to another, at the same speed, then in high time warps = their bubbles will always intersect but they will never have a collision. Not perfect, but still very good since those cases in space are typically very rare or made on purpose (i.e. while docking).

If it is not like that and I'm completely misunderstanding, the please disregard everything I've said and kick me away to a math class.

[cocoscacao]

3 hours ago, asmi said:

And this is not even considering that in reality there is always more than one celectial body affecting the orbital motion of vessels

Are you talking gamewise, or in general? I think they don't really take that into account in both games, which is fine

[MarcAbaddon]

Honestly speaking, from the current version of the game I did not think they thought too much about the details (or decided to ignore them, which could be a pragmatic choice).

Right now I think the main issue that really limits the usability of this feature is that you get locked into your current heading. When navigating close to a celestial body you usually want to keep burning pro-grade/retro-grade/whatever and a slow burn with locked direction will just not go what you want. Getting out of Kerbin orbit with low thrust engines will still be painful. It's more usable in high orbits or when orbiting Kerbin, because then your heading is relatively stable relative to pro-grade. 

Another issue that won't come up in normal play as much is that burning on rails ignores assymetric thrust configurations and simply behaves as if your thrust vector is in-line with your center of mass.  One scenario where it might come up is if you have another vessel docked, shifting your center of mass. 

It only working for active vessels might be another issue once you have a lot of things going up at once. But since we have no alarm clock features yet either, I think the game is just not ready for complex simultaneous missions and it might get implemented later.

Given that those issues are not addressed, I am a bit skeptical about the implementation being very robust under other circumstances as well.  I wouldn't be surprised if they used time warp dependent updates even when not strictly required.

[K^2]

5 hours ago, asmi said:

We can't know it because we don't know what the trajectory is going to look like as the burn is underway. Also imagine if there is an SOI change somewhere during the burn?

We have to do the fine steps for trajectory integration - that's unavoidable with gravity. Which means that you can actually cache the maximum force of gravity during a coarse step. Not a problem at all.

SoI change is another potential boundary. In a general case, you're going to check off all of your potential boundaries and look for the earliest point you have to do additional work. That's going to be collisions, SoI changes, running out of fuel, running into a planetary shadow, running out of a radio range, and potentially any number of other conditions. This simple case illustrates collisions only, but yes, for the full simulation, you have to consider all such stopping conditions.

5 hours ago, asmi said:

That's not how rocket engines work. They provide fixed thrust (==force), but acceleration is always changing because vessel's mass always decreases

We are looking for the worst case scenario. You just take the acceleration at the end of the coarse step for the maximum acceleration the ship could have had.

You'll note that we're not even checking for a direction of gravity and acceleration. We just assume they are colinear, because that's the worst case. And that's all we have to check. If the worst case generates a feasible collision, we do more work. But overwhelming majority of the time, that won't be the case, and we can simply skip refined computations.

5 hours ago, asmi said:

That is also absolutely wrong because, remember, ships are moving along orbits, and not just in straight lines. And orbital motion presumes that there is always a non-zero acceleration.

If you take a ship capable of maximum acceleration a, initially moving at velocity v from position p, it will be within 0.5at² of p + vt after some time t elapses. It doesn't have to end up at exactly that distance from that second point, but that's the furthest it can end up. Which means that if we can exclude a collision with a sphere of a radius of R + 0.5at² centered at p + vt, then the collision with a sphere of radius R at a point the ship actually ended up is impossible. Again, the fact that we got an intersection doesn't mean a collision happened, but if we don't, it certainly did not. Which means we can do coarse steps in linear segments, so long as we inflate the feasibility region sufficiently to account for the acceleration.

The rest is change of coordinate systems and using Minkowski difference to reduce a capsule-capsule collision to a sphere-line collision check. This is textbook standard optimization. If you don't think it works, I suggest you review the steps in more detail, because that's something that a lot of modern physics engines heavily rely on.

If you don't know how Minkowski sums and differences work, and how these are used in collision detection, I suggest you review the concept, and maybe take a look at some applications, such as the GJK distance algorithm to illustrate the point.

5 hours ago, asmi said:

I'm not trying to pick on your, what I'm trying to demonstrate is that things are a lot more complicated than they seem to someone who never actually done such things before, and intuitive solutions turn out to be totally wrong.

This sort of thing is literally my job.

[asmi]

12 hours ago, K^2 said:

This sort of thing is literally my job.

[snip]

12 hours ago, K^2 said:

We have to do the fine steps for trajectory integration - that's unavoidable with gravity. Which means that you can actually cache the maximum force of gravity during a coarse step. Not a problem at all.

If you need integration - you can't have large timesteps. You can't have it both ways.

12 hours ago, K^2 said:

We are looking for the worst case scenario. You just take the acceleration at the end of the coarse step for the maximum acceleration the ship could have had.

Worst case is large timestep and tight orbit - which means your vessel is supposed to on the opposite side of celectial after that step. Or maybe even in the same exact spot (relative to the orbiting celectial of course, not in world coordinates). That gives you exactly zero information about possible collision course.

12 hours ago, K^2 said:

You'll note that we're not even checking for a direction of gravity and acceleration. We just assume they are colinear, because that's the worst case. And that's all we have to check. If the worst case generates a feasible collision, we do more work. But overwhelming majority of the time, that won't be the case, and we can simply skip refined computations.

At large enough timestep those spheres will be so enormous that you will have to do subsampling pretty much all the time. Which is one of the problems I listed initially.

12 hours ago, K^2 said:

If you take a ship capable of maximum acceleration a, initially moving at velocity v from position p, it will be within 0.5at² of p + vt after some time t elapses. It doesn't have to end up at exactly that distance from that second point, but that's the furthest it can end up. Which means that if we can exclude a collision with a sphere of a radius of R + 0.5at² centered at p + vt, then the collision with a sphere of radius R at a point the ship actually ended up is impossible. Again, the fact that we got an intersection doesn't mean a collision happened, but if we don't, it certainly did not. 

At large timesteps that sphere will be so huge that it will encompass close to entire SOI of a celestial you are orbiting. And the reason the sphere has to be large is to account of orbital motion because that timestep can cover a significant portion of an orbit (or even several orbits).

This is the same reason you can't use naive linear propagation integration (S1 = S0  + V0*dt, V1 = V0 + A*dt in vector form of course) to model the orbital motion because this way you will get nonsensical resutls like violating the laws of concervation of energy. This is the sort of thing that KSP1 was doing back in the day, which is why orbits of active vessels were always dancing around - well it was one of the reasons, other included phantom forces from the physics engine.

12 hours ago, K^2 said:

Which means we can do coarse steps in linear segments, so long as we inflate the feasibility region sufficiently to account for the acceleration.

And if you do that, you end up with doing subsampling pretty much all the time at large timesteps, which effectively means that you can't do a large time steps at all. And we're not even talking about such large timesteps - even for low Earth orbit it takes only 90 min / 2 = 2700 seconds to end up on the opposite side of the planet, Kerbin being 10 times smaller this number is even less (20 min / 2 = 600 seconds? I don't remember the period of LKO of top of my head). If we assume "normal" physical timestep of 1/60 seconds (I think that's Unity's standard), that's about 36000x time acceleration. Given that in most saves there is always a metric ton of stuff in Kerbin orbit (from spacestations to comm sats to spent stages and all kinds of other junk), your algorithm will always indicate possible collisions.

------------------

[snip] this collision business is just an example, and I'm personally much more interested in modelling subsystems aboard inactive vessels (like power, comms, ECLSS resources, etc.). THIS is where stuff gets real, and, what makes it worse, there is no big body of academic research like one which exists on a topic of orbital motion, so you are pretty much on your own.  [snip]

Edited May 12, 2023 by Starhawk
Redacted by moderator