Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am creating a 2D game in which two space ships, orbiting around a planet under the influence of gravity, fire projectiles at each other, which are also under the influence of gravity.

I'm creating an AI for this game that needs to compute the trajectory its bullet should have in order for the bullet orbit the planet and eventually hit its enemy.

If we assume that the velocity of the bullet and space ship are constant, the problem is very simple, there are tons of pages out there on how to lead a target, and I have implemented that target-leading algorithm in my game, but the bullet moves slow enough that by the time it reaches where the enemy space ship would have been, both the bullet and spaceships' velocity have changed due to gravity.

My first idea was that the ship and bullet would be moving in an ellipse. I decided to look up the parametric equation for an ellipse, setting the X and Y functions equal to themselves, where the left side has the constants for the bullet's ellipse, and the right side has constants for the enemy's ellipse, and solving each equation for T, but I got lost there, and that won't cover parabolas and hyperbolas if the bullet or enemy reaches escape velocity.

So, my question: Assuming the planet is centered at the origin and doesn't move, given my spaceship's position/velocity, the enemy spaceship's position/velocity, the mass of the bullet, and the speed that the bullet will be launched from my ship (not including the velocity of the ship itself), how do I calculate a normalized vector representing the direction my ship should fire so that it hits the enemy?

It's ok if there are certain situations where it's impossible to hit the enemy - in those situations my ship can either not fire, or revert to the "constant velocity" formula.

I'm sure there will be multiple (potentially infinite) solutions, i'm interested in the solution that will occur soonest.

It's ok to ignore the possibility that the bullet hits the planet when computing which direction to fire in - once the direction is computed, i just need a way to check if the bullet's trajectory hits the planet before it hits the enemy. If it does, my ship just won't fire. If it's very simple to find multiple solutions that's a possibility, but it's not at all a priority.

share|improve this question
    
Somewhat related (but not a duplicate): math.stackexchange.com/questions/139730 –  joriki Oct 1 '12 at 6:47
    
You don't need the masses of the objects; they cancel out as long as you're only dealing with gravitational forces. –  joriki Oct 1 '12 at 7:14
    
Removed the mentions to mass –  Elliott Oct 1 '12 at 7:30

1 Answer 1

I doubt that you'll find anything better than a messy numerical solution. I'd write one of the ellipse equations in implicit form,

$$ \frac{x^2}{a_1^2}+\frac{y^2}{b_1^2}=1\;, $$

the other in parametric form,

$$ \begin{align} x&=x_0+a_2\cos\alpha\cos\phi+b_2\sin\alpha\sin\phi\;,\\ y&=y_0-a_2\sin\alpha\sin\phi+b_2\cos\alpha\cos\phi\;, \end{align} $$

then substitute the parametric one into the implicit one and solve for the parameter $\phi$. Bringing terms proportional to $\sin\phi$ to one side, squaring and using $\sin^2\phi=1-\cos^2\phi$ yields a quartic equation for $\cos\phi$. You can solve that either numerically or with the known complicated explicit formulas. Then you can determine when the bullet first crosses the other ship's path (the desired solution will always hit the ship upon first crossing its path), and by how much it misses the ship.

That gives you the deviation as a function of the angle at which the bullet is fired, and you can find the root(s) of that function using any well-known one-dimensional root-finding algorithm that doesn't require analytic derivatives, e.g. Brent's method.

P.S.: Actually it's straightforward to find the derivative of $\phi$, so you can use Newton-Raphson for finding the root if you want. I'll denote derivatives with respect to the angle at which the bullet is fired by a prime. Let the first equation describe the ship's ellipse, which is fixed. Then differentiating the first equation yields

$$ \frac{xx'}{a_1^2}+\frac{yy'}{b_1^2}=0\;. $$

In the second equation, everything depends on the angle. Differentiating the second equation yields $x'$ and $y'$ as linear functions of $\phi'$ whose coefficients are all known (though slightly cumbersome to calculate), so substituting into the differentiated first equation yields a linear equation for $\phi'$. Then calculating the derivative of the deviation from that should be rather straightforward. It's quite a hassle though, so it's only worth it if you need the improved convergence. Also you may have to first get close to the solution with a more robust method before switching to Newton-Raphson.

share|improve this answer
    
Hi, thanks for the response. I think I might not completely understand your answer - I know how to find the ellipse of the ship in implicit form, but for the formula of the bullet, I don't know several of the variables that it seems like I need to know. for example, the time (α), the axes (a2, b2). both of these rely heavily on what direction the projectile is fired in, don't they? Or do they cancel out somewhere? –  Elliott Oct 3 '12 at 22:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.