The OP hasn’t been super-clear about the nature of the game, and it does absolutely make a difference in the best optimization method. Patched conics may very well be the best solution; my precomputation solution assumed that several bodies were all influential.
It’s not strictly true that patched conics don’t work well when you get to three bodies; they work fine as long as there is a kind of mass hierarchy. For instance, orbiting a moon of a planet that’s orbiting a star works just fine as long as the mass ratios are high. The moon, planet, and star are all a significant influence, but as long as the acceleration field is fairly flat for the higher levels of the hierarchy, it works.
Swing-by maneuvers, at least some varieties of them, also work. For instance, if you start at Earth and raise your apoapsis to Jupiter, then you will enter Jupiter’s SOI a a high (relative) retrograde velocity. Swing around so that you are now going prograde, and you exit Jupiter’s SOI with a quite high velocity.
Do a burn at periapsis (i.e., near Jupiter) and you do even better because the excess velocity from your hyperbolic trajectory is greater than the delta-V you spent on the burn.
On the other hand, stuff like LaGrange Point orbits don’t work. And as you mentioned, I don’t think any variety of dynamic capture works.
At any rate, lots of fun possibilities here. I’m curious what the AI is actually doing here–maybe some kind of stochastic pathfinding, for instance.
A “precomputed solution” for the gravity field would have to be recalculated every step to account for the motion of the various sources. A discrete grid is sometimes used in fixed frame gravity fields–for instance, most detail models for the Earth gravity field in orbit used for high precision geodesy use a combination of a reference ellipsoid combined with a local gravity anomaly model (either a discrete grid or high order spherical harmonics)–but only because the gravity field is fixed with relationship to an rotating Earth reference coordinate frame. Because of the computational complexity the model parameters are typically precomputed only for the planned orbit. There would be no reason to do this in broad open space where one mass dominates the local gravity field with smooth gradients and continuous geodesic field.
The use of patched conics for calculating swing-by maneuvers depends on the fidelity of the simulation; if the transition from the ‘external’ sphere of influence to the local sphere of influence occurs over a single step then it can be simulated directly with patched conics by selecting the trajectory parameters to minimize the difference in energy (in the external system) and just transforming from the external to local coordinate frame. The trajectory can be estimated to somewhat finer steps by linearizing using the Clohessy-Wiltshire method (see Prussing, Chapter 8). However, for high fidelity simulation you do have to use a numerical integration process, typically solving the Jacobi’s integral formulation for the restricted three body case. When dealing with more generic n-body systems or systems in which the influence of the acting masses on the object in question cannot be cleanly delineated, then we go to more generic Hamiltonian formulation and numerically integrate and perturb the field locally to get the state change. However, this is far more work and effort than should be required for a game simulation.
Indeed, but the OP specifically said that the planets were fixed.
Well, one reason is that it’s easy. Patched conics are tricky, but a precomputed field gives a reasonable speedup for the basic numerical solution. There’s something to be said about an inner loop that’s just a few lines of code, especially if you aren’t actually travelling to Mars.
A basic coordinate frame transformation appears to be what Kerbal Space Program does. I’m not sure about any energy minimization stuff, but since it’s a real-time game, I doubt it–the timesteps are always small enough that it wouldn’t make a difference.
Sphere of influence transitions and certain other artifacts cause a lot of edge case problems in Kerbal Space Program, Stranger. The crude methods you use may be good enough for some ideal studies of a particular flight, but they are not bulletproof methods that you would want if you were building a real time simulation with the intention of players being able to do anything.
Also, the methods you use are too slow. This is why you need high order, energy conserving integration - for a game’s purposes, you want enough accuracy for reliable orbital rendezvous with long timesteps for more time to synchronize threads and multiplayer clients with each timestep.
Finally, sphere of influences end up being a bunch of special cases, and the code becomes quite dirty. N-body is actually the simpler solution.
Well, it would be if the planets were moving. Since the OP wants fixed planets, Dr. Strangelove’s solution is the correct one.
Amusingly, a modified version of A* pathfinding could probably operate on a potential energy grid and calculate the fastest possible transit given a particular delta V budget.
The KSP implementation of patched conics leaves a lot to be desired, though. For instance, there’s zero reason why one should be able to pass completely through an SOI, but in KSP it’s possible. At high time accelerations there’s a large time step that might jump past the SOI–but a proper implementation would simply compute the intersection point and stop there. It’s not particularly hard to intersect a conic with a sphere, but KSP doesn’t do it (some of this might have to do with the Unity engine… I dunno).
I’m leaning towards the following solution, for now:
Since the number of positions to calculate it’s the main factor affecting the speed of the AI decision making I tried many short trips instead of a long one.
For example calculating the angle and original speed for traveling from Saturn to the Sun took from 200 to 800 milliseconds (depending on the ship’s original speed, angle and position relative to Saturn), so now I make it calculate the variables to a middle point between Saturn’s and Jupiter’s orbit when it reaches that point it calculates the variables for traveling to Jupiter, then to a middle point between Jupiter and Mars and so on until it reaches it’s destination.
Each small trip calculation takes from 10 to 100 milliseconds and with a little optimization it should be tolerable.
I realized that I was asking the program to do something the human player does not do, to whit: calculate a combination of speed and angle that would take the ship all the way to it’s destination. When I controlled the ship and wanted to go near the Sun from Saturn I would use the “many short trips” strategy described above.
This change loses the beautiful trajectories the computer calculated (one cool result used Saturn’s gravity to correct an orbit “down” and Jupiter to correct it “up” finally reaching the Sun after tracing an S shape) but it’s way faster.
The game is a space ship combat “simulator” mixed with some RPG elements, I’ll invent some technobable for it being limited to 2D, and for the “maximum speeds” I’m giving to different ships and missiles for simplicity’s sake.
The planets are fixed to avoid further complications in the trajectory calculations.
The player would take the place of a ship’s captain at first, graduating to command of small flotillas of ships later.
Ships will fight with missiles at long range and with energy weapons at short range.
I’m still working on a prototype where a human controlled ship will fight a computer controlled one.
I think you should fix this. Multithread your code - 800 milliseconds is not long if the main game is not waiting on it. Don’t make AI ships visible to the player (don’t spawn them in the world) until after their paths have been calculated.
This seems to be a very long time, but I don’t have a good feel for what you’re doing. A basic tour of a few planets shouldn’t need more than about a thousand timesteps, and each step shouldn’t need more than perhaps a thousand flops. Even single-threaded and in double precision (probably not necessary here), it seems like one trip should take well under a millisecond on a reasonably modern system.
What language are you programming in? In C++ you can achieve peak perf easily; in C# you can come within a small integer factor; but if it’s JavaScript or Lua or something, it’s probably hopeless…
I’m using C#, calculating a course of a few thousands timesteps takes about 10ms, but to reach a given point I’m using trial and error changing the angle of the ship and sometimes the speed and seeing where it will take the ship, so calculating the needed speed and angle to reach a given point can take about a second for long voyages. That’s why I wondered if there was some equation I could use to reach those variables without calculating all the intervening points.
I was about to say that it would be impossible because by the time the worker thread comes back with the solution the ship would no longer be there, but then I realized that I can make it so the calculation is made for a future point in the ship’s current path and implemented once it reaches it, so I’ll probably dedicate tonight’s coding to exploring that possibility.
Thanks for the tip!.
That wouldn’t work because the ship has to react to the player’s actions and other developments by deciding on new courses of action that would demand new travel calculations.
Understood about the multiple paths, but 10 ms seems a bit slow for C#. You’re just using Euler’s method currently, right? By my mental estimate, that’s around 100-200 FP ops per timestep. So about 500k FP ops for a few thousand steps.
But even a really old CPU, with SSE not working, should still get something like 2 gigaflops in DP. Even if C# has 4x overhead (on the high side in my experience), that’s still only ~1 ms per course. Seems like you might be hitting some inefficiencies. Have you spent some time just refactoring your math? For instance, it’s easy for divides and square roots to appear in lots of places, but I think you only need one of each per body, per timestep (divides and square roots are generally more expensive than adds/multiples) if you factor it right.
Another point, I’m not using Euler’s method, at least not on purpose (I’m trying to grok it from it’s wikipedia page and I’ve reached the conclusion that It’s too damn late and I’m too tired )
What I’m doing is adding the vector of each’s planet gravity accel to the vector of the ship’s current velocity and calculating the next position from that velocity, then repeating until it reaches it’s destination, the Unity engine reports a collision in the next position, or an arbitrary number of steps (about 5000) have been calculated.
Heh, debug vs. release will certainly make a difference!
You’re using Euler’s method, which is the most basic method of solving a differential equation. You’re actually using it twice; first to estimate the velocity from the acceleration, and then again to estimate the position. Your inner loop should look something like:
accel = computeAccel(pos, bodies);
vel += timeStep * accel;
pos += timeStep * vel;
However, you said you loop over all the bodies, which isn’t going to be quite as efficient since there will be some extra multiplies by timeStep and the gravitational constant.
Knuth’s comment about premature optimization is wise, but there’s something to be said about refactoring your math as much as possible before coding it. Simple and well-factored math tends to be fast as well.
Umm, I calculate the accel from all the bodies once, no timeStep there, then I apply it to the current velocity and then multiply by timeStep, looks like I’m using the methond only once to me.
Let me see , looking at the code, it works somewhat like this:
initialize variable lastVelocity with current craft velocity
Main Loop starts
calculate position in path as craft's position + lastVelocity + timeStep.
Loop throug the array of planet's, add it's gravity accel to newVelocity variable.
lastVelocity += newVelocity
Loop.
You are right, I think I’m committing just the reverse of the sin Knuth warns about, I’m changing my design to accomodate a slow process un ways that may not be necessary, I’ll try to optimize it first.
There’s the first use of the time step. (I corrected your formula above, BTW, but I assume it was just a typo in your post.)
And if you’re doing it right, this is the second place you need to account for the time step. You should have (new velocity) = (old velocity) + (acceleration)(timestep), or (symbolically) v = v[sub]0[/sub] + a∆t.
I just realized that in the real world, or at least a Newtonian one, the code should do as MikeS says and multiply the new velocity by timeStep, that’s because the forces are acting on the ship for the duration of the timeStep, but in this program there is a “FixedUpdate” event that fires each timeStep milliseconds and adds the velocity, since this code does not multiply by timeStep neither does the code simulating the path (in fact they are the same subroutine). I could change it but it works fine (meaning it looks realistic) this way and it would slow down the loop I’m trying to optimize.
That’s reasonable. It effectively just means that you have a fixed timestep of 1 unit of game time, so an acceleration of 1 m/ticks[sup]2[/sup] always applies 1 m/tick of velocity per iteration. In fact, you can fold together the mass, gravitational constant, and timestep into one constant associated with each body. Just make sure to keep track of your units.
I’m not using a gravitational constant, the acceleration per tick is calculated as
PlanetDirection * PlanetMass / Distance ^ 2
where PlanetDirection is a 2 dimensional vector: Ship -> Planet
PlanetMass is a number out my hat, without units, for game purposes it only matters in relation to other planets, thus the Sun has mass = 10, Jupiter = 1, and Earth = 0.1.
Distance is measured in meters, but I’m obviously cheating to shorten the number of steps in my calculations, so the Sun for example has a radius of 5 meters :).
Everything is more or less to scale and the ship is very small, so the player will not notice the small size of everything.
I wonder if that PlanetDirection * PlanetMass / Distance ^ 2 equation could be refactored somewhat to make it more efficient? currently is being calculated 7 times per step.
)