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

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 2

+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 ({x, y}) src position of shooter  * @param ({x, y, vx, vy}) dst position & velocity of target  * @param (Number) v   speed of projectile  *  * @return ({x, y}) Coordinate at which to fire (and where intercept occurs). Or `null` if target cannot be hit.  */ function intercept(src, dst, v) {   const tx = dst.x - src.x;   const ty = dst.y - src.y;   const tvx = dst.vx;   const tvy = dst.vy;    // Get quadratic equation components   const a = tvx * tvx + tvy * tvy - v * v;   const b = 2 * (tvx * tx + tvy * ty);   const c = tx * tx + ty * ty;    // Solve quadratic   const ts = quad(a, b, c); // See quad(), below    // Find smallest positive solution   let sol = null;   if (ts) {     const t0 = ts[0];     const t1 = ts[1];     let 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) {   let 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 {     let 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; }  // For example ... const sol = intercept(   {x:2, y:4},              // Starting coord   {x:5, y:7, vx: 2, vy:1}, // Target coord and velocity   5                        // Projectile velocity )  console.log('Fire at', sol)