Hitting a moving target with an accelerating missile

The last few days I spent quite some time solving this problem. My first idea was, that I could just calculate the time the missile needs to travel to the target at maximum acceleration. With this time I can predict the new position of the target and aim toward that point with the missile. It is clear that this is not very accurate, but I thought that it is accurate enough.  Have a look how this worked:


Hitting a moving target with an accelerating missile on Vimeo.

The stupid missile in the first part of the video uses the approach I described. On the moving target it performs well, if the missile has no start velocity. But if you do add a start velocity, it gets really bad. You can see this better on the none moving target. The missile does move in an orbit around its target, because it will always accelerate towards the target.
So how does the smart missile work? Luckily I have a brother who studies physics and he explained me patiently how I can solve this (if you are not interested in the math you can download the code here and use it as a black box in your game or what ever you are programming).

The Math behind it:
In 2D space the target is at position X at the time t (d = distance to missile, v0 = velocity of the target):

For the missile the equation looks like this (w = start velocity missile, a = acceleration missile):

The missile hits the target if both equations return the same position in space x:

To get a solution that fulfills the equation we have to use the quadratic formula (replaced vectors with the vector components - index i can be set to x or y) :


The missile and target are at the same position if :



(k = length of acceleration vector)
Now we want to know which value of the angle alpha fulfills the equation. Sadly, we cant easily calculate the angle, but have to use an approximation method. I used Newton's method because I knew it already from school. The problem is, that we have four equations that have to be checked (plus-plus, plus-minus, minus-plus, minus-minus). So we have to use newton four times and look which of the four solution is the best. For newtons method you also need to derive the above equation (used wolfram alpha for this). Writing the derivate down in code was a pain. Newtons method on the other side is very easy to implement:

delegate float Function(Vector3 velocityDiff, Vector3 distance, 
                        float acceleration, float phi);

static float SolveWithNewton(Function function, Function derivative, 
                             Vector3 v, Vector3 d, float a, 
                             float startPhi, int numIterations)
{
    float phi = startPhi;
    for (int iteration = 0; iteration < numIterations; iteration++)
    {
        // precalculate values that are needed in the function and the derivative, 
        // so that we calculate them only once
        cosPhi = (float)Math.Cos(phi);
        sinPhi = (float)Math.Sin(phi);
        tanPhi = (float)Math.Tan(phi);
        vxQuad = v.X * v.X;
        vyQuad = v.Z * v.Z;
        insideRootVx = vxQuad + 2 * a * d.X * cosPhi;
        insideRootVy = vyQuad + 2 * a * d.Z * sinPhi;
        if (insideRootVx > 0) rootVx = (float)Math.Sqrt(insideRootVx);
        if (insideRootVy > 0) rootVy = (float)Math.Sqrt(insideRootVy);

        float functionValue = function(v, d, a, phi);
        float gradient = derivative(v, d, a, phi);
        phi = phi - functionValue / gradient;

        if (float.IsNaN(phi) || Math.Abs(functionValue) < Epsilon) break;
    }
    return phi;
}

Performance:
Right now I calculate the angle for the missile every frame and use maximal eight iterations in Newton's method. Worst case this means 24 iterations, because we have to test all four possible sign combinations. In every iteration we have at least one Sin, Cos, Tan, Sqrt and a few multiplication/division calculations. On my machine (Quad Core Q9300) this works fine (tested with circa 40 missiles). But I cant recommend this, especially on the Xbox with XNA where the floating point performance isn't that great (but I haven't tested it). The good news is, that you don't have to calculate the angle every frame. Its enough to calculate it every time the velocity of the target changes.