Intro

Back in Uni me and two other students worked on a Space Shooter.
In it you fly a space ship and get to shoot other space ships with projectile-based weaponry. As part of the UI we added indicators for where the player has to aim for the shots to hit the other ships.

This however leads to the big question: Where does the player have to shoot for the projectile to land?

This article aims to explain a solution based on basic linear algebra, as well as the path and thinking that lead to it.

Defining the Problem

In the Intro Segment I presented a high-level overview of what the here described hit prediction is trying to achieve. Let’s try to quantify what the hit prediction has to achieve, what it has to work with, and the environment it has to act in.

We want to be able to show the player where they have to shoot for a projectile to hit — assuming that the target does not change speed or direction. For this, we need to know where an impact would take place.

We work in a 0G dragless environment. This means that an object’s direction will not change over time. If a projectile is moving at $200\frac{\text{units}}{\text{second}}$, it will continue to do so until it expires.

Another rule of the environment is that projectiles inherit the momentum of the firing ship.
If a ship moving forward at $100\frac{u}{s}$ shoots the same $200\frac{u}{s}$ projectile forward, the projectile will be travelling at $300\frac{u}{s}$. Conversely, if the ship were the shoot the projectile “backwards”,it would travel at a total of $100\frac us$.

We have our own and enemies position and direction, as well as our weapon’s projectile speed to work with.
From the position and direction we can calculate a position at a given time using the following formula.

$\Large \vec{p}(t)=\vec{p_0}+\vec{v} \cdot t$

In short, you get the position at a given time ( $\vec{p}(t)$ ) by taking the current position ( $\vec{p_0}$ ) and adding the current direction ( $\vec{v}$ ) by the time travelled ( $t$ ) to it.

However, while this is part of the solution, it is not the important piece to the puzzle.

Simplifying the problem

First of all, while we do want to find where the collision takes place, we do not need to find it immediately. As mentioned earlier, we can infer the position at a given time using the starting position and direction. So we can spare loads of headaches by not trying to find out where, but when a collision would take place.

To find a collision we would have to try and “shoot” many projectiles and see if they ever collide with the target. This is, however, not very feasible. Instead, we can abstract away the projectile altogether.

If you think about, if you were to shoot many projectiles into all directions at the same time, you would be left with something like a circle expanding from your spaceship.

Hit Detection

From here, collision detection is fairly easy.

Simple Example: No Movement

Assuming both shooter and target are stationary, we can get the time of collision with the following formula:

$$\Large \begin{aligned} |p_\text{shooter} - p_\text{target}| - t \cdot v_{projectile} &= 0 \\ |p_\text{shooter} - p_\text{target}| &= t \cdot v_{projectile} \\ \frac{|p_\text{shooter} - p_\text{target}|}{v_{projectile}} &= t \\ \\ \end{aligned}$$

An Example:

$$p_\text{shooter}:= \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} p_\text{target}:= \begin{pmatrix} 9 \\ 8 \\ 7 \end{pmatrix} v_\text{projectile} := 10\\\\ \begin{aligned} |p_\text{shooter} - p_\text{target}| - t \cdot v_{projectile} &= 0 \\ \sqrt{(1-9)^2+(2-8)^2+(3-7)^2} &= t \cdot 10 \\ \frac{\sqrt{116}}{10} &= t \\ 1.077 &\approx t \end{aligned}$$

For a projectile that flies at $10\frac{u}{s}$ it takes about 1.077 seconds to get a collision if starting at $p_\text{shooter}$ and trying to hit $p_\text{target}$. So far, nothing special. We just divide the distance between the two positions by the projectile speed.

Stationary shooter and moving target

For moving targets we simply have to insert the target’s position at a given time into the fuction. In short, $|p_\text{shooter}-p_\text{target}|$ needs to be changed to $|p_\text{shooter}-p_\text{target}(t)|$.

To be able to infer the position at a given point in time we need the target’s movement direction ( $\vec{s}$ ).

To keep the formula short, I am changing $p_\text{shooter}-p_\text{target}$ (vector defining the difference between the two) to be $P$.

Let’s define a distance Function to return the distance between shooter and target at a given time $t$. It accepts 2 vectors: the difference between shooter and target, $P$, and the target’s movement direction $\vec{s}$, as well as time $t$.

