|
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 derived the algorithm myself. I'm sharing this here in the hopes of finding a better solution than the one I came up with.
Problem:
Make a projectile launcher shoot a moving target in N-dimensional space with a straight projectile of constant finite speed. In other words, find the target position to shoot at. This will require finding the time, t, it takes to reach that target position.
- Time from bullet launch to desired impact: t
To keep this derivation simple, we can assume the projectile travels in a straight line and is immune to gravity. It is easy enough to modify the solution to take gravity into account once we have the straight line solution.
Given:
- Bullet Starting Position vector: Pb0
- Bullet Speed (scalar constant, non-infinite): Sb
- Target Starting Position vector: Pt0
- Target Starting Velocity vector: Vt0
- Target Acceleration vector (constant): At
Goal:
Find a unitized vector representing the bullet's firing direction. Since we know the bullet's speed as Sb, 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 Sb and this unknown direction into a single variable:
- Bullet velocity vector (constant): Vb = unit direction * Sb
Derivation Strategy:
Constant acceleration means that the target's movement is mathematically predictable...
Kinematic equation for position:
finalPosition = initialPosition + initialVelocity*time + 0.5*acceleration*time^2
If the perfectly aimed bullet meets the moving target, then we can say that finalPosition will coincide between the kinematic equations for the moving bullet and the moving target.
- Pb0 + Vb*t = Pt0 + Vt0*t + 0.5*At*t*t
And so my train of thought towards a solution goes like this...
- Finding 't' can lead to finding the final position
- the final position is where the launcher would need to aim. This problem would be solved if we can obtain the final position (i.e. there is probably a "LookAt" function for the launcher in your gameplay code that can take an XYZ position as a parameter)
- The above equation can't be solved by itself because Vb is also unknown.
Attempt #1 - System of Equations:
There are two unknowns in the above equation: t and Vb... Vb is a vector of n-dimensional velocity that is the result of the normalized vector of bullet heading times scalar magnitude of bullet speed, Sb.
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 (Vb). Knowing the value of Vb and Sb will allow us to determine the normalized vector that determines which way the gun should point 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 it's 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 "systems of equations" method was a parametric representation of the bullet as a spherical field whose radius would be equivalent to the distance from target to gun at the proper value of t. So when t is 0, the radius of that sphere is 0, when t is righteous, the distance from gun to target will intersect in one of two places... since lines are able to intersect spheres in two places.
So combining the two concepts, I had an equation that looked like this:
- VectorMagnitude(Pt0 + Vt0*t + 0.5*At*t*t - Pb0) = Sb*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:
- Pb0 + Vb*t = Pt0 + Vt0*t + 0.5*At*t*t
...to determine Vb, which is easy enough to isolate.
Bad news: Vector magnitude is the square root of the sum of the magnitude of each axis. The generic solution to the combined equation involving Vector magnitude is doable, but an isolated t in terms of all those variables would end up being hairy to the 4th degree because of that acceleration factor which gives you t^4 (t to the fourth power) somewhere in that mix; at least that's what I got when I attempted a solution using what I knew about quadratic equations. It could be simplified if constant acceleration were assumed, but even then, you would end up with a giant quadratic mess which leaves you with two possible solutions because of the "±" involved. You can visualize this "±" by going back to the expanding sphere analogy, and so after all that, you would then need to figure out which of the two possibilities is the correct one.
So I decided to bail on that direction and, instead, went with a type of iterative Newtonian-like approximation. Somehow, I do wonder if I might have missed out on some elegant means of solving this with the systems method.
Caveat: Setting Acceleration (At) to 0 simplifies the solution if you are willing to assume constant velocity (which also means no gravity).
Attempt #2 - Iterative Approximation:
So 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 gun should point at when it fires the projectile.
Find t, save the world!
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 gun to target's current position.
- t0 = VectorMagnitude(Pt0 - Pb0) / Sb
First iteration:
So now you have t0, which is a decent first guess at the time of assassination. Plug that t0 into the target's kinematic equation to find its position when t0 seconds have passed:
- Pt1 = Pt0 + Vt0*(t0) + 0.5*At*(t0)*(t0)
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.
- t1 = VectorMagnitude(Pt1 - Pb0) / Sb
Recurring Iteration:
Now you have a new time, t1. t1 is better than t0 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 delay an answer that is "good enough", but be sure to use the original target position Pt0, as the kinematic equation is based on the original known position at time t=0.
- Pt2 = Pt0 + Vt0*(t1) + 0.5*At*(t1)*(t1)
- t2 = VectorMagnitude(Pt2 - Pb0) / Sb
So the general pattern is...
- Pt[n] = Pt0 + Vt0*(t[n-1]) + 0.5*At*(t[n-1])*(t[n-1])
- t[n] = VectorMagnitude(Pt[n] - Pb0) / Sb
Assuming that the speed of the bullet is faster than the speed of the target, the deltas between successive t values will diminish between each iteration. Those t values are mathematically bound to converge asymptotically upon the correct value of t depicting the time the 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 different ticks in similar fashion to an A* search. As part of your AI CPU budgeting routine, you will probably want to limit the number of iterations you do per tick to avoid CPU hiccups... either by a hard count limit and/or some heuristic for t being "close enough". 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 don't change direction/acceleration. Of course, in a first person shooter, you probably want AIs to aim their missed shots in front of the player target's camera for dramatic effect and this algorithm has enemy aim statistically likely to chase the moving target from behind.
Attempt #3 - ???
This problem is typically solved without acceleration. Acceleration is what makes the problem more complex because it throws that t^2 into the mix which eventually becomes a T^4 when you convert that vector into a scalar magnitude.
I had my own reasons for taking acceleration into account: My AI was to be the best version of me. But when the AI is the bad guy shooting against you, you have to ask yourself...
- How important is the target's acceleration, really?
- How perfect does target prediction really need to be?
During most typical games, moving AI entities probably have an acceleration of 0 most of the time. Even if not, the collision hull may actually be large enough to accomodate the offset from the pure velocity-based approximation. Maybe you can fudge the effect of acceleration after the fact. Maybe the game design and fiction would allow the proectiles to have a slight curve to them as they travel.
There are a lot of ways to avoid taking acceleration into acount for this type of targeting, but I have a strong feeling that somebody out there has succeeded at attempt #1 where I had failed. The ideal solution would be an atomic equation that you can plug numbers into instead of an iteration-based solution.
I gave up on attempt#1 because I was unwilling to solve a system of variables that involved a messy quadruple root situation in order to isolate t. Perhaps another equation that involves a dot product projection of one vector onto another might have made a more solvable system.
So many games have NPCs predictively shooting at the player's future position. I do wonder what types of solutions other programmers have come up with for this sort of thing.
|
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.
My weapon is math.
Ka-shinggggg!!!!!
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.