Shooting at a moving target as3

As I was implementing the towers I needed them to aim and shoot on the anticipated position of an enemy, assuming they are moving linearly (no acceleration). This is because the bullets in my game are physics entities that won’t hit the enemy instantly but after some time as it travels towards the predicted interception point. As a human you do those predictions all the time, for example passing a football to a running team mate, you predict where to pass so that your friend don’t have to stop and wait for the football to arrive. This is sometimes called leading a target, aim prediction or simply shooting at a moving target.

I though I would write up how I did this, much for my own sake (haven’t fiddled with this in a long time) and as they say repetition is the mother of all knowledge. You can skip to the bottom part to get the code directly. Also sorry for not using a proper font for math symbols. At least I tried to be consistant, * is the dot product and for scalar multiplication I didn’t use the mul sign (e.g. st).

These are the variables:
v = enemy velocity
p = enemy position in relation to tower (enemyPos-towerPos)
s = bullet speed
t = the time of impact (unknown – what we want to find out)

Now assuming that the enemy will continue in its path we can calculate where to shoot to get a hit.

The first equation we set up is:
|p+vt| = st

This happens when the distance from the tower to the bullet and enemy is the same. You can think of p+vt as a point along a line, starting at the enemy pos (p) and extending in the direction of its velocity (v) as the time (t) grows. The |p+vt| simply means the distance (from the tower) of a point on the line at a given time. st is the distance the bullet have traveled after t time units (remember distance = time * speed).

What we want to do is to find out the time (t) when they are at equal distances. To solve it we need to rearrange the expression a bit. Remember that |v| = sqrt(v*v) (* = dot product), in order to “free” t from its walls |p + v * t| we start by squaring both sides:

|p+vt|^2 = s^2t^2

Freeing t out of the distance operator (|):
|p+vt|^2 = sqrt((p+vt)*(p+vt))^2 =
(p+vt)*(p+vt) =
p*p + 2p*vt + v*vt^2 = s^2*t^2

Now we set it up as a quadratic equation just as we learnt in school.

v*vt^2 – s^2t^2 + 2p*vt + p*p = 0

(v*v – s^2)t^2 + 2p*vt + p*p = 0 (This is the quadratic form ax^2 + bx + c = 0).

Now we only have to solve it, so we plug it into the olden equation:

t1 = (-b + sqrt(d)) / 2a
t2 = (-b – sqrt(d)) / 2a

where d=b^2-4ac

There are two possible solutions to quadratic equations. The factor inside the sqrt is called the discriminant, d, and reveals information about the solutions, a positive d means we have two real solutions, if d is zero there is only one solution and if it’s below zero we have complex solutions this means that we don’t have anyway of hitting the enemy (enemy moving away faster than bullet).

a = v*v – s^2

b = 2*p*v

c = p * p

This is basically what I implemented, than after I got the solutions I returned the lowest positive t via some ugly if statements. I wasn’t really happy with this so I kept looking around and ran into  slembcke’s post ‘leading target‘, in addition to illustrating the equations nicely with graphs he points out that we can use the alternate quadratic formula if we only are interested in the first possible time of impact (works when there is a positive solution).

t = 2c / (-b+sqrt(d))

After unittesting this bad boy I felt pretty comfortable that it was what I was looking for, even though I haven’t proved it for myself. One thing to keep in mind is that this will return 2c/0 (division by zero) if  sqrt(d)=b, this happens when the enemy is moving away at the exact  speed as the bullet, in one of the towers axis (the bullet can’t catch up nor fall behind). I solved this by checking if the t == Infinity, if so I handle it just as if there are no solutions (negative t).

Another small improvement that  James McNeill pointed out is that you can cancel the 2 factor in b. As for this aiming problem we get 2*p*v for our b factor, squaring this in d (b*b) , gives us sqrt(4(pv)^2 – 4ac) => 2 * sqrt((pv)^2 – ac) so now we can cancel the 2 in the top 2c.

The equation we end up with is:

a = v*v – s^2

b = p*v (removed the 2 factor)

c = p * p

d = b*b – ac (removed the 4 factor)

t = c / (sqrt(d) – b)

Here is AS3 source code to calculate how to aim on a moving target:

private function _getToi(targetDir:Vec2Const, targetVel:Vec2Const, bulletSpeed:Number):Number
{
	const a:Number = targetVel.lengthSqr() - bulletSpeed * bulletSpeed;
	const b:Number = targetDir.dot(targetVel);
	const c:Number = targetDir.lengthSqr();
	const d:Number = b * b - a * c;
	if (d <= 0) return -1;
	return c / (Math.sqrt(d) - b);
}

Once you have the time of impact, you check if it’s negative or infinity – if so there is no firing solution. Otherwise you can easily calculate the aim position or direction by interpolating from the enemy position in by it’s velocity scaled by the time:

public function getAimPos(shooterPos:Vec2Const, targetPos:Vec2Const, targetVel:Vec2Const, bulletSpeed:Number):Vec2
{
	const targetDir:Vec2Const = targetPos.sub(shooterPos);
	const toi:Number = _getToi(targetDir, targetVel, bulletSpeed);
	if (toi == -1 || toi == Infinity) return null;
	return targetPos.add(targetVel.scale(toi));
}

As a final note, I assumed that the shooters (towers) are standing still, you can easily modify this by adding a shooterVelocity and pass the relative velocity to the _getToi method.