Calculating a lead on a target

However, this may not converge.  I’ll return to this because it’ll be there in any solution we find, but intuitively we can guess that it’s a case where our Target is moving as fast or faster than our Sniper’s projectile.  Of course, this wouldn’t happen when we’re talking about humans and bullets, but we may not always be talking about that.  Luckily with a recurrence relation like this, it’s easy to check if we’re converging, we simply watch the change in value between each \Delta t_k and \Delta t_{k+1} and make sure the number is getting smaller.  If it grows or stays the same, we can’t solve the problem.

public float projectileSpeed;

public float lastError = Mathf.Infinity;

Vector3 CalculateLeadIterative (Vector3 previousPrediction) {

Vector3 V = targetVelocity;

Vector3 D = previousPrediction - sniper.position;

float dt = D.magnitude / projectileSpeed;

Vector3 pos = target.position + V * dt;

float thisError = (pos - previousPrediction).magnitude;

if (thisError >= lastError) {

Debug.LogError ("No solution exists");

lastError = -1; // -1 is signaling its wrong, never should be negative

} else {

lastError = thisError; // outside code checks when this is close enough to 0.

}

return pos;

}

Here’s an example player showing this code working.

Okay, so we have a solution but it’s not really efficient.  If we could find a closed for solution, we could just plug the numbers in and get the answer back.  Maybe that’s possible.  Well let’s start with that recurrence relation we were using, but just get rid of the steps.  There’s only one \Delta t that we want, so let’s plug that in to both sides of the equation.

\Delta t = \frac{||P_b + V_b \Delta t - P_a||}{s}

So, now we can’t easily find a solution for \Delta t because its on both sides of the equation, so we have to do the hard work of seeing whether or not we can isolate it.  I’m out of practice; there’s probably a shortcut I’m missing.  In the end I’ll show the work in case there’s a mistake I’ve made along the way.

So first, I’ll move the s out of the way.

s\Delta t = ||P_b + V_b \Delta t - P_a||

Square both sides because it’s a vector magnitude over there and I want to get rid of that square root so I can pull it apart.

s^2\Delta t^2 = ||P_b + V_b \Delta t - P_a||^2

Because I don’t know a shortcut for this, I’m going to pull the vectors apart.  But for now I’m just going to look at the x component because y and z will look exactly the same and we’ll just add them back in (again because we’re inside a vector magnitude).

\ldots (P_{b,x} + V_{b,x} \Delta t - P_{a,x})^2 \ldots

Doing the work of the full squaring, we get this.

\ldots P_{b,x}^2 + 2 P_{b,x} V_{b,x} \Delta t - 2 P_{b,x}P_{a,x} + V_{b,x}^2 \Delta t^2 - 2 P_{a,x} V_{b,x} \Delta t + P_{a,x}^2 \ldots

And then pulling together the like terms, we see we’re approaching a quadratic equation on \Delta t, which is promising because solving a quadratic equation is straight forward.

\ldots V_{b,x}^2 \Delta t^2 + 2 (P_{b,x} - P_{a,x}) V_{b,x} \Delta t + P_{b,x}^2 + P_{a,x}^2 - 2P_{a,x}P_{b,x} \ldots

That’s pretty close, but we can do one more simplification on those last three terms P_{b,x}^2 + P_{a,x}^2 - 2P_{a,x}P_{b,x}, that’s just a binomial.  I remembered one shortcut.  Yay!

\ldots V_{b,x}^2 \Delta t^2 + 2 (P_{b,x} - P_{a,x}) V_{b,x} \Delta t + (P_{b,x} - P_{a,x})^2 \ldots

Okay now, we need to pull in the other components, y and z.  I’ll do this for each term, so it’s not too messy.

The first term after adding in the other components looks like (V_{b,x}^2 + V_{b,y}^2 + V_{b,z}^2) \Delta t^2.  But we recognize that’s the square magnitude of V_b, so really we have ||V_b||^2 \Delta t^2.  This also works for the third term, which becomes ||P_b - P_a||^2.

The second term,

2[(P_{b,x} - P_{a,x})V_{b,x}+(P_{b,y} - P_{a,y})V_{b,y}+(P_{b,z} - P_{a,z})V_{b,z}]\Delta t,

if we look closely, is a dot product between the vector (P_b - P_a) and the vector V_b, which becomes 2 (P_b - P_a) \cdot V_b \Delta t.

So putting it all back together we’ve got,

s^2\Delta t^2=||V_b||^2\Delta t^2 + 2(P_b - P_a) \cdot V_b \Delta t + ||P_b - P_a||^2

And then pulling the s^2\Delta t^2 over, we finally have a quadratic equation.

Page 2 of 3 | Previous page | Next page