Shooting a Moving Target

If you've ever played some sort of shooter game, you probably know about "leading the target". It doesn't matter if it's Space Invaders or some new whiz bang FPS, if the projectile takes a while to get to its target, you have to aim ahead a bit in order to hit it. This takes a little practice to learn as a player, so how do you implement it for an AI?

The first thing to do is to simplify the problem. While both the player and the target may be moving, we only care about the relative movement and position of the target to the player. You can remove even more variables by considering only distances instead of positions. When you fire the projectile, it will be at a certain distance at a certain time. Assuming you fired in the correct direction, if the target is also at that same distance at that same time, then you will be able to hit the target. So if we can figure out when the projectile could hit the target, then we can easily figure out where it will be, and aim at that spot.

Let's start with some examples to explore the problem a bit. In the following graphs, the x-axis is time, and the y-axis is distance from the player. The orange line is the target. In this case it's moving straight at the player. At 2 seconds, it passes them and then starts moving away instead. The other lines are projectiles where the purple one is a fast one, and the blue one is slow. The purple line crosses the orange line once at ~0.7 seconds. That's when the purple projectile would hit it if it was fired straight at the target. Something curious happens with the blue projectile since it's moving slower than the target (its slope is less). You can fire it straight at the target and hit it at ~1.7 seconds, or fire it the other way and let the target catch up and run into it at 2.5 seconds. Interesting, but you don't really want to do that since it gives the target almost an extra second to swerve and avoid it.

Most targets won't be moving straight at something that is shooting at them. They might be moving away from the player, or if they are moving towards the player they will probably pass close by, but not hit them. In that case, the nice orange V above turns into something a little more interesting, a hyperbola.

Now the blue projectile will never be able to hit the target no mater what direction it's fired in. The target never gets close enough for the blue projectile to reach it, and once it passes the minimum distance and starts moving away the slow moving projectile will never be able to catch up. So if the target is far enough away, or moving fast enough, it might not be possible to hit it.

So in the general case to find the time when a projectile will hit a target, you need find the intersection of a line against a hyperbola. Since there can be two solutions, you really only want the soonest one. A little vector algebra for the distance equation, and some high school algebra for the solution will get you something like this:

// delta: relative position
// vr: relative velocity
// muzzleV: Speed of the bullet (muzzle velocity)
// returns: Delta time when the projectile will hit, or -1 if impossible
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 desc = b*b - 4f*a*c;

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

Now you know if, and when a projectile could hit it's target. Figuring out where the target will be is a simple matter of (aim at) = (current target position) + (current target velocity) * (delta time).

// 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 deltaTime = AimAhead(delta, vr, muzzleV);

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

  // fire at aimPoint!!!
}

That's it! You can use this for more than just firing projectiles too. You can update the trajectory of a guided missile to intercept a target even as it tries to evade, or allow an AI ship to intercept a target. This tends to be a really neat effect as they will try to cut their target off instead of simply flying towards them or following them.