How to predict encounters between a ship and a body's sphere of influence in 2D

Question

Long time listener, first time caller. I'm making a little hobby game in XNA, its about transport ships in space, analogous to container ships at sea. I need to be able to predict the encounter between a Ship and a planet/moons gravitational sphere of influence in a restricted 2D environment. The positions at time of the Ship and planet/moon, Body for short, are determined from keplerian orbital elements. The Ship and Body both orbit the same centre of attraction.

The approach I have devised so far is first to do some preliminary checks on the apoapsis and periapsis (farthest and closest points from centre of attraction) to see if an encounter is possible. Between checks such as this and if the Ship's orbit is open (hyperbolic, I approximate the parabola case to a hyperbola), it can rule out many scenarios where there could not be an encounter.

If these checks determine an encounter is possible, I determine the minimum and maximum distance from centre of attraction that the Ship is eligible for an encounter. I then get the intersection points of the ships orbit with the two circles defined by that minimum and maximum. This results in zero, two, or four, points on the Ship's orbit, defining zero, one, or two periods where it could encounter the sphere of the Body. At this point if there are zero intersections it is possible the whole of the Ship orbit is in the encounter zone, this is probably an uncommon extreme case but would need to be covered.

I can get the times that the Ship will pass those points on it's orbit, giving one or two windows of time to check for encounter, but from there my best solution is searching the time span by dividing it into steps, calculating the Body's position at those times, and then testing for encounter.

The trouble with that approach is knowing the size to make the steps to efficiently find the encounter. Getting the Body's position at time is somewhat expensive so I'd rather do it as little as possible, but steps too large could potentially miss the encounter.

Are there any properties of confocal conic shapes that could help reduce the search space? Or are there other ways to predict encounter/collision between what is effectively a point moving along a conic path and a circle moving along an ellipse sharing a focal point.

Assignment

Since you are talking gravity and rotation, you should check out Osmos. – Explorer

I've played some of it, notably (one of) the level(s) with orbs orbiting a centre. It's nice, a fun game. I'm trying to create something similar to the patched conic predictor in Kerbal Space Program, but in a constrained 2D environment. – Assignment

You are currently using Eulerian integration, which is fine for most applications assuming a small enough time step. Your question I guess is this: given the fact that the ship's trajectory follows a known geometric shape, can we analytically determine intersections with another known geometric shape? Specifically, confocal conic sections intersected with the minkowski sum of a circle and ellipse. – Candlepower

In this scenario I am not using any integration positions of the objects are determined solely from the orbital elements and time. This is less realistic than if the ships movement was integrated, as you only act under gravity from one object as opposed to N. For example a ship orbiting earth wouldn't be effected by gravity from Luna, but it's position would be fully predictable for any arbitrary point in time, not counting encounters. I'd never heard of Minkowski Addition, but I think you're right. It would give the path swept by the sphere of influence along the ellipse, is that right? – Assignment

I guess you would have to create geometry representing the area occupied by the objects between the steps in time (think Donnie Darko) after calculating positions-current and positions-next. It would get tricky because an intersection between those geometries would not guarantee an actual collision occurred but it would be a good indicator that you should do something a bit more computationally heavy. While I have nothing relating to curves I sure wouldn't mind any help on that: github.com/aarondandy/vertesaur – Turbidimeter

How expensive is it to compute the next step of motion? I.e. if you are running at say 60fps, what percentage of each frame is used for physics? Can you simply run the simulation at maximum speed (at the equivalent of say 15fps) and thus predict the future based on that? I can't imagine that the physics are that expensive if you don't have to perform collision testing, unless you have a lot of objects all applying gravity to each other! -edit- oh you aren't using integration... why not? I think most physics based games use integration in one form or another. – Eberhardt

Integration is fine and all, but being able to pick any point in time, past or future, and determine the positions of the planets/ship (aside from encounters with other bodies). Kepler's 2-body scenario is fully deterministic and predictable.It's expensive as you've to solve Kepler's Equation, it might end up not being the most expensive function but I do intend it to be used by a lot of entities and even if I wasn't concerned with the cost there is the question of the interval to check. You don't want to search in large enough jumps that you miss the encounter. – Assignment