$$\Large dist(t, \vec{P}, \vec{s}) = \sqrt{(P_x+s_{x}·t)^2 + (P_y+s_{y}·t)^2 + (P_z+s_{z}·t)^2}$$

Adding the previous segments, we get $dist(t, \vec{P}, \vec{s}) = t \cdot v$, or $dist(t, \vec{P}, \vec{s}) - t \cdot v = 0$.

Telling WolframAlpha to resolve against $t$ leaves us with these two solutions:

$$t_{1,2} = \frac{ 2P_x s_x + 2P_y s_y + 2P_z s_z \pm \sqrt { (-2P_x s_x - 2 P_y s_y -2 P_z s_z)^2 - 4 (-P_x^2 - P_y^2 - P_z ^2)(-s_x^2 -s_y^2 -s_z^2 + v^2) } }{ 2(-s_x^2-s_y^2-s_z^2+v^2) }$$

I have cleaned up the formula a little bit:

$$t_{1,2} = \frac{ 2(P_x s_x + P_y s_y + P_z s_z) \pm \sqrt { (-2(P_x s_x + P_y s_y + P_z s_z))^2 - 4 (P_x^2 + P_y^2 + P_z ^2)(s_x^2 + s_y^2 + s_z^2 - v^2) } }{ -2(s_x^2+s_y^2+s_z^2-v^2) }$$

And with this formula, we can find out when a projectile were to hit the moving target.
Let’s adapt the example from the previous segment and use
$\vec{s} = \begin{pmatrix} 12 \\ -6 \\ 2 \end{pmatrix};\vec{P} = \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} - \begin{pmatrix} 9 \\ 8 \\ 7 \end{pmatrix} = \begin{pmatrix} -8 \\ -6 \\ -4 \end{pmatrix}$

To keep things from getting too hard to grasp, I will first just resolve the square root for now.

$$\begin{aligned} \text{temp}&=\sqrt { (-2(P_x s_x + P_y s_y + P_z s_z))^2 - 4 (-P_x^2 + P_y^2 + P_z ^2)(-s_x^2 + s_y^2 + s_z^2 - v^2) } \\ &= \sqrt { (-2([-8\cdot12] + [-6\cdot-6] + [-4\cdot2]))^2 - 4 ((-8)^2 + (-6)^2 +(-4)^2)(12^2 + (-6)^2 + 2^2 - 10^2) } \\ &= \sqrt { (-2(-96 + 36 -8))^2 - 4 (64 + 36 + 16)(144 + 36 + 4 - 100) } \\ &= \sqrt { (136)^2 - 4 (116)(84) } \\ &= \sqrt { 18496 - 38976 } \\ &= \sqrt { -20480 } \rightarrow \text{no solution} \end{aligned}$$

And a look at that! A negative value inside the root. This is an edge case and means that the function has no return value. The ship’s movement speed for this example is rather quick at $|\vec{s}| \approx 13.56$, which is quicker than $v = 10$.

The target is effectively outrunning any projectile that would be shot in the given scenario. As a result, the function does not have any solutions. Do keep in mind however that under certain circumstances this can still yield a result (read: when the target is flying towards the shooter).

Let’s retry with $v=20$.

$$\begin{aligned} \text{temp}&=\sqrt { (-2(P_x s_x + P_y s_y + P_z s_z))^2 - 4 (-P_x^2 + P_y^2 + P_z ^2)(-s_x^2 + s_y^2 + s_z^2 - v^2) } \\ &= \sqrt { (-2([-8\cdot12] + [-6\cdot-6] + [-4\cdot2]))^2 - 4 ((-8)^2 + (-6)^2 +(-4)^2)(12^2 + (-6)^2 + 2^2 - 20^2) } \\ &= \sqrt { (-2(-96 + 36 -8))^2 - 4 (64 + 36 + 16)(144 + 36 + 4 - 400) } \\ &= \sqrt { (136)^2 - 4 (116)(-216) } \\ &= \sqrt { 18496 + 100224 } \\ &= \sqrt { 118720 } \\ &\approx 344.55 \\ \\ t_{1,2} &= \frac{2([-8\cdot12]+[-6\cdot-6]+[-4\cdot2]) \pm 344.55}{-2(12^2+(-6)^2+2^2-20^2)}\\ t_{1,2} &= \frac{2(-68) \pm 344.55}{-2(-216)}\\ t_{1,2} &= \frac{-136 \pm 344.55}{432}\\ t_1 &= \frac{-136 + 344.55}{432} \approx 0.48; t_2 = \frac{-136 - 344.55}{432} \approx -1.11 \end{aligned}$$

