Predicting enemy position in order to have an object lead its target

Question

In my 2D game I have AI turrets that should assist the player by automatically firing towards enemies. I would like to make them fire intelligently and lead their target instead of just targeting an enemy's current position. So, given the (always constant) velocity and position vector of both the enemy and the turret's projectile, how can I find a vector that represents the actual position the turret must target in order for the projectile to intersect (and hit) the enemy?

Any links to articles that describe the math, algorithms, etc. would be appreciated!

Answer 1

This question on GameDev, and this question on StackOverflow should provide you with the answer you're looking for. :)

Answer 2

I'm not gonna give you an answer I'm sure is useful or even correct, but here it goes:
After playing with mathematica a little more (check the end of the answer for notebook /published notebook) files, this solution appears to be correct, even thought it might not be the best one in terms of efficiency.

I wrote this in mathematica which corresponds to your problem. Basically it solves the equations / inequalities in order to the OA variable which is what we need to find out. The output is gonna give us the possible solutions that OA can have and the conditions that need to verify for each solution to be valid:

Reduce[{BPx, BPy} + t*{BVx, BVy} == {OPx, OPy} + t*OV*{Cos[OA], Sin[OA]} && t != 0 && OV != 0, {OA}]

• {BPx,BPy} is blue's current position

• {BVx,BVy} is blue's velocity vector

• {OPx,OPy} is orange's bullet position

• OV is the norm of orange's bullet velocity vector (total speed)

• OA is orange's bullet angle (angle of velocity vector)

• t is the time needed for the bullet to hit blue

I tried putting t>0 && OV>0 in the conditions but mathematica would take forever so I just used t!= 0 && OV != 0. So the solutions I'm gonna give here just work when blue is not in the exact same position as orange and when the orange's bullet really moves (instead of staying still)

The output is gigantic: http://freetexthost.com/xzhhpr5e2w

However if we extract the OA == _ parts, we get this:

http://freetexthost.com/iyrhqoymfo

Those are the values OA can have (each one requiring different conditions to be valid).

With some further analysis taking out the solutions that require OV to be negative which we don't want, I got this:

http://freetexthost.com/iy4wxepeb6

So these are the possible solutions to the problem, each one requiring different conditions to be valid. In order for a certain angle OA to be a valid solution, the following conditions must meet:

Reduce[{BPx, BPy} + t*{BVx, BVy} == {OPx, OPy} + t*OV*{Cos[OA], Sin[OA]} && t != 0 && OV != 0, {t}]

Output:

(BVy - OV Sin[OA] != 0 && BPx == (BPy BVx + BVy OPx - BVx OPy - BPy OV Cos[OA] + OPy OV Cos[OA] - OPx OV Sin[OA])/(BVy - OV Sin[OA]) && t == (-BPy + OPy)/(BVy - OV Sin[OA]) &&  BPy OV - OPy OV != 0) || 
(BVy == OV Sin[OA] && BPy == OPy && BVx - OV Cos[OA] != 0 && t == (-BPx + OPx)/(BVx - OV Cos[OA]) && BPx OV - OPx OV != 0) || 
(BVy == OV Sin[OA] && BVx == OV Cos[OA] && BPy == OPy && BPx == OPx && OV t != 0)

So consider only the solutions where that verifies (you don't need to verify the t==_ parts. They are the ones that give you the time needed for the bullet to hit the vehicle if the other conditions are valid. Notice that if t results in a negative value, you cannot consider a given OA as a valid solution, even if it verifies the other conditions (this is because we used t!= 0 instead of t>0 in reduce)).

It also might be a good idea to ask in https://math.stackexchange.com/ about this.

Edit

I've grown some interest for this question, so I've created a commented notebook with a graphical demonstration of everything I explained . Download it here:

http://www.2shared.com/file/pXhYyhN1/towerBullets.html
Or here: http://www.2shared.com/file/W01g4sST/towerBullets.html

(this is the published version, and you only need the mathematica player -which is free- to see it. If you don't have mathematica this is the way to go)

Screenshot: