To hit a moving target by shooting a gun you have to lead it, aiming at the spot where the target will be when the bullet reaches it. In this article we consider three successively harder versions of this problem.
To simplify the math, express the target's position and velocity relative to the shooter's, so that the shooter is effectively stationary at the origin. Assume that the target moves in a straight line, if it is moving. Also assume no air drag.
Motion without gravity
Without gravity, bullets travel in a straight line at constant velocity. To determine where to shoot, imagine shooting an infinite number of bullets simultaneously in all directions, forming an expanding sphere of death. While the sphere is expanding, the target is moving along a straight line (or standing still). If we can determine the instant at which this expanding sphere touches the moving target, we know where to aim: at the target's position when it gets hit by the expanding sphere of death.
Variable definitions:
Equation for the time when the target and bullet are equidistant from the shooter:
Square both sides:
Expand:
Group terms by powers of t:
Examine the equation above. If the target's velocity is zero, the impact time works out to simply be target distance divided by bullet speed, which makes sense. The constant term is never negative; it is positive as long as shooter and target are not at the same position. The quadratic term curves upward if the target's speed is faster than the bullet speed. In this case, only the linear term would be capable of bringing the curve below the zero line. In problem terms: if the target is faster than the bullet, the bullet can hit the target only if the target is moving toward the shooter fast enough.
Code for solving this quadratic might look like this:
double time_of_impact(double px, double py, double vx, double vy, double s)
{
double a = s * s - (vx * vx + vy * vy);
double b = px * vx + py * vy;
double c = px * px + py * py;
double d = b*b + a*c;
double t = 0;
if (d >= 0)
{
t = (b + sqrt(d)) / a;
if (t < 0)
t = 0;
}
return t;
}
Once t is known, plug it into the expression for the motion of the target to find the point to aim at:
This code works equally well with 3D vectors. In a real game I'd be using a vector data type rather than passing around the X, Y, and Z components individually, and I'd have a function for doing dot products instead of writing out x1*x2 + y1*y2 + z1*z2 every time.
If the discriminant (d in the code) is less than zero, it means there are no real roots. In real terms this means the target is moving away faster than the bullet can travel, so there is no possibility of an impact. The code deals with the no-root situation by clamping t to zero, which will cause the gun to aim at the target's current position. A more sensible thing to do might be to find the time t that minimizes distance between bullet and target, and aim at the target's position then.
There is also generally a negative root which corresponds to playing time backwards from the current moment, and as such is not usable.
Space combat games such as Freelancer or Darkstar One draw a targeting reticle ahead of enemy ships, at the spot where you need to shoot in order to hit them. Now you can go forth and do likewise. Obviously, the aim position is different for different bullet speeds, so if you have turbolasers that shoot at 4.5 km/sec and linear tachyon atomizers that shoot at 6 km/sec, you might want two reticles.
Gravity without motion
On earth, gravity pulls bullets downward as they fly. (They also slow down quite a bit due to air resistance, but I'm not going to get into that today.) To counteract gravity you have to aim higher for far-away targets. Let's figure out how to do this with a stationary target first.
Returning to our expanding sphere of death, we could imagine it falling due to gravity as it expands. Equivalently, we could think of the stationary target “falling” upward into the sky instead. This allows us to leave the sphere centered on the origin. Here's the equation for a target which starts at rest and falls upward until it hits the expanding sphere:
In a typical game, gravity operates along a single axis. In this case, the G vector will have zeros in all the other components. Squaring:
Expand:
Group terms by power of t:
Although we have a fourth power of t, we can substitute u = t2 and be left with a quadratic instead:
The two solutions to this u quadratic correspond to the two parabolic arcs that pass through the target point. There's a short, low arc and a longer, high arc. (At maximum range they merge together into one.) Choose whichever one works best for your situation.
Once you've solved for t, plug it into the equation for motion of the target to get the aim position:
Be sure that your targeting code integrates to the same position your simulation will when it moves the bullet through the air. The equations above assume correct integration, but as a kid I wrote things that weren't quite right. For instance:
The code is assuming that velocity is expressed in distance per frame, and acceleration in distance per frame squared. However, it should be adding half the acceleration to the position as well, like this:newPosition = oldPosition + oldVelocity;
newVelocity = oldVelocity + acceleration;
newPosition = oldPosition + oldVelocity + 0.5 * acceleration;
newVelocity = oldVelocity + acceleration;
Gravity and motion together
Finally, let's shoot an arcing projectile at a moving target! The initial equation is just a combination of the starting equations for the previous two cases:
Square:
Expand:
Collect terms by power of t:
This is a quartic equation and there's no way around it. Let's start by sanity-checking it.
If gravity is zero, the quartic and cubic terms drop out (as well as part of the quadratic term) and we're left with the motion-but-no-gravity equation. If velocity is zero instead, the cubic and linear terms drop out (as well as part of the quadratic term) and we're left with the gravity-but-no-motion equation.
When I'm working on solving problems like this, I find it helpful to rig up my game to plot graphs in real time. In this case, I drive the target around and get a constantly-updated graph of the polynomial and its derivatives for shooting at it. This allows me to quickly get a feel for the nature of the problem. Here's an example graph (with added labels):
Looking at the equation, you can see that the fourth-order term will always be positive, which means that the red curve will always turn upward on the outer ends. The constant term will always be positive as long as the target is not at the same place as the shooter, which means the curve will be positive as it crosses the Y axis.
The quartic curve has (up to) three points where it changes direction from upward to downward or vice versa. One way to find the roots would be to divide the curve up into intervals between these points. If one end of an interval is above zero and the other is below zero, you know there is a root within that interval. You could use a binary search to locate it, or you could use the midpoint of the interval as an initial guess and use Newton's method to converge on the root. The outer intervals are unbounded so binary search wouldn't necessarily work there, but you could double a t value until it evaluates positive and then binary search within that interval.
The extrema of the quartic correspond to zeros (roots) of its first derivative (the green line in the graph). The first derivative of a quartic is a cubic. We could follow a similar procedure to find its roots: find the zeros of its derivative (the blue line); use them to subdivide the curve into intervals; evaluate the function at the interval endpoints; and search for roots in the intervals that cross the X axis.
When there are no roots, I decided I wanted my gun to shoot at an angle that brought the bullets as close as possible to the target. This corresponds to finding the non-negative t that gives the smallest value for the quartic function. Minima have to be either at one of the zeros of the first derivative, or at t = 0. Once the roots of the cubic are known it's simple to evaluate the function at them, and at t = 0, and pick the one with the smallest value.
Jochen Schwarze wrote some cubic/quartic solving code in Graphics Gems I which works great.
Once again, once t is known, plug it into the left-hand side of the original equation to get the aim position:
Ron Levine wrote a Usenet posting a few years ago covering some of the same ground. There's also a page on the Unreal Wiki.
No comments:
Post a Comment