Getting the cross point between a projectile and its target (or how to get the desired impact point)

Note: Should be reviewed by a native speeker

In my space game I am using unguided projectiles. So, the question is: At which point will the projectile and the target meet.

I start with the pythagorean theorem to get the desired length from projectile starting position to the desired impact point

c² = a² + b²

or in 3 dimensions

e² = x² + y² + z²

So let’s assume the following:

The target has speed: v
The projectile has speed: v2
The local coordinate (difference) is TargetPos - ProjectilePos: d

So because the projectile should head straight forward to the desired point, v2 can be a number, v has to be a vector.

What we want to calculate is the time needed t until the target and the projectile meet. All distances (e, x, y, z) can be calculated by

s = v * t

Leading us to

Projectile's len to desired pos:
e = v2 * t

Target's desired pos:
x = d.x + v.x * t
y = d.y + v.y * t
z = d.z + v.z * t

Leading us to

e² = x² + y² + z²
 
v2² * t² = (d.x + v.x * t)² + (d.y + v.y * t)² + (d.z + v.z * t)²

Using binominal formula (a + b)² = a² + 2ab + b²

v2² * t² = (d.x² + 2 * d.x * v.x * t + v.x² * t²) + (d.y² + 2 * d.y * v.y * t + v.y² * t²) + (d.z² + 2 * d.z * v.z * t + v.z² * t²)
 
v2² * t² = (v.x² * t² + v.y² * t² + v.z² * t²) + (2 * d.x * v.x * t + 2 * d.y * v.y * t + 2 * d.z * v.z * t) + d.x² + d.y² + d.z²
v2² * t² = t² * (v.x² + v.y² + v.z²) + t * (2 * d.x * v.x + 2 * d.y * v.y + 2 * d.z + v.z) + d.x² + d.y² + d.z²
0 = t² * (v.x² + v.y² + v.z² - v2²) + t * (2 * d.x * v.x + 2 * d.y * v.y + 2 * d.z + v.z) + d.x² + d.y² + d.z²

There is a formula to solve square functions (found at wiki and learned in school ages ago :-P ) with the following syntax: 0 = a * x² + b * x + c

t = (-b +- Sqrt(b² - 4 * a * c)) / (2 * a)
 
a = (v.x² + v.y² + v.z² - v2²)
b = (2 * d.x * v.x + 2 * d.y * v.y + 2 * d.z + v.z)
c = d.x² + d.y² + d.z²

Now we can calculate the time needed t very easy. After that we calculate our desired pos in world coordinates (the target is moving away from its current position v * t):

FinalPos.x = TargetPos.x + v.x * t
FinalPos.y = TargetPos.y + v.y * t
FinalPos.z = TargetPos.z + v.z * t

And that’s it. We have finally calculated the point where our projectile will hit the target if it is not changing speed or direction meanwhile.

Note: You can run into problems if your target is faster than the projectile.

Complete Delphi Function

// MovementVec is the movement vector of the target
// Speed is the velocity of the projectile
function GetCrossPoint(TargetPos, Pos, MovementVec: TV_3DVector; Speed: single): TV_3DVector;
var
  A, B, C: single;
  t: single;
  Diff: TV_3DVECTOR;
begin
  // Get the difference (local point)
  Diff := MathCalc.VSubtract(TargetPos, Pos);
 
  // Formula -> e² = x² + y² + z²
  // -> v² * t² = (x + vx * t)² + (y + vy * t)² + (z + vz * t)²
  // -> 0 = t² * (vx² + vy² + vz²) - t² * v² + t * (2x * vx + 2y * vy + 2z + vz) + x² + y² + z²
  // -> 0 =  t² * (vx² + vy² + vz² - v²) + t * (2x * vx + 2y * vy + 2z + vz) + x² + y² + z²
 
  A := Sqr(MovementVec.x) + Sqr(MovementVec.y) + Sqr(MovementVec.z) - Sqr(Speed);
  B := 2 * Diff.x * MovementVec.x + 2 * Diff.y * MovementVec.y + 2 * Diff.z * MovementVec.z;
  C := Sqr(Diff.x) + Sqr(Diff.y) + Sqr(Diff.z);
 
  // Square formula -> t = (-b +- Sqrt(b² - 4ac)) / 2a
  if A = 0 then
    Result := TargetPos
  else
  begin
    t := (- B + Sqrt(Sqr(B) - 4 * A * C)) / (2 * A);
 
    // There are 2 possible solutions for square function, we want the positive solution
    if t < 0 then
      t := (- B - Sqrt(Sqr(B) - 4 * A * C)) / (2 * A);
 
    // Time can not be negative
    if t <= 0 then
      Result := TargetPos
    else
    begin
      Result.x := TargetPos.x + MovementVec.x * t;
      Result.y := TargetPos.y + MovementVec.y * t;
      Result.z := TargetPos.z + MovementVec.z * t;
    end;
 
  end;
 
end;
 

How to use it:

var
  CrossPoint, Direction, TransformedDirection: TV_3DVector;
begin
    // My forwarding vector is (1,0,0)
 
    // Get vector by speed
    Direction := Globals.Vector3(Target.Speed / 1000, 0, 0);
 
    // Transform vector by rotation matrix
    MathCalc.TVVec3TransformCoord(TransformedDirection, Direction, Target.GetRotationMatrix);
 
    // Get the cross point
    CrossPoint := GetCrossPoint(Target.GetPosition, Projectile.GetPosition, TransformedDirection, ProjectileSpeed / 1000);
 
    // Now you can turn your projectile to the desired pos or do something else
    ...
end;
 
tutorialsarticlesandexamples/getting_the_cross_point_between_a_projectile_and_its_target.txt · Last modified: 2013/11/22 13:32