Performance of game is.........

[numerobis]

There's two problems here:

Problem (1): given a set of vessels off-rails, and one vessel on-rails under player control, calculate when each off-rails vessel will come close to the player-control vessel.

Problem (2): given a set of vessels off-rails, and a set of planets, calculate when each vessel will change SoI or fall too low in the atmosphere.

At base, these two tasks look similar: both refer to deciding when a point on a conic trajectory will intersect a ball on a conic trajectory. But as I will show, they've got a fundamental difference.

If you solve problem 2, you can store the solution in an appropriate data structure and not have to solve problem 2 again until an SoI change occurs, because the trajectories aren't changing over time. From then on, every frame, all we need to do is check whether time exceeds the time of the first SoI change -- no matter how many vessels there are in the game, it's just one floating-point comparison that we need to do. When that frame comes, there's more work to do, but that's so rare that the details almost don't matter.

With problem 1, we can again store the solution to when the next event will occur that an off-rails vessel will come within physics range. But that solution is invalid on the next frame: every single frame, the physics updates the orbital parameters, so they aren't identical to before -- and if you're going through the atmosphere or firing engines they can be very different. That means everything we calculated in the previous frame is now wrong. There might be a paper out there describing how to solve this optimally, maybe based on kinetic spanners or related work. But it's not going to be trivial.

That means the asymptotics don't change: we do O(nm) work to process m frames if we have n vessels.

Asymptotics matters a lot when improving implementations. You can make your inner loop super fast, or you can reduce the number of times you call the inner loop. Both are vaild. In my experience, the latter is usually the bigger win when you start out.

Programming is my unpaid day job, just like you! I'm also president, CEO and chai wallah (to list all my c-level positions). For my Ph.D. and postdoc I studied dynamic, parallel, and kinetic algorithms.

[Anquietas314]

Problem (2): given a set of vessels off-rails, and a set of planets, calculate when each vessel will change SoI or fall too low in the atmosphere.

The atmosphere thing is completely unrelated and far easier to solve: periapsis < X. As for calculating SoI changes, it would make much more sense to do this per-vessel as you perform maneuvers that could cause SoI changes in the first place. Doing it afterwards with constant updates is silly.

With problem 1, we can again store the solution to when the next event will occur that an off-rails vessel will come within physics range. But that solution is invalid on the next frame: every single frame, the physics updates the orbital parameters, so they aren't identical to before -- and if you're going through the atmosphere or firing engines they can be very different.

This is no different from SoI changes; while you're still performing the maneuver to do the transfer, physics is updating every frame. Once you're in time-warp or switch ships, this is no longer an issue. The same is perfectly true of physics spheres.

Programming is my unpaid day job, just like you! I'm also president, CEO and chai wallah (to list all my c-level positions). For my Ph.D. and postdoc I studied dynamic, parallel, and kinetic algorithms.

Really, you're going to take the "you're unpaid so you're obviously full of crap" approach? This doesn't deserve a response.

Edited January 11, 2015 by armagheddonsgw

[numerobis]

Oh, and here I thought we were having a respectful conversation.

[Anquietas314]

Oh, and here I thought we were having a respectful conversation.

So did I, right up until the snide comment at the end of your last post.