How to calculate shot angle and velocity to hit a moving target?

Question

I am developing a 2D Android game and I am making an aiming algorithm for AI projectiles to hit enemies either following a path, or free moving. At the moment it just calculates where the target will be after a distance and fires a projectile to meet it at that distance. Of course this means varying the projectile speed to meet the target.

Does anyone have any tips for a simple-ish algorithm (optimal-ish) to calculate when the projectile needs to fire and where it needs to aim if it can only travel at a constant velocity? Say the projectile goes twice the speed of the target?

The only way I can think of involves searching and seems quite large.

Answer 1

In a tower defence game I made, I used a quadratic equation to predict the intersection and thus aim point. The following aiming code snippet assumes the enemy is traveling at a constant speed and direction. It also assumes the projectile will be traveling at a known constant speed (could be any speeds but must be known to the algorithm).

Vector totarget =  target.position - tower.position;

float a = Vector.Dot(target.velocity, target.velocity) - (bullet.velocity * bullet.velocity);
float b = 2 * Vector.Dot(target.velocity, totarget);
float c = Vector.Dot(totarget, totarget);

float p = -b / (2 * a);
float q = (float)Math.Sqrt((b * b) - 4 * a * c) / (2 * a);

float t1 = p - q;
float t2 = p + q;
float t;

if (t1 > t2 && t2 > 0)
{
    t = t2;
}
else
{
    t = t1;
}

Vector aimSpot = target.position + target.velocity * t;
Vector bulletPath = aimSpot - tower.position;
float timeToImpact = bulletPath.Length() / bullet.speed;//speed must be in units per second

Since it also determines time of impact I simply waited until the time pasted to call the impact graphics at the position of the target at that time... no need for any collision detection to determine hits.

Answer 2

The AI, the target's location during the time the projectile is fired, and the target's eventual location at point of death form a triangle.Here is what you should already know:

1. Side length a, which is the projectile speed
2. Side length b, which is the target speed
3. The angle of motion of the target of motion of the target.

You have three parts of the triangle, a SSA case, so solve it like this

1. Find angle B based on the the angle of motion and the location of the AI
2. Use the law of sines to find angle A

Angle A should allow you to determine the angle at which the projectile should be launched.