I have been playing with target intersection prediction after I played a game called Beacon, where the enemies predict where you are going. After a bit of struggle, I got it to work accurately. This post at stackoverflow helped. I’m going to explain how it works more in depth.

**Assumptions
**Here we have a cannon on the ground, trying to hit a flying target. Let us assume the target is travelling with constant velocity, unaffected by gravity, and so is the projectile shot by the cannon.

The target will have a known velocity `u`

. We will also know the speed of the projectile `|v|`

in advance, and we want to find the vector `v`

that will make it hit the target.

**Method
**The idea is to transform the shooter and target to a new coordinate system where the line between them is one of the axes, match up the parallell speed, and then calculate the appropriate tangential speed for the projectile.

In order for the projectile to hit the target, the I composants of the velocities, `vi`

and `ui`

must be equal. If they are not, the projectile will be too fast or slow in that direction and cannot hit the target.

To calculate `vi`

, first find the vector between A and B, and normalize it. Then project `u`

onto `AB`

using a dot product, giving `uj`

. Subtracting `uj`

from `u`

, we get `ui`

which is equal to `vi`

.

Once `vi`

has been determined, `|vj|`

can be found by using Pythagoras theorem, since we know the magnitude `|v|`

.

Then we can multiply the unit vector `AB`

by `|vj|`

to get `vj`

, and lastly, add together `vj`

and `vi`

to get `v`

**Pseudocode**

// Find the vector AB

ABx = Bx - Ax

ABy = By - Ay

// Normalize it

ABmag = sqrt(ABx * ABx + ABy * ABy)

ABx /= ABmag

ABy /= ABmag

// Project u onto AB

uDotAB = ABx * ux + ABy * uy

ujx = uDotAB * ABx

ujy = uDotAB * ABy

// Subtract uj from u to get ui

uix = ux - ujx

uiy = uy - ujy

// Set vi to ui (for clarity)

vix = uix

viy = uiy

// Calculate the magnitude of vj

viMag = sqrt(vix * vix + viy * viy)

vjMag = sqrt(vMag * vMag - viMag * viMag)

// Get vj by multiplying it's magnitude with the unit vector AB

vjx = ABx * vjMag

vjy = ABy * vjMag

// Add vj and vi to get v

vx = vjx + vix

vy = vjy + viy

It can be interesting to note that any vector v with vi=ui, and vj in the direction of the target, will make the projectile hit the target. For example the two purple lines in the diagram. But the only one with the correct magnitude is the v we have found.

This example is in 2D, but the same method can be used in 3D by considering the plane in which the target, cannon and target velocity lies.

**Corner Cases**

It is not always certain that the cannon can hit the target. This can be the case if the target is faster than the projectile, and moving away from it. For the hit to be possible `u`

must be greater than `vi`

at the time of fire. If `u<vi`

the expression in the square root will be negative, and thus the root will be undefined, so you should have a check for that.

**Example**

Flash example

**Source code**

Flashdevelop project

## Update:

I have updated this article with some pseudo code, and to be much easier to understand.

## Update 2, the same thing in 3D:

Unity3D example and source code

Pingback: Moving target intercept in 3D » Danik Games DevBlog()

Pingback: The Planning Stage of my Killbot AI – A Studio 2 Blog | Kirsty Tschirpig()