The Perfect Intersection

It is possible to use physics to predict the collision of two moving points. Suppose there's a player, for example, defined as a position in 3D space p = [p_x, p_y, p_z] and a corresponding velocity v = [v_x, v_y, v_z]. In t seconds, the position of the player will be p(t) = p + vt (vector scaling and addition). There is no need for integrators if we assume the velocity is constant; the estimate is exact.

To simplify the proof, assume that the weapon is fired from the origin of the world at [0,0,0]. We don't know where to fire the weapon yet (unknown direction), so the exact velocity of the projectile is not known. We do, however, know the speed s of the projectile.

At time t in the future, the projectile will be at a distance of st from the origin (distance is speed multiplied by time). For the projectile to hit, the player must be in the same position at any t. So the distance of p(t) to the origin (denoted |p(t)|) will be the identical to the projectile's distance to the origin:

This equation is sufficient to enable us to compute the time of collision. To make it easier to extract t, we can use the square of these values. The second equation here expands the vector algebra into real numbers:

Using a sum to simplify the notation, then developing the inner square:

We would like to compute the collision time t from these equations. Factorizing to expose t, we get a quadratic equation in the form at²+bt²+c=0 (second order polynomial). The symbols a, b, and c are arbitrary variables used to simplify the equations and the implementation. They are defined as follows:

Computing the time of collision involves first calculating these values for a, b, and c. Then, we plug them into the miracle solution for quadratic equations to get the result:

The result is defined as long as the statement in the square root is positive. (That is, the speed of the bullet must allow it to hit the moving target.) Theoretically, there is actually another solution to the polynomial using the positive square root. However, this predicts negative values of t (in the past).

Given t, we can compute the estimated point of collision with p(t) = p + vt. So that's the place the animat aims for the bullet to hit the enemy!

Practical Demo

There is an example animat on the web site based on these concepts. It can be found under the name of Predictor. Essentially, the AI first checks for visible players. If there is one nearby, its position and velocity are monitored. These are plugged straight into the preceding equation, and the trigger is pulled! See the instructions on http://AiGameDev.com/ to get a few of them up and running in the game.