Predictive Aim Mathematics for AI Targeting

by Kain Shin on 05/15/09 08:33:00 pm

The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.

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:

- Kinematic Equations
- System of Equations + Degrees of Freedom
- Newton's Method
- Vector Properties
- Dot Product
- The Law of Cosines
- The Quadratric Equation
- Exponent Properties

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 n-dimensional 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**:

- Bullet Initial Position (i.e. muzzle position): P
_{bi} - Bullet Speed (scalar constant, finite): S
_{b} - Target Initial Position: P
_{ti} - Target Initial Velocity: V
_{ti} - Target Acceleration (constant): A
_{t}

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:

- Bullet velocity (constant vector): V
_{b}= desiredAimDirection * S_{b}

**The goal is to find the n-dimensional normalized vector, desiredAimDirection**

Derivation Strategy:

Feel the Math...

Imagine two things happening at the same time:

- A sphere growing outward representing all possible places that a projectile can be at time t. Radius is 0 when t=0
- A line growing longer representing target position in relation to a starting target position from time t. Length is 0 when t=0

...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 time-based 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".

- final position of bullet with zero acceleration = final position of target with nonzero acceleration
- P
_{bi}+ V_{b}*t = P_{ti}+ V_{ti}*t + 0.5*A_{t}*t^{2}

The thought journey goes as follows...

- Finding 't' leads to knowing the final position of both, the projectile and the target
- the final position is where the muzzle would need to aim.
- The above equation can not be solved by itself because V
_{b}is also unknown.

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 n-dimensional 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:

- Distance from muzzle to target = distance traveled by the bullet in t seconds
- Length( finalTargetPosition - muzzlePosition ) = distance traveled by the bullet in t seconds
- Length(P
_{ti}+ V_{ti}*t + 0.5*A_{t}*t^{2}- P_{bi}) = S_{b}*t

Good news: Only one unknown in the above equation. If we isolate the t, then we can plug that t into this known equation:

- P
_{bi}+ V_{b}*t = P_{ti}+ V_{ti}*t + 0.5*A_{t}*t^{2}

...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 Newtonian-like 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.

- t
_{0}= Length(P_{ti}- P_{bi}) / S_{b}

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:

- P
_{t1}= P_{ti}+ V_{ti}*t_{0}+ 0.5*A_{t}*t_{0}^{2}

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.

- t
_{1}= Length(P_{t1}- P_{bi}) / S_{b}

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.

- P
_{t2}= P_{ti}+ V_{ti}*t_{1}+ 0.5*A_{t}*t_{1}^{2} - t
_{2}= Length(P_{t2}- P_{bi}) / S_{b}

So the general pattern is...

- P
_{t[n]}= P_{ti}+ V_{ti}*(t_{[n-1]}) + 0.5*A_{t}*t_{[n-1]}^{2} - t
_{[n]}= Length(P_{t[n]}- P_{bi}) / S_{b}

And the answer you are looking for is...

**desiredAimDirection = Normalize( P _{t[n]} - P_{bi});**

... to hit that target in t

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 CPU-load 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:

- finalProjectilePosition = finalTargetPosition
- Gravity = A
_{b} - P
_{bi}+ V_{b}*t_{[n]}+ 0.5*A_{b}*t_{[n]}^{2}= P_{t[n]} - V
_{b}*t_{[n]}= P_{t[n]}- P_{bi}- 0.5*A_{b}*t_{[n]}^{2} - V
_{b}= [ P_{t[n]}- P_{bi}- 0.5*A_{b}*t_{[n]}^{2}] / t_{[n]} - V
_{b}= [ P_{t[n]}- P_{bi}] / t_{[n]}- 0.5*A_{b}*t_{[n]}

And the answer you are looking for is...

**V _{b}**

... to hit that target at P

Note that V

**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:

- Target Starting Velocity vector: V
_{ti}can now be just V_{t}since it is constant - Equation 1: Length(finalTargetPosition - muzzlePosition) = distanceTraveledByProjectile
**Equation 1: Length(P**_{ti}+ V_{t}*t - P_{bi}) = S_{b}*t- Equation 2: finalProjectilePosition = finalTargetPosition
**Equation 2: P**_{bi}+ V_{b}*t = P_{ti}+ V_{t}*t

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:

- Length(P
_{ti}- P_{bi}+ V_{t}*t) = S_{b}*t - Length( (P
_{ti}- P_{bi}) + V_{t}*t) = S_{b}*t - theta is the angle between (P
_{ti}- P_{bi}) and V_{t}*t - If the target was moving at a perfect 90 degree angle from the muzzle (theta == 90 degrees), then the pythagorean theorem would have been enough, but the target is more likely to run at a skewed angle ranging from perfectly towards to perfectly away from the muzzle. And so we use the Law of Cosines, instead
- Law of Cosines: a
^{2}+ b^{2}- 2*a*b*cos(theta) = c^{2 } **Law of Cosines**:- a = Length(P
_{ti}- P_{bi}) - b = Length(V
_{t}*t) - c = S
_{b}*t