And here’s the result, $t\approx 0.48$. We can ignore the second result here as it is in the past. $t$ can now be inserted into $p_\text{target}(0) + s_\text{target} \cdot t$ to get:

$$p_\text{target}:= \begin{pmatrix} 9 \\ 8 \\ 7 \end{pmatrix}; s_\text{target}:= \begin{pmatrix} 12 \\ -6 \\ 2 \end{pmatrix}\\ p_\text{target}(t=0.48) = \begin{pmatrix} 9 \\ 8 \\ 7 \end{pmatrix} + \begin{pmatrix} 12 \\ -6 \\ 2 \end{pmatrix} \cdot 0.48 = \begin{pmatrix} 14.76 \\ 5.12 \\ 7.96 \end{pmatrix}$$

An that’s the point of collision. You can simply overlay a lead reticle on the hud pointing towards that position. And because the shooter’s ship is stationary, you do not have to account for the projectile’s momentum.

Moving shooter and target

During gameplay, however, the shooter will not be stationary. We could try to expand the afforementioned formula even further to account for a moving shooter; but that won’t be necessary as we can use a simple trick to be able to reuse the formula above: Changing the frame of reference.

Unity (and I assume many other game engines) have the concept of world space and local space. World space defines positions, rotations, and so on relative to a defined, static origin. In contrast, local space defines everything in relation to an object.

The local position of an object in its own local space is always the zero-length vector $\vec{0}$. We can construct a new coordinate system that uses the position and velocity of our shooter as the origin. This way, in our new coordinate system, the shooter is effectively standing still and we do not have to account for momentum.

Here is what the conversion will look like:

$$\Large \begin{aligned} \vec{p}_\text{local} &= \vec{p}_\text{world} - \vec{p}_\text{shooter} \\ \vec{s}_\text{local} &= \vec{s}_\text{world} - \vec{s}_\text{shooter} \end{aligned}$$

If you insert the shooter into the equasion we get $\vec{0}$ for both position and movement direction:

$$\begin{aligned} \vec{p}_\text{local} &= \vec{p}_\text{shooter} - \vec{p}_\text{shooter} &= \vec{0} \\ \vec{s}_\text{local} &= \vec{s}_\text{shooter} - \vec{s}_\text{shooter} &= \vec{0} \end{aligned}$$

Let’s take the example from above and assume that our own ship has the following movement vector $\vec{s}_\text{shooter} = \begin{pmatrix} 2 \\ 3 \\ 4 \end{pmatrix}$

$$p_\text{shooter}:= \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix}; s_\text{shooter}:= \begin{pmatrix} 2 \\ 3 \\ 4 \end{pmatrix}; p_\text{target}:= \begin{pmatrix} 9 \\ 8 \\ 7 \end{pmatrix}; s_\text{target}:= \begin{pmatrix} 12 \\ -6 \\ 2 \end{pmatrix} \\$$ $$\Large \begin{aligned} p_{\text{target}_\text{local}} &= p_{\text{target}_\text{world}} - p_{\text{shooter}_\text{world}} \\ &=\begin{pmatrix} 9 \\ 8 \\ 7 \end{pmatrix} - \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} =\begin{pmatrix} 8 \\ 6 \\ 4 \end{pmatrix} \\\\ s_{\text{target}_\text{local}} &= s_{\text{target}_\text{world}} - s_{\text{shooter}_\text{world}} \\ &=\begin{pmatrix} 12 \\ -6 \\ 2 \end{pmatrix} - \begin{pmatrix} 2 \\ 3 \\ 4 \end{pmatrix} =\begin{pmatrix} 10 \\ -9 \\ -2 \end{pmatrix} \end{aligned}$$

