Tosos Game Project

Recently, Quadgnim, on the Unity 3d forums, asked me if I could help him figure out how the code for leading a target would work.  I thought about it for a minute, and then thought about it for a few more minutes.  And now after several hours, I’ve decided it was one of the more fun derivations I’ve done in a while.  So I’m going to share.

First, I’ll lay out the problem.  Consider a sniper, “A” and a target, “B”.  Sniper A is stationary and trying to track a target who is moving, for simplicity at some fixed speed in some arbitrary 3-dimensional direction.  Sniper A wants to fire on B, but if he fires where he sees B, then by the time the bullet arrives, B may have moved out of the way.  So the Sniper must aim at where B will be when the bullet get there.

Here’s a picture of the situation.

A fires on B with the solid red line. But B has moved to the dotted position B prime. A should have fired with the dotted red line.

This would be very simple if B were moving directly toward A or directly away from A.  Then we could either subtract or add that speed to our projectile speed and solve.  But we must concern ourselves with the perpendicular speed as well.  So where do we start?

In order to solve this, we must find a missing variable.  We know all the variables except time, that is the time at which our projectile will hit the target if we aimed properly.  Technically we don’t know where to aim, but if we knew the time, then because B is moving at a steady velocity we would just aim at B’s position plus the distance he travelled over that time, that looks like this

, where is B’s position and is B’s velocity.

So all we need to do is find the and plug it into that equation and that’s where we know B will be and thus where Sniper A should aim.

But how do we actually solve this?  Well, let’s start with the naive approach: Lets just fire directly at B and solve for that .  That’s pretty straight forward, we just need to find the distance from Sniper A to Target B and then divide by the speed of the projectile.  That looks like this:

where and are A and B’s positions and is the speed of the projectile.

But the problem here is that we’ve missed the target by .   Now we could take the approach that we find an initial this way, call it and then use that to compute a new and find a .  That would look like this:

We can continue to iterate this recurrence relation this way, finding and so on.  This is a pretty good way to solve a non-linear problem like this, if we don’t know of a closed form solution.  We just keep iterating until, if we’re lucky, we get a converged value, a .

First find the time it takes to reach B0, then compute how far B has moved to B1. Re run the algorithm using B1 to find B2 and so on.

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 and 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 that we want, so let’s plug that in to both sides of the equation.

So, now we can’t easily find a solution for 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 out of the way.

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.

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).

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

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

That’s pretty close, but we can do one more simplification on those last three terms , that’s just a binomial.  I remembered one shortcut.  Yay!

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 .  But we recognize that’s the square magnitude of , so really we have .  This also works for the third term, which becomes .

The second term,

,

if we look closely, is a dot product between the vector and the vector , which becomes .

So putting it all back together we’ve got,

And then pulling the over, we finally have a quadratic equation.

Finally, we can compute a solution as follows, using

,

,

.

and plug them into

We’ll get two solutions for .  One will be negative value of .  We can see this as the point in the past where if the Target B, shot at the Sniper A then the projectile would have just now arrived.  But what we care about is the future where Sniper A fires at Target B, so we just need to find larger than 0.   And we’re able to write out the code.

public float projectileSpeed;

Vector3 CalculateLead () {
  Vector3 V = targetVelocity;
  Vector3 D = target.position - sniper.position;
  float A = V.sqrMagnitude - projectileSpeed * projectileSpeed;
  float B = 2 * Vector3.Dot (D, V);
  float C = D.sqrMagnitude;
  if (A >= 0) {
    Debug.LogError ("No solution exists");
    return target.position;
  } else {
    float rt = Mathf.Sqrt (B*B - 4*A*C);
    float dt1 = (-B + rt) / (2 * A);
    float dt2 = (-B - rt) / (2 * A);
    float dt = (dt1 < 0 ? dt2 : dt1);
    return target.position + V * dt;
  }
 }

Going back to the discussion of impossible cases we see that in .  Seeing it in the bottom of the fraction, we know that if is zero this will blow up.  That happens when Target B’s velocity is the same as the projectile speed.  But looking under the square root we see that if B’s velocity is larger than projectile speed, we get imaginary results, which since we’re looking for a physical solution we want to avoid.

Finally, looking at the numerator of the quadratic solution

Lets make the following substitutions:   will be .   will be .  And we’ll replace the dot product in with .  And what we wind up with is,

Expanding under the square root we get,

And then simplifying,

Because, , we get,

Which is another binomial under the square root, giving,

Removing the square root,

Pulling out the and the extra minus sin, and put this back in with the denominator (which lets us get rid of the 2 all together).

Seeing this, our earlier intuitions about the problem pop right out.  The term represents how fast Target B is moving either directly toward or directly away from Sniper A.  The term represents how fast Target B is moving perpendicular to Sniper A.  Pull the math all the way to its final conclusion we’re able to find the patterns that make sense with our original intuition.

I love me some math.