- a = Length(P
**Dot Product:**- cos(theta) = DotProduct( Normalize(P
_{bi}- P_{ti}), Normalize(V_{t}*t) ) **cos(theta) = DotProduct( Normalize(P**_{bi}- P_{ti}), Normalize(V_{t}**) )**

- cos(theta) = DotProduct( Normalize(P
- Length(P
_{ti}- P_{bi})^{2}+ Length(V_{t}*t)^{2}- 2*Length(P_{ti}- P_{bi})*Length(V_{t}*t)*cos(theta) = (S_{b}*t)^{2} **Let’s refer to Length(P**_{ti}- P_{bi}) as D to represent initial distance from muzzle to target- D
^{2}+ Length(V_{t}*t)^{2}- 2*D*Length(V_{t}*t)*cos(theta) = (S_{b}*t)^{2} - D
^{2}+ (Length(V_{t})*t)^{2}- 2*D*Length(V_{t})*t*cos(theta) = (S_{b}*t)^{2} **Let’s refer to Length(V**_{t}) as S_{t}to represent Target Speed- D
^{2}+ (S_{t}*t)^{2}- 2*D*S_{t}*t*cos(theta) = (S_{b}*t)^{2} - D
^{2}+ S_{t}^{2}*t^{2}- 2*D*S_{t}*t*cos(theta) = S_{b}^{2}*t^{2} - 0 = S
_{b}^{2}*t^{2}- D^{2}- S_{t}^{2}*t^{2}+ 2*D*S_{t}*t*cos(theta) - 0 = S
_{b}^{2}*t^{2}- S_{t}^{2}*t^{2}+ 2*D*S_{t}*t*cos(theta) - D^{2} - 0 = (S
_{b}^{2}- S_{t}^{2})*t^{2}+ 2*D*S_{t}*cos(theta)*t - D^{2} **Quadratic formula**: For 0 = a*t^{2}+ b*t + c- a = (S
_{b}^{2}- S_{t}^{2}) - b = 2*D*S
_{t}*cos(theta) - c = -D
^{2} - t = [ -b ± Sqrt( b
^{2 }- 4*a*c ) ] / (2*a)

- a = (S
- The dot product result from above is the value to use for
**cos(theta)** - You can probably stop here to solve for t since you likely have those coefficients a, b, and c stored as local variables
**t = [ -2*D*S**_{t}*cos(theta) ± Sqrt[ (2*D*S_{t}*cos(theta))^{2}+ 4*(S_{b}^{2}- S_{t}^{2})*D^{2}] ] / (2*(S_{b}^{2}- S_{t}^{2}))

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 time-reversing 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

- V
_{b}*t = P_{ti}+ V_{t}*t - P_{bi} - V
_{b}= (P_{ti}+ V_{t}*t - P_{bi}) / t **V**_{b}= V_{t}+ [(P_{ti}- P_{bi}) / 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...

- Use
over**double**whenever possible**float** - Favor multiplication over division to minimize loss of significant digits
- Avoid using sqrt as much as possible to minimize loss of significant digits

V_{b} being an n-dimensional 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 a constant S_{b} and an assumption that A_{b} would be zero. In essence, we are saying that the speed of the bullet will never change. Our new version of equation 2 broke that assumption by saying that gravity will change the speed of the bullet during flight.

For a video game, this is okay. For an actual mechanical device in the real world where S_{b} is a an actual mechanical constraint of the physical device, this would likely not be okay because we are actually changing the capability of the launcher with this lobbing strategy saying that it can launch harder when pointing upwards and launch softer when pointing downwards... all to support more tunable gameplay over realism.

Specifically, what we are doing here is calculating a V_{b} that * feels* like S

You must be at peace with this discrepancy before moving on with the processing of Equation 2:

- V
_{b}*t = P_{ti}+ V_{t}*t - P_{bi}- 0.5*A_{b}*t^{2} - V
_{b}= (P_{ti}+ V_{t}*t - P_{bi}- 0.5*A_{b}*t^{2}) / t **V**_{b}= V_{t}- 0.5*A_{b}*t + [(P_{ti}- P_{bi}) / t]

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} to extract pure direction from it, we preserve that magnitude in addition to direction to 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 top-right 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...

- How important is tracking target acceleration, really?
- How perfect does target prediction really need to be?

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 heat-seeking curve to them as they travel. Or explode in proximity applying splash damage.

Maybe the game design will call for a pseudo-random perturbation of the aim vector or diceroll-based "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 instant-fire 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.