And from here on you simply use the method defined in Stationary shooter and moving target. Your ship is, in your new local coordinate system, no longer moving and conveniently placed at the origin, which means that $P = p_{\text{target}_\text{local}}$.

Reference Implementations

As promised, some basic reference implementations in some languages to copy-paste from :)

• JS/TS
• Python
• Rust

Reference Implementation: JS/TS

type Vec3 = [number, number, number];

/**
 * Run an operation on a per-component basis, return the result as a new vector
 */
function vec3Operate(
  a: Readonly<Vec3>,
  b: Readonly<Vec3>,
  operation: (componentA: number, componentB: number) => number
) {
  const [ax, ay, az] = a;
  const [bx, by, bz] = b;
  return [operation(ax, bx), operation(ay, by), operation(az, bz)] as const;
}

function vec3Sum(a: Readonly<Vec3>) {
  return a[0] + a[1] + a[2];
}

function getTimeOfCollision(
  shooterPos: Vec3,
  shooterDir: Vec3,
  targetPos: Vec3,
  targetDir: Vec3,
  projectileSpeed: number
) {
  const localTargetPos = vec3Operate(targetPos, shooterPos, (a, b) => a - b);
  const localTargetDir = vec3Operate(targetDir, shooterDir, (a, b) => a - b);

  const rootLeftSegment =
    -2 * vec3Sum(vec3Operate(localTargetPos, localTargetDir, (a, b) => a * b));
  const rootRightSegment =
    -4 *
    vec3Sum(vec3Operate(localTargetPos, localTargetPos, (a, b) => a * b)) *
    (vec3Sum(vec3Operate(localTargetDir, localTargetDir, (a, b) => a * b)) -
      projectileSpeed * projectileSpeed);
  const rootValue = rootLeftSegment * rootLeftSegment + rootRightSegment;

  if (rootValue < 0) {
    return undefined;
  }

  const root = Math.sqrt(rootValue);
  const bottom =
    -2 *
    (vec3Sum(vec3Operate(localTargetDir, localTargetDir, (a, b) => a * b)) -
      projectileSpeed * projectileSpeed);

  const result1 = (-rootLeftSegment - root) / bottom;
  const result2 = (-rootLeftSegment + root) / bottom;

  return [result1, result2].sort().find((e) => e > 0);
}

function getPointOfCollision(
  shooterPos: Vec3,
  shooterDir: Vec3,
  targetPos: Vec3,
  targetDir: Vec3,
  projectileSpeed: number
) {
  const t = getTimeOfCollision(
    shooterPos,
    shooterDir,
    targetPos,
    targetDir,
    projectileSpeed
  );
  if (!t) {
    return undefined;
  }
  const directionAfterTime = vec3Operate(
    targetDir,
    [t, t, t] as const,
    (a, b) => a * b
  );
  return vec3Operate(targetPos, directionAfterTime, (a, b) => a + b);
}

console.log(
  getTimeOfCollision([1, 2, 3], [1, 1, 1], [9, 8, 7], [13, -5, 3], 20)
); // 1.1124020543465936

console.log(
  getPointOfCollision([1, 2, 3], [1, 1, 1], [9, 8, 7], [13, -5, 3], 20)
); // [ 23.461226706505716, 2.4379897282670324, 10.337206163039781 ]

Reference Implementation: Python

import dataclasses
import math

@dataclasses.dataclass
class Vec3:
    x: float
    y: float
    z: float

    def sum(self):
        return self.x + self.y + self.z
    
    @staticmethod
    def operate(a, b, operation):
        return Vec3(operation(a.x,b.x), operation(a.y,b.y), operation(a.z,b.z))

    def multiply(self, b):
        return Vec3.operate(self, b, lambda a,b: a*b)
    def add(self, b):
        return Vec3.operate(self, b, lambda a,b: a+b)
    def sub(self, b):
        return Vec3.operate(self, b, lambda a,b: a-b)

@dataclasses.dataclass
class Entity:
    position: Vec3
    direction: Vec3