@Turbidimeter : I'm able to narrow the range of possible times down to up to two periods, times that the ship will pass through the planets time-tunnel. Next I want to be smart about telling if the planet will be there at the same time and then finding the precise encounter point. I might just have to search using some small enough time interval, but I was hoping there was something better than just brute force. – Assignment

I don't know anything about games, but everybody's always trying to approximate three-body problems as easier two-body problems. But a "dominant" influence isn't an "only" influence. If that were a real spaceship with me on board I would want a numerical simulation fine-grained enough NOT to neglect the moon and sun just because I'm in orbit around the earth. It could even be easier on the programmer, though harder on the computer, just to do a complete sum of all the forces. – Valer

Have you asked this question on the Game Development SE site also? – Germanium

@Valer I set out to have fully integrated ship motion, taking influence from all bodies and using long duration gradual acceleration. However, I also want to be able to predict arrivals/misses at destinations, both for a player aid and for AI ships to be able to reliably travel. The only way to predict that is actually projecting positions ahead of time. Planet positions could be cached to be used by several ships, but each ship would need to use small enough steps to be reliable and far enough be useful for each considered course change. I thought that would be too expensive and [1/2] – Assignment

@Valer ultimately I decided predictability and reliability was more important for me than full realism. NASA have used the patched-conic approximation in preliminary navigation, also Lambert's Problem and Huffman Transfers, each which make different assumptions (single attraction, instant acceleration & circular orbiting planets, respectively) that are often negligible or correctable mid-flight. I hoped that however many position-at-time calculations I have to do would end up costing less than projecting. I could be wrong about that though. [2/2] – Assignment

@Germanium I haven't, but probably should. I asked here as it had a larger population and the problem wasn't isolated only to the domain of games. They could well have some insight, I should cross post it there. – Assignment

Can you send me your e-mail; I have a bunch of papers on this very subject (my e-mail is shown on my SO page) – Smother

I can't see your email on your profile page, but I think mine is listed on my profile. – Assignment

So, have you solved the problem? What about your game, have you moved it to the logical end? Is there an opportunity to see the result? – Chetchetah

Answer 1

Use radial collision detection (circles), with one circle representing the planet's gravity influence (will be larger than the planet itself), another circle for each ship, and cause the center point of each circle to move toward each other in a straight line ever so slightly as the distance decreases.

Apply the amount of pull each circle has to the rate of movement of each ship. Movement can be done with just simple trig, cos() for x, sin() for y, no need for any more complex math. When the distance between any two objects is less than the sum of their radii, then a collision has occurred.

But when doing this form of collision on just the "gravity circles", so to speak, when they collide, you can increase the speed of the ship by a small amount every iteration to simulate the pull of gravity.

Lolanthe

I'm not sure I understand what you're suggesting. Certainly they can both be represented by circles, the planets influence is a circle in my 2D case, but I don't follow the "moving towards each other ... ever so slightly as the distance decreases" part? Then you seem to explain a way to simulate gravity in circular motions? Using just cos and sin? I have no problems currently simulating gravity, that wasn't the question. – Assignment

I was trying to address your question, "Or are there other ways to predict encounter/collision between what is effectively a point moving along a conic path and a circle moving along an ellipse sharing a focal point." May not have been an approach you were looking for but the term "hobby game" led me to believe you might consider a more straightforward suggestion rather than a complex one. Is conical really the best word to describe the pull of gravity in 2D? It is more of a spiral movement. – Lolanthe

No, conical is it in 2D and 3D. Kepler did better work at showing it than I can. It could be a spiral if the ship was providing it's own acceleration as well as the acceleration from gravity. It may be primarily hobby, but my goal is simulating celestial mechanics as much as possible. – Assignment

Answer 2

You could try constructing the function describing the (square of the) distance between the planet and the ship as a function of time, using the usual Pythagoras distance expression. You are looking for zeros of this function, so Newton's method or similar can be applied to find them.

