2d game : fire at a moving target by predicting intersection of projectile and unit

Question

Okay, this all takes place in a nice and simple 2D world... :)

Suppose I have a static object A at position Apos, and a linearly moving object B at Bpos with bVelocity, and an ammo round with velocity Avelocity...

How would I find out the angle that A has to shoot, to hit B, taking into account B's linear velocity and the speed of A's ammo ?

Right now the aim's at the current position of the object, which means that by the time my projectile gets there the unit has moved on to safer positions :)

Answer 1

First rotate the axes so that AB is vertical (by doing a rotation)

Now, split the velocity vector of B into the x and y components (say Bx and By). You can use this to calculate the x and y components of the vector you need to shoot at.

B --> Bx
|
|
V

By


Vy
^
|
|
A ---> Vx

You need Vx = Bx and Sqrt(Vx*Vx + Vy*Vy) = Velocity of Ammo.

This should give you the vector you need in the new system. Transform back to old system and you are done (by doing a rotation in the other direction).

Answer 2

I wrote an aiming subroutine for xtank a while back. I'll try to lay out how I did it.

Disclaimer: I may have made one or more silly mistakes anywhere in here; I'm just trying to reconstruct the reasoning with my rusty math skills. However, I'll cut to the chase first, since this is a programming Q&A instead of a math class :-)

How to do it

It boils down to solving a quadratic equation of the form:

a * sqr(x) + b * x + c == 0

Note that by sqr I mean square, as opposed to square root. Use the following values:

a := sqr(target.velocityX) + sqr(target.velocityY) - sqr(projectile_speed)
b := 2 * (target.velocityX * (target.startX - cannon.X)
          + target.velocityY * (target.startY - cannon.Y))
c := sqr(target.startX - cannon.X) + sqr(target.startY - cannon.Y)

Now we can look at the discriminant to determine if we have a possible solution.

disc := sqr(b) - 4 * a * c

If the discriminant is less than 0, forget about hitting your target -- your projectile can never get there in time. Otherwise, look at two candidate solutions:

t1 := (-b + sqrt(disc)) / (2 * a)
t2 := (-b - sqrt(disc)) / (2 * a)

Note that if disc == 0 then t1 and t2 are equal.

If there are no other considerations such as intervening obstacles, simply choose the smaller positive value. (Negative t values would require firing backward in time to use!)

Substitute the chosen t value back into the target's position equations to get the coordinates of the leading point you should be aiming at:

aim.X := t * target.velocityX + target.startX
aim.Y := t * target.velocityY + target.startY

Derivation

At time T, the projectile must be a (Euclidean) distance from the cannon equal to the elapsed time multiplied by the projectile speed. This gives an equation for a circle, parametric in elapsed time.

sqr(projectile.X - cannon.X) + sqr(projectile.Y - cannon.Y)
  == sqr(t * projectile_speed)

Similarly, at time T, the target has moved along its vector by time multiplied by its velocity:

target.X == t * target.velocityX + target.startX
target.Y == t * target.velocityY + target.startY

The projectile can hit the target when its distance from the cannon matches the projectile's distance.

sqr(projectile.X - cannon.X) + sqr(projectile.Y - cannon.Y)
  == sqr(target.X - cannon.X) + sqr(target.Y - cannon.Y)

Wonderful! Substituting the expressions for target.X and target.Y gives

sqr(projectile.X - cannon.X) + sqr(projectile.Y - cannon.Y)
  == sqr((t * target.velocityX + target.startX) - cannon.X)
   + sqr((t * target.velocityY + target.startY) - cannon.Y)

Substituting the other side of the equation gives this:

sqr(t * projectile_speed)
  == sqr((t * target.velocityX + target.startX) - cannon.X)
   + sqr((t * target.velocityY + target.startY) - cannon.Y)

... subtracting sqr(t * projectile_speed) from both sides and flipping it around:

sqr((t * target.velocityX) + (target.startX - cannon.X))
  + sqr((t * target.velocityY) + (target.startY - cannon.Y))
  - sqr(t * projectile_speed)
  == 0

... now resolve the results of squaring the subexpressions ...

sqr(target.velocityX) * sqr(t)
    + 2 * t * target.velocityX * (target.startX - cannon.X)
    + sqr(target.startX - cannon.X)
+ sqr(target.velocityY) * sqr(t)
    + 2 * t * target.velocityY * (target.startY - cannon.Y)
    + sqr(target.startY - cannon.Y)
- sqr(projectile_speed) * sqr(t)
  == 0

... and group similar terms ...

sqr(target.velocityX) * sqr(t)
    + sqr(target.velocityY) * sqr(t)
    - sqr(projectile_speed) * sqr(t)
+ 2 * t * target.velocityX * (target.startX - cannon.X)
    + 2 * t * target.velocityY * (target.startY - cannon.Y)
+ sqr(target.startX - cannon.X)
    + sqr(target.startY - cannon.Y)
  == 0

... then combine them ...

(sqr(target.velocityX) + sqr(target.velocityY) - sqr(projectile_speed)) * sqr(t)
  + 2 * (target.velocityX * (target.startX - cannon.X)
       + target.velocityY * (target.startY - cannon.Y)) * t
  + sqr(target.startX - cannon.X) + sqr(target.startY - cannon.Y)
  == 0