def get_time_of_collision(shooter: Entity, target: Entity, projectile_speed: float):
    local_target_pos = target.position.sub(shooter.position)
    local_target_dir = target.direction.sub(shooter.direction)

    root_left_segment = -2 * local_target_pos.multiply(local_target_dir).sum()
    root_right_segment = -4 * local_target_pos.multiply(local_target_pos).sum() * (local_target_dir.multiply(local_target_dir).sum() - projectile_speed**2)

    root_value = root_left_segment*root_left_segment + root_right_segment
    
    if root_value < 0:
        return None
    
    root = math.sqrt(root_value)
    bottom = -2 * (local_target_dir.multiply(local_target_dir).sum() - projectile_speed**2)

    all_results = [
        (-root_left_segment - root) / bottom,
        (-root_left_segment + root) / bottom
    ]
    all_results.sort()

    results = [f for f in all_results  if f > 0]
    if len(results) == 0:
        return None
    return results[0]

shooter = Entity(
    Vec3(1,2,3),
    Vec3(1,1,1)
)
target = Entity(
    Vec3(9,8,7),
    Vec3(13,-5,3)
)

def get_point_of_collision(shooter: Entity, target: Entity, projectile_speed: float):
  t = get_time_of_collision(shooter, target, projectile_speed)
  return target.position.add(target.direction.multiply(Vec3(t,t,t)))

print(get_time_of_collision(shooter, target, 20))
# 1.1124020543465936

print(get_point_of_collision(shooter, target, 20))
# Vec3(x=23.461226706505716, y=2.4379897282670324, z=10.337206163039781)

Reference Implementation: Rust

struct Vec3 {
    x: f32,
    y: f32,
    z: f32
}

impl Vec3 {
    fn new(x: f32, y: f32, z: f32) -> Self { Self { x, y, z } }

    fn add(self: &Self, other: &Vec3) -> Vec3 {
        Vec3::new(self.x + other.x, self.y + other.y, self.z + other.z)
    }
    fn sub(self: &Self, other: &Vec3) -> Vec3 {
        Vec3::new(self.x - other.x, self.y - other.y, self.z - other.z)
    }
    fn sum(self: &Self) -> f32 {
        self.x + self.y + self.z
    }
    fn mul(self: &Self, other: &Vec3) -> Vec3 {
        Vec3::new(self.x * other.x, self.y * other.y, self.z * other.z)
    }
}

struct Entity {
    position: Vec3,
    direction: Vec3,
}

impl Entity {
    fn new(position: Vec3, direction: Vec3) -> Self { Self { position, direction } }
}


fn get_time_of_collision(shooter: &Entity, target: &Entity, projectile_speed: f32) -> Option<f32> {
    let local_target_pos = target.position.sub(&shooter.position);
    let local_target_dir = target.direction.sub(&shooter.direction);

    let root_left_segment = -2f32 * local_target_pos.mul(&local_target_dir).sum();
    let root_right_segment = -4f32 * local_target_pos.mul(&local_target_pos).sum() * (local_target_dir.mul(&local_target_dir).sum() - projectile_speed*projectile_speed);

    let root_value = root_left_segment*root_left_segment+root_right_segment;
    if root_value < 0f32 {
        return None;
    }

    let root = f32::sqrt(root_value);
    let bottom = -2f32 * (local_target_dir.mul(&local_target_dir).sum() - projectile_speed*projectile_speed);

    let results = vec![(-root_left_segment - root) / bottom, (-root_left_segment + root) / bottom];
    let result = results.into_iter()
        .filter(|x| f32::is_sign_positive(*x))
        .min_by(|a,b| a.total_cmp(&b));
    result
} 


fn main() {
    let shooter = Entity::new(Vec3::new(1f32, 2f32, 3f32), Vec3::new(1f32, 1f32, 1f32));
    let target = Entity::new(Vec3::new(9f32, 8f32, 7f32), Vec3::new(13f32, -5f32, 3f32));

    match get_time_of_collision(&shooter, &target, 20f32) {
        Some(t) => {
            let collision_position = target.position.add(&target.direction.mul(&Vec3::new(t,t,t)));
            // Collision will take place after 1.1124021s at (23.461227, 2.4379897, 10.337206)
            println!("Collision will take place after {}s at ({}, {}, {})", t, collision_position.x, collision_position.y, collision_position.z);
        },
        None => println!("No collision can take place")
    }
}