Is there an easy way to calculate the position of a space ship at time T, from it’s original speed, mass and the position and masses of nearby gravity sources?.
I’m working on a space ship game and so far I can do it by calculating all the previous positions until I reach T, but that can get very slow for high values of T, is there a way to create a function => F(initialPosition, surroundingPlanets,T) without calculating all previous positions?.
Thanks in advance,
Frodo.
If there is more than one body exerting significant gravitational influence there is no general analytical solution.
I suspected that the 3 body problem would rear it’s ugly head, this is in a 2d space and I am adding the speed due to each planet gravitational effect every “tick”, could something be made to work given those 2 differences from the real world physics?.
Also, the planets are fixed, they do not move, only the spaceship is affected by gravity.
You appear to be missing a vector for your velocity, maybe more than one if the thrust becomes off-axis.
Yes, the function I’m looking for would be really f(initialPosition, initialVelocity,surroundingPlanets,T) where initialVelocity would be a vector.
Kerbal space program does it using patched conics but I think this is only useful for a single gravity field, though I may be wrong on that.
Even with the modifications you’ve mentioned, I’m pretty sure that the answer is still no. Your best bet to speed up your code is to look into more sophisticated algorithms for numerically solving differential equations; in particular, you might want to look into so-called adaptive step size algorithms, which allow you to increase the length of “ticks” when not much is happening (which would be a lot of the time, in your case—your velocity won’t be changing all that fast when you’re far from any masses) and still be sure that your answer is fairly accurate.
I’m thinking of doing something like that, and also find more optimization tricks to accelerate the function, but it’s seems strange to me that there is no more efficient ways of doing this calculation, how do they plan for space probes like Dawn or Voyager for example?.
Investigating Saffer suggestion I see that apparently for real life space missions they usepatched conics, like in Kerbal Space Program.
If the game’s 2d, you can use various analytical solutions.
If you’re looking for a correct answer, though, you want to use fourth order symplectic integration. Symplectic integration preserves energy over integration steps, which is much more important than phase angle for a simulation of gravity. Fourth order means it gets a lot done per timestep (and it’s much more efficient per cpu cycle used)
Here’s a free online book with source code that covers how to build such a tool : The Maya Project home page
To be fair, I seriously doubt your integration method is slow enough to be a problem. Collisions need orders of magnitude more cpu power. Are you profiling your code?
Thanks! I’ll take a look, the site seems a bit too high in mathematical difficulty for me but I can try to understand the code even if the higher theory escapes me.
It needs a bit of optimizing yet but it calculates 1000 positions in about 8 milliseconds in a 6 planet and sun star system (a path from “Saturn” to the “Sun”).
The problem is that for the AI to plan it’s strategy I need to simulate a lot of paths, calculating a lot of intermediate positions I don’t need may prove too taxing.
Correction, 80 milliseconds, and 2900 positions. I misremembered an early incorrect test.
Ok, there’s 3 main techniques you can use to speed things up. I suspect you can get a several-thousand fold improvement if you implement them all.
Well, you can spatially divide the solar system and add up the total influence from gravity at each division level. In your case, you’d divide it into a quad-tree, and at each quad-tree zoom level, you keep a variable that tracks a point-source of gravity that is the sum of all gravity sources in that subdivision.
This means for your simulation not to become horrendously inaccurate, the timesteps have to be pretty close together.
Well, the higher order methods increase accuracy exponentially. A “fourth order method” is only inaccurate by (1/(some small constant))^4 . This means you can safely make the time between timesteps really long - several seconds, even minutes.
The methods involve a complex equation instead of just x += vt, and v += at, but these equations require all of the same data you already have, and you can easily abstract them in your programming language so you only have to type them in once. You don’t have to understand how they were derived.
Here’s an article on how to do it : http://http.developer.nvidia.com/GPUGems3/gpugems3_ch31.html
All right, you’ve said that:
This suggests that you can precompute the gravitational field. Create a large 2D array (several thousand units squared), and precompute the sums of the gravitational accelerations. Then, when it comes time to simulate, you can do a simple lookup (with a bilinear or bicubic filter) instead of having to sum across all your planets.
It’s a lot of math upfront, but you only have to do it once for a given planetary configuration.
my bad
The variable would track all gravity sources that affect the subdivision but are outside of it?. I don’t quite get this method.
I can set the time step of “reality” to a larger span of time too, thus reducing the number of positions to calculate, this is the strategy i’m testing now and it seems promising, I think if I reduce it too much the orbits would start to look less and less round and more like an hexagon…
I’ll take a look at the site you linked too and try the higher order methods see if I can use that method to furter speed up the calculations.
That looks promising too, but I don’t know if I can use it with the game programming framework I’m using (Unity).
Looks good, I’ll have to see if the amount of time spent calculating the gravity vectors of ll planets is long enough to justify it, I sort of want to procedurally generate star systems in the game and this method could complicate that.
The overhead might not be worth it, but to save some time, you could when the system is created initialize the array of gravity vectors, but don’t fill it in. Only calculate an entry when you need it (if it hasn’t been calculated already).
But I’d look hard into using closed-form conic equations whenever the spacecraft is close enough to a planet that nothing else has a big effect (or far enough away from them all that the star is the only thing that matters).
Perhaps I’m uniquely misunderstanding the request of the o.p., but he seems to be asking for a method of calculating the state of an object in planar motion at relatively low precision (e.g. not calculating dynamic capture or swing-by maneuvers). Provided that the impulsive maneuvers can be treated as instantaneous (i.e. shorter than the time step interval at which you are determining states) there isn’t any need for complex numerical integration schemes, or precomputing a gravity field, or creating a hamiltonian formulation and converting into phase space, or whatever. This is simple state-based orbital mechanics for which basic orbital mechanics (often referred to as “Kepler’s Laws of Planetary Motion” but the more generic formulations will apply equally to any object of any size) are entirely sufficient. The method of patched conics–that is, creating a trajectory such that the trajectory (the path of which is defined as part of a conic section) in the sphere of influence of one body is tangent at the intersection to the path leading into the sphere of influence of another.
For instance, a spacecraft going from Earth to, say, Neptune will have an escape trajectory from Earth orbit that will be a section of a hyperbola, which will align with an elliptical orbit about the Sun, which will then intersect with an elliptical orbit about Neptune. You can calculate the difference in total orbital energy (kinetic energy of the object and the potential energy to escape from orbit) which will give the impulse transfer (e.g. the work required from which momentum can be calculated) required to go from one orbital state to another. When the spacecraft is on a ballistic (e.g. unpowered, no thrust) trajectory, the position can be calculated purely as a function of time, or the time as a function of the mean anomaly (angle of the body along its trajectory from the defining epoch). It is typically not possible to have an explicit solution to the intersection except in very trivial cases, but standard optimization routines can be used to select trajectory parameters that achieve minimal difference in orbital energy at the intersection without having to perform your own integration.
This can all be done with algebra and trigonometry; no integral calculus required. The only reason you would need to perform integration is if you have a long duration thrust, or the object is moving sufficiently slowly that its step from one celestial body’s SOI to another isn’t essentially instantaneous (relative to the time step of the simulation), or the object is under the significant influence of three or more bodies (or if the spacecraft itself is large enough to gravitationally influence another body, in which case, you should probably park the Death Star and start with something a little more sensibly sized). In this case a time step that varies in proportion with the momentum change per time step (which can be approximated by using basic algebra) should be used and the difference from state to state calculated with sufficient truncation that you don’t propagate errors. For just a short period with appropriately-sized time steps using the Euler method should be fine; for more precision or integration over a longer period, adaptive Runge-Kutta methods are generally used. (You could use a high order method but I’ve never needed to use more than order 4 to get reasonable precision for the trajectory models I’ve built.)
Seriously, unless you are looking at orbital perturbations or calculating some kind of high precision ephemerides, the patched conic and simple numerical integration described above is all that is needed, and all I’ve ever used to perform mission studies and basic simulations to calculate close estimates of durations and required impulse. Robert Braeunig’s Rocket & Space Technology Site is, as usually, an excellent source of basic information. You can also look on various “open university” sites for class notes like this one from MIT Open Courseware for introductory Dynamics. I highly recommend Johhn Prussing’s Orbital Mechanics as an easy introductory reference and self-study. Although it is fairly expensive, I have the previous 1993 edition which is excellent and can be found quite cheaply used. It is certainly much more accessible–but less comprehensive as an orbital mechanics reference–than BMW or Vallado’s infamous Fundamentals of Astrodynamics and Applications.
Good luck to you in your efforts.
Stranger
From a game design / AI perspective it’s less important that your calculations be *correct *than that they be repeatable.
For example, you could say that if an object is more than X kilometers from a mass, you ignore than mass during your calculations. You might get a decent result just by using the sun by itself most of the time and occasionally the sun + one planet. It won’t be an accurate simulation, but from the player’s perspective will it matter? Will they be able to tell the difference between a full N-body calculation and this kind of shortcut?
And as long as your AI is using the same crude algorithm to calculate future positions then it will be able to make accurate predictions about what’s going to happen.
A lot of games do stuff like this. They don’t simulate reality. They simulate something easier that gives a mostly right answer most of the time.