Howling Moon Software

Just about everybody who’s played a shooting game knows about leading the target. For instance, in Halo, rockets move pretty slow compared to bullets. To get good at the game, you have to learn how far ahead of your target to fire the rockets so they will run into the rocket’s path just as it gets to them.

This isn’t an easy skill to learn as a player, so how do you implement it so that AI players can do it too? It’s easiest to think of this problem in relative positions and velocities. This puts the firing point at the origin and the relative motion of the target is a line. This is of course assuming that the target isn’t changing direction or accelerating.

Because you don’t know which direction to fire the bullet in, think of it as an expanding circle of bullets in every direction instead of just a single bullet. The distance of these bullets from the gun at time t is then simply the absolute value of t times the muzzle velocity. This is good to know, because at any particular point in time we also know the position (and therefor distance to) the target. This is good! When the distance of the bullets is equal to the distance to the target we have a hit. Let’s graph the two distance equations together to see what we are dealing with. In the following graph, the target (blue line) and the bullet (red line) are moving at the same speed. The X-axis is time, and the Y-axis is the distance from the gun. The target starts to the upper left of the gun and is moving right. That is why the line dips downward.

The point where the two equations cross is the point in time where a bullet can hit the target if fired immediately and in the correct direction. However, it looks like the equations could possibly intersect in more places than one. How many times can they cross? In the example graph shown above, the bullet and target are moving at the same speed and the target is moving towards the gun. In this case there is only one intersection.

In the above graph, the bullet is moving faster than the target. No matter which way the target is moving, the bullet will be able to catch up with it and hit it. There are two intersections in this graph and one of them is in the past. How is this possible??? Well, the bullet is moving in a straight line, and for the equation to make sense, it had to have been moving through the gun at the exact time it was fired. So if you could fire a bullet backwards through time, you could hit the target. Not helpful to figure out where we need to fire without a time machine though.

In this case, the target is moving faster than the bullet and the target is moving away from the gun. The bullet is never able to catch up to the target and there is no firing solution.

In this final case, the target is moving faster than the bullet, but starts out moving towards the gun. There are two possible ways to hit the target. You can either fire the bullet towards the target and hit it as it comes towards you. You can also fire the bullet out in front of the target and let the target catch up to and hit the bullet. While somewhat humorous that this is possible, it would be rather daft. It would give the target (either a player or an AI pilot) plenty of time to change direction and avoid the bullet. In the case of a kinetic weapon, it would also decrease the relative velocity of the bullet and target so that it would do less damage anyway.

So now that we have all of these possible cases, how do you know when you can actually hit the target or not and which solution to pick? It turns out that the problem can be reduced to a simple quadtratic equation and solved with the quadratic formula. Solving it isn’t too hard, so I’ll spare the details. You end up with the following coefficients: a = Vr•Vr – Vm^2, b = 2(Vr•D), and c = D•D. Vr is the relative velocity of the gun and the target, Vm is the muzzle velocity (bullet speed), and D is the relative position of the gun and the target. For those who are unfamiliar with vector algebra, • is the dot product operator. u•v is the same as u.x*v.x + u.y*v.y+ u.z*v.z (if you are doing 3D). Changing the quadratic formula around a bit you can solve for the smallest positive time value using x=2c/(sqrt(b^2 – 4ac) – b) (wikipedia refers to this as the alternate form). However, when both solutions are negative, it will return the smallest negative solution. Here’s the C# Unity3D code we use to calculate the time of impact:

// Calculate the time when we can hit a target with a bullet
// Return a negative time if there is no solution
protected float AimAhead(Vector3 delta, Vector3 vr, float muzzleV){
  // Quadratic equation coefficients a*t^2 + b*t + c = 0
  float a = Vector3.Dot(vr, vr) - muzzleV*muzzleV;
  float b = 2f*Vector3.Dot(vr, delta);
  float c = Vector3.Dot(delta, delta);

  float det = b*b - 4f*a*c;

  // If the determinant is negative, then there is no solution
  if(det > 0f){
    return 2f*c/(Mathf.Sqrt(det) - b);
  } else {
    return -1f;
  }
}

We return a negative number when the determinant is negative (not solvable). This works out well because it will also return a negative number when there are two solutions and both are negative. The code that uses the value can simple check if it’s negative to mean that there is no solution.

So now we know everything we need to know except where to aim the bullet at. We started out with the assumption that we could fire out an infinite number of bullets in every direction around a circle and that one of them would hit the target. The only bullet that actuall will hit the target is the one that is aimed at the spot where the target will be at the time of the collision, and because we are assuming that the target moves in a straight line, this is easy to solve for:

// Find the relative position and velocities
Vector3 delta = target.position - gun.position;
Vector3 vr = target.velocity - gun.velocity;

// Calculate the time a bullet will collide
// if it's possible to hit the target.
float t = AimAhead(delta, vr, muzzleV);

// If the time is negative, then we didn't get a solution.
if(t > 0f){
  // Aim at the point where the target will be at the time
  // of the collision.
  Vector3 aimPoint = target.position + t*vr;

  // fire at aimPoint!!!
}

Now you should know everything that you need to implement leading a target for the AI in your own games!