This should work well provided that the planet's motion is much slower than the ship's -- then the function will be relatively smooth, and Newton's method will have no trouble converging. However if the planet's motion is much faster than the ship's, then this distance function will bounce up and down, like a "spring" superimposed on some parabola-like curve, and will possibly intersect the x axis several times. Newton's method can have trouble with such functions, where the derivative changes direction rapidly.

Hopefully some terms will cancel out when you construct the distance function, or the expression can be otherwise simplified or approximated, but if not it may be sufficient to look for zeros in the vertical and horizontal directions. (You could in fact choose distances along any axis -- e.g. the major axis of the planet's orbit.) Zeros in either of these functions are necessary but not sufficient conditions for collision, and may be simpler to calculate. If you have a list of x-direction zeros sorted by time and the same for y-direction zeros, you can find any true collisions by calculating their intersection with a list merge (a la mergesort).

Moira

Zero's in that function would be the points where the ship intercepted the centre of the planet? I'd be looking for points on the function where distance (squared) equalled radius of influence (squared). For ships travelling in system, (eg Luna(or higher) to Low Earth Orbit Station), the target could well orbit several times creating that kind of spring. Also, Newton's Method is already used in getting the position at time for each body, so would mean you couldn't make a function that represented the distance between the two with respect to time? – Assignment

I had oversimplified by modelling the distance as being between 2 points; if the "gravitational sphere of influence" is a sphere (i.e. a circle in 2D) then the distance we actually want to calculate is the shortest distance between a point (the ship) and a circle (the GSI). Happily this is a very simple adjustment: just subtract the radius of the GSI from the distance between the planet's centre and the ship! :) (This will give you a "signed" distance when the ship is inside the GSI, but we don't care because we're only looking for zeros.) I didn't understand your last sentence I'm afraid. – Moira

To get a function of distance between the planet and ship over time you would have something like f(t) = s(t) - p(t), and as you said, terms would hopefully cancel. In getting position you need the true anomaly, to get that at time you need to get the eccentric anomaly from the mean anomaly (which is the only aspect of the orbit which changes consistently with time). The equation for eccentric anomaly is M = E - e*sin(E), which doesn't have a closed form solution. So for each s(t) & p(t) you need to numerically solve that equation, as such I don't know how you'd define f(t). – Assignment

Answer 3

Since this hasn't got an accepted answer yet and I don't see the below calculations I'll add these in the hopes that it will help someone. I've not figured out how to get a date time, I have however figured out how to get angles. This will get you the distance between the orbiting body and the soi (or ship) if you know the angle:

public static double RadiusAtAngle(double angle, double semiLatusRectum, double eccentricity)
{
    return semiLatusRectum / (1 + eccentricity * Math.Cos(angle)); 
}

More importantly, flipping that calc gets you the angle to the soi edge if you know the semiLatusRectum and the eccentricity (radius here will be the distance from the body to the soi edge):

public static double AngleAtRadus(double radius, double semiLatusRectum, double eccentricity)
{
    //r = p / (1 + e * cos(θ))
    //1 + e * cos(θ) = p/r
    //((p / r) -1) / e = cos(θ)
    return Math.Acos((semiLatusRectum / radius - 1) / eccentricity);
}

For reference, semiLatusRectum can be found from the semiMajorAxis and eccentricity:

public static double SemiLatusRectum(double SemiMajorAxis, double eccentricity)
{
    if (eccentricity == 0)//ie a circle 
        return SemiMajorAxis;
    return SemiMajorAxis * (1 - eccentricity * eccentricity);
}

Note that these calcs will also work for hyperbolic trajectories.

Shirk

I asked a different question about the same problem and got an answer there: #16501682 I never really made a game out of it, but the encounter prediction logic worked well though all my testing. Might not be cheap enough to run during frames in a game, never got far enough to determine that. I still plan to clean it up and post it online, but life keeps getting in the way. – Assignment

Interesting, if you've still got the C# conversion around for that I'd love to take a look, the pastbin link is now dead. – Shirk

It seems the pastebin I posted the last time someone asked expired. I should post it properly somewhere. – Assignment