... giving a standard quadratic equation in t. Finding the positive real zeros of this equation gives the (zero, one, or two) possible hit locations, which can be done with the quadratic formula:

a * sqr(x) + b * x + c == 0
x == (-b ± sqrt(sqr(b) - 4 * a * c)) / (2 * a)

Answer 3

Following is polar coordinate based aiming code in C++.

To use with rectangular coordinates you would need to first convert the targets relative coordinate to angle/distance, and the targets x/y velocity to angle/speed.

The "speed" input is the speed of the projectile. The units of the speed and targetSpeed are irrelevent, as only the ratio of the speeds are used in the calculation. The output is the angle the projectile should be fired at and the distance to the collision point.

The algorithm is from source code available at http://www.turtlewar.org/ .

// C++
static const double pi = 3.14159265358979323846;
inline double Sin(double a) { return sin(a*(pi/180)); }
inline double Asin(double y) { return asin(y)*(180/pi); }

bool/*ok*/ Rendezvous(double speed,double targetAngle,double targetRange,
   double targetDirection,double targetSpeed,double* courseAngle,
   double* courseRange)
{
   // Use trig to calculate coordinate of future collision with target.
   //             c
   //
   //       B        A
   //
   // a        C        b
   //
   // Known:
   //    C = distance to target
   //    b = direction of target travel, relative to it's coordinate
   //    A/B = ratio of speed and target speed
   //
   // Use rule of sines to find unknowns.
   //  sin(a)/A = sin(b)/B = sin(c)/C
   //
   //  a = asin((A/B)*sin(b))
   //  c = 180-a-b
   //  B = C*(sin(b)/sin(c))

   bool ok = 0;
   double b = 180-(targetDirection-targetAngle);
   double A_div_B = targetSpeed/speed;
   double C = targetRange;
   double sin_b = Sin(b);
   double sin_a = A_div_B*sin_b;
   // If sin of a is greater than one it means a triangle cannot be
   // constructed with the given angles that have sides with the given
   // ratio.
   if(fabs(sin_a) <= 1)
   {
      double a = Asin(sin_a);
      double c = 180-a-b;
      double sin_c = Sin(c);
      double B;
      if(fabs(sin_c) > .0001)
      {
         B = C*(sin_b/sin_c);
      }
      else
      {
         // Sin of small angles approach zero causing overflow in
         // calculation. For nearly flat triangles just treat as
         // flat.
         B = C/(A_div_B+1);
      }
      // double A = C*(sin_a/sin_c);
      ok = 1;
      *courseAngle = targetAngle+a;
      *courseRange = B;
   }
   return ok;
}

Answer 4

+1 on Jeffrey Hantin's excellent answer here. I googled around and found solutions that were either too complex or not specifically about the case I was interested in (simple constant velocity projectile in 2D space.) His was exactly what I needed to produce the self-contained JavaScript solution below.

The one point I would add is that there are a couple special cases you have to watch for in addition to the discriminant being negative:

• "a == 0": occurs if target and projectile are traveling the same speed. (solution is linear, not quadratic)
• "a == 0 and b == 0": if both target and projectile are stationary. (no solution unless c == 0, i.e. src & dst are same point.)

Code:

/**
 * Return the firing solution for a projectile starting at 'src' with
 * velocity 'v', to hit a target, 'dst'.
 *
 * @param Object src position of shooter
 * @param Object dst position & velocity of target
 * @param Number v   speed of projectile
 * @return Object Coordinate at which to fire (and where intercept occurs)
 *
 * E.g.
 * >>> intercept({x:2, y:4}, {x:5, y:7, vx: 2, vy:1}, 5)
 * = {x: 8, y: 8.5}
 */
function intercept(src, dst, v) {
  var tx = dst.x - src.x,
      ty = dst.y - src.y,
      tvx = dst.vx,
      tvy = dst.vy;

  // Get quadratic equation components
  var a = tvx*tvx + tvy*tvy - v*v;
  var b = 2 * (tvx * tx + tvy * ty);
  var c = tx*tx + ty*ty;    

  // Solve quadratic
  var ts = quad(a, b, c); // See quad(), below

  // Find smallest positive solution
  var sol = null;
  if (ts) {
    var t0 = ts[0], t1 = ts[1];
    t = Math.min(t0, t1);
    if (t < 0) t = Math.max(t0, t1);    
    if (t > 0) {
      sol = {
        x: dst.x + dst.vx*t,
        y: dst.y + dst.vy*t
      };
    }
  }

  return sol;
}


/**
 * Return solutions for quadratic
 */
function quad(a,b,c) {
  var sol = null;
  if (Math.abs(a) < 1e-6) {
    if (Math.abs(b) < 1e-6) {
      sol = Math.abs(c) < 1e-6 ? [0,0] : null;
    } else {
      sol = [-c/b, -c/b];
    }
  } else {
    var disc = b*b - 4*a*c;
    if (disc >= 0) {
      disc = Math.sqrt(disc);
      a = 2*a;
      sol = [(-b-disc)/a, (-b+disc)/a];
    }
  }
  return sol;
}