UPDATE:
Feel free to jump to "Attempt #3" if you just want a quick answer to your search that puts you on the path to writing an informed utility function in your math library that you can call your very own.
I just found out that some folks are pointing others to this page as a reference. That is quite awesome! I am honored to have written something useful to the community at large. Feel free to add comments below or send me thoughts on ways to improve this article. Math corrections are also welcome. My favorite comments will be the ones where you tell me what game this helped you make :)
For the record, this is using math taught in high school/early college algebra, geometry, and physics. Teachers may sometimes find themselves faced with skeptical students wondering when they will ever use any of this stuff in real life:
As a product of my education, I have a particular soft spot for math and science teachers. This page is my love letter to all of them.
A while back, I decided to look up algorithms for predictive firing on the internet, but I couldn't find any that incorporated acceleration in three dimensions, so I made an attempt at deriving the algorithm, myself.
This is my story. I hope you like it.
^{Image Credit: The Internets (possibly from Something Awful's Photoshop Phriday)}
The Problem:
Aim a projectile launcher to hit a moving target in ndimensional space (2d or 3d) with a straight projectile of constant finite speed.
To keep this derivation simple, we can assume the projectile travels in a straight line and is immune to gravity. Once we have the straight line solution, we can modify that solution to support lobbed projectiles.
The Givens:
The Goal:
Find a unitized vector representing the bullet's firing direction. Since we know the bullet's speed as S_{b}, we can multiply that speed with the unit vector to get the vector that represents the bullet's velocity and direction.
For our purposes, we will combine S_{b }and this unknown direction into a single variable:
The goal is to find the ndimensional normalized vector, desiredAimDirection
Derivation Strategy:
Feel the Math...
Imagine two things happening at the same time:
...Feel it!
Become the NPC! When the enemy is before you, you see the matrix in your virtual simulation: the sphere growing outward from the muzzle of your weapon as your target attempts to flee in a straight line. In your virtual simulation, you see only the sphere centered at your muzzle and a line tracing from your target's head... and it is beautiful!
The rest of this page is an illustration of your NPC's sphere of potential influence intercepting the straight line defined by the target's current position and movement.
Philosophically and spiritually, we are seeking that position in time and space at which the arrowhead of that growing line from the target intersects the edge of that growing sphere from the muzzle.
I am intentionally not including a picture of an arrowed line and sphere here to encourage you to develop/confirm your own neural pathways to instinctively and flexibly form this timebased moving model in your head as a prerequisite for being able to understand how this solution works for any predictive aim scenario... "Open your mind, Quaid! Open your mind!!!"
Yay Physics!
We are all born with an inherent understanding of physics, which is why we know that the line representing target motion will grow in length over time.
The Kinematic Equations allow us to convert positions, time, and speed into growing lines and spheres. This is the kinematic equation relevant to our purpose:
Position_{Final} = Position_{Initial} + Velocity_{Initial}*time + 0.5*Acceleration*time^{2}
If the perfectly aimed bullet meets the moving target, then we can say that finalPositions will coincide between the kinematic equations for the moving bullet and the moving target.
Note that I am using the word "bullet" instead of projectile in order to play nice with acronyms where P unambiguously means "Position" instead of "Projectile", and B means "Bullet". Apologies in advance for the ambiguity between time t and "Target".
The thought journey goes as follows...
Strategy #1  System of Equations with Acceleration:
There are two unknowns in the above equation: t and V_{b}.
V_{b} is a vector of ndimensional velocity that is the result of the normalized vector of bullet heading times scalar magnitude of bullet speed, S_{b}.
Since there are two unknowns and only one equation, then one method of solving this is through a system of equations. With two independent equations and two unknowns, we can isolate one of the unknowns (like t) and plug that into the other equation to identify the other unknown (V_{b}). Knowing the value of V_{b} and S_{b} will allow us to determine the normalized vector that defines the desired heading of the muzzle when it shoots.
For the second equation, I specifically wanted to take direction out of the picture when it came to the bullet because I know its speed but not its direction. Without direction, the bullet can be thought of as a growing sphere. Hence, the other equation I used for this method feels like a parametric representation of the bullet as a spherical AoE (Area of Effect) field growing outward per t whose radius would be equivalent to the distance from muzzle to target at the proper value of t. So when t is 0, the radius of that sphere is 0, and when t is righteous, the distance from muzzle to target will intersect in one of two places... since lines are able to intersect spheres in two places.
Combining the two concepts, I had an equation that looked like this:
Good news: Only one unknown in the above equation. If we isolate the t, then we can plug that t into this known equation:
...in order to isolate V_{b}, which will lead us to the goal.
Bad news: I did the math (which I'll go into detail with in Attempt#3), but gave up and then decided not to post my formulas in this article because it was uuuuuuugly. The generic solution to the combined equation involving Vector magnitude is technically doable, but an isolated t in terms of all those variables would end up being hairy to the 4th degree because of acceleration, which gives you t^{4} somewhere in that mix after doing Law of Cosines followed by Quadratic coefficient determination.
I decided to bail on that direction and, instead, went with an iterative Newtonianlike approximation.
Strategy #2  Iterative Approximation with Acceleration:
If I find the value of t that coincides with perfect impact, then I can find where that impact would occur by plugging into the target's kinematic equation. That future position would be where the muzzle should point at when it fires the projectile.
Feel the Math!
Think of this as bouncing back and fourth between time, t, and Target Position, P_{t} which are defined by equations that feed into each other. Bouncing back and fourth gets you closer and closer to convergence as each new P_{t} gets you a more accurate new t, which gets you a more accurate new P_{t} after that and so fourth until you feel that your iterated P_{t} accurately reflects the actual P_{t} at the future time of impact, t.
Baseline iteration:
A fair first approximation is to assume that the target is not moving. In this case, the value of t is the time it takes for the bullet to travel from muzzle to target's current position.
First iteration:
So now you have t_{0}, which is a decent first guess at the time of impact. Plug that t_{0} into the target's kinematic equation to find its position when t_{0} seconds have passed:
Now you have a new position for the target at the supposed moment of impact, time to calculate a new t with that new position.
Recurring Iteration:
Now you have a new time, t_{1}. t_{1} is better than t_{0} because it took a more accurate position guess into account. If you want, you can go on as many times as you are willing to iterate to get an answer that is "good enough". Be sure to use the original target position P_{ti}, as the kinematic equation is based on the original known position at time t=0.
So the general pattern is...
And the answer you are looking for is...
desiredAimDirection = Normalize( P_{t[n]}  P_{bi});
... to hit that target in t_{[n]} seconds.
Assuming that the speed of the bullet is faster than the speed of the target (imagine a growing Area of Effect), the deltas between successive t and P values will diminish between each iteration. Those t values are mathematically bound to converge asymptotically upon the correct value of t depicting the time that projectile and target need to travel before reaching coinciding positions.
The nice thing about this iteration method is that it can be easier on CPU cycles if you arrange the code to amortize iteration steps across separate cycles as part of your AI CPUload budgeting methods. One side effect of iteration is that using the value of t from your current step in the next iteration across ticks can make it look like your AI's aim is gradually becoming more accurate for targets that move predictably... as if they were refining their aim while looking at you :)
In the case of a first person shooter, you probably want AIs to aim their missed shots in front of the player target's camera for dramatic effect. This particular algorithm has enemy aim statistically likely to chase the moving target from behind.
Supporting Lobbed Projectiles for Strategy #2:
Lobbed projectiles are simply projectiles that have downward acceleration on them, assuming gravity goes down in your video game simulation :)
Spiritually, Equation 2 represents this:
And the answer you are looking for is...
V_{b}
... to hit that target at P_{t[n]} in t_{[n]} seconds.
Note that there is V_{b} is explicityly NOT Normalized in this solution. If something feels a little off about this, you are correct. I will go into more detail on why we do this after Strategy #3.
Strategy #3  Assuming Zero Acceleration:
The downside of Strategy #2 is that it requires multiple cycles and even then, it is not exact. If you want to do this as a single pass utility function that is mathematically accurate on the first attempt, then we're going to have to revisit the original strategy described in #1.
Acceleration is what makes the Strategy #1 difficult to solve because it throws that t^{2} into the mix which eventually becomes a T^{4} when you convert that vector into a scalar magnitude.
The problem of predictive aim is much more solvable if we just drop this whole Acceleration bit.
For completeness sake, here is the derivation of predictive aim direction for a target moving with zero acceleration:
Two equations. Two unknowns, t and V_{b}
First find t, then you can use that to solve for V_{b}
Equation 1 can be broken down to isolate t through these simple steps:
You now have two possible values of t.
This can happen when you are intersecting a growing line with a growing sphere.
"But which one of you is the real t?"
"You're going to have to calculate us both... it's the only way!"
If t is negative, you can eliminate that value immediately because timereversing computers will not be available to humans until the year 2942. By then, we will all be dead.
If both values of t are positive, then you may want to pick the smallest one if that is the design you are "shooting" for (get it? shooting? LOL). You basically have a situation where both possibilities will reach their mark (i.e. target is running away from your NPC at a skewed angle from a somewhat slow projectile), but you probably want the NPC to bias towards hitting sooner rather than later... perhaps. The choice is yours.
We want to isolate V_{b} in Equation 2: P_{bi} + V_{b}*t = P_{ti} + V_{t}*t
You can check your math by making sure that...
Length(V_{b}) == S_{b}
If your numbers are slightly off, then this may be attributed to floating point precision loss. The best advice I can give you on that is to...
V_{b} being an ndimensional vector should get you the direction you need:
desiredAimDirection = Normalize( V_{b} );
Supporting Lobbed Projectiles for Strategy #3:
We start with this:
"finalProjectilePosition = finalTargetPosition"
If your projectiles are affected by gravity, then all you have to do is modify Equation 2 to account for constant projectile acceleration in 2D/3D space:
P_{bi} + V_{b}*t + 0.5*A_{b}*t^{2} = P_{ti} + V_{t}*t
At this point, we have already solved for t, and in the lobbed case, A_{b} is a vector representing gravity.
If something feels a little off about this, you are correct. We previously calculated t from equation 1 using S_{b} and an assumption that A_{b} would be zero. Our new version of equation 2 broke that assumption.
For a video game, this is okay. For an actual mechanical device where S_{b} is a constant, this would likely not be okay because we are actually changing the mechanical capability of the launcher with this lobbing strategy... all to support more tunable gameplay over realism.
Specifically, what we are doing here is calculating a V_{b} that feels like S_{b} to the player in terms of timing but actually shoots a projectile that goes slightly faster (assuming an upwards lob) than what S_{b} would imply just to compensate for gravity. A gentle drop of a grenade in a downward direction would actually mean that magnitude of the projectile velocity would be less than S_{b}.
You must be at peace with this discrepancy before moving on with the processing of Equation 2:
If you were to check your math, you will likely find that...
Length(V_{b}) != S_{b}
... for the gameplay reasons stated above.
Because of this, instead of normalizing V_{b}, we preserve that magnitude and make sure the projectile/grenade/victim impulses with exactly this vector when it leaves the muzzle/hand/blowhole.
In Search of Perfection:
^{Image Credit: The Internets... I swear! Just look at that frickin' scissor at the topright corner!}
I had my own reasons for wanting to take acceleration into account: My AI was meant to fight other AIs and eventually become sentient in its quest to become a master ninja of ALL AIs. But when that AI is an enemy shooting against the human player, one must step back and ask the following design questions...
Typically for most games, moving objects probably have an acceleration of zero most of the time since velocity tends to be capped and/or stable. Even if not, the collision hull of that object may actually be large enough to accomodate the offset from an inaccurate approximation.
Maybe the game design and fiction would allow the projectiles to have a slight heatseeking curve to them as they travel. Or explode in proximity applying splash damage.
Maybe the game design will call for a pseudorandom perturbation of the aim vector or dicerollbased "dramatic misses" to give a sense of skilled vs. unskilled NPCs in a way that diminishes the need for pinpoint accuracy.
Or maybe none of this matters because all bullets in the game are instantfire hitscan raycast weapons or the game is multiplayer deathmatch only hahahahahaha!
In the end, I may not always take acceleration into account, but if I do, I would go with iterative approximation between P and t to have NPCs act like they are getting better the longer they aim at a PREDICTABLE target.
Owain abArawn 
19 May 2009 at 2:46 pm PST

Perhaps an area for further research would be to consult naval artillery gunnery manuals. This is essentially the same problem you are considering where both the shooter and the target are in motion, plus it considers ballistic drop and wind effects. Gunnery officers have had to solve this problem for hundreds of years, before there were radars, computers, or laser range finders. Perhaps you could check the archives at a naval museum for a gunnery manual for the basic algorithm, and adapt it for use in your shooter.
Practically speaking, if you have accelerations in 3 axis of motion for both the shooter and the target, your probablility of hitting anything at long range is nil for a hand held weapon (which I assume you are simulating in your AI). If you don't have an aimed shot from a stable firing position, you are essentially pointing in the general direction of your target to employ the "spray and pray" school of marksmanship. You may get the occasional 'golden BB' to hit your target, but that's about it. 


Kain Shin 
I am an AI.
My weapon is math. Kashinggggg!!!!! 


Owain abArawn 
Not much interest generated in the 'featured post', it seems.
I've been thinking of this and decided the best thing you might want to do is pay a visit to a firing range, and do some fundamental research on marksmanship. There are ranges that rent weapons, so if you don't own a pistol (cheapest to fire), and don't want to buy one for yourself, you can still get some practice. If you consider math to be your weapon, a visit to the firing range may be a humbling experience for you. Trying for any kind of accuracy when you have accelerations in 3 dimensions for both shooter and target is pretty much out of the questions. If you can keep your rounds going down range, that will be good, and hitting the target will be even better. 


Kain Shin 
Math is hard. Fist probably better for weapon use.



Kain Shin 
If anyone is interested, I have posted a C# Unity3Dcompatible version of Strategy #3 as public domain on my website:
http://ringofblades.com/Blades/Code/PredictiveAim.cs 

