Projectile Interception

Warning: this post is math intensive so if you’re not interested in math and/or programming you might not enjoy this.

In an earlier post Brendan had mentioned how the AI utilize an advanced algorithm for shooting targets. This post will explain how AI in Twelve are able to consistently land shots when the lasers they shoot have a significant travel-time. It describes the interception algorithm used to determine where the AI should shoot. This is intended to benefit other developers trying to program a similar algorithm for their games.

The math used in this post does not exceed a high school level education (at least that’s the level of education I’m at). It's linear algebra that should be simple enough for most programmers to follow.

When designing an algorithm it usually helps to explicitly state the problem being solved. In this case, we're trying to make AI that can shoot a moving target. This is hard because the shots the AI takes do not travel instantly. For a shot to hit a target it has to be fired towards the target’s future position rather than their current position.

A simple example is the rocket launcher in most first person shooters. Unlike bullets, rockets take time to travel distances. To hit a target the player must lead their shot by a certain distance to compensate for the speed of the rocket. The purpose of this algorithm is to precisely determine the direction a shooter needs to shoot for the projectile to intercept the target.

Given the position of the shooter, the position and velocity of the target, and the speed at which a shot travels, we want to find a unit vector that is the direction the shooter needs to shoot to hit its target.

Here’s a diagram representing an example scenario:

For simplicity we'll assume that the unit of distance is meters and the unit of time is seconds. The blue spacecraft is the shooter and the red spacecraft is the target. The green vector is the velocity of the target. The unit for velocity is meters / second so its magnitude represents how many meters the target will move in 1 second. The dotted line represents all the future positions of the target (this assumes it travels at a constant velocity). We can predict exactly where the target will be after any amount of time using the following relation:

The shooter’s projectile travels at a specific speed, which means the time it takes for the projectile to travel between where the shooter shot from and the target will depend on the distance between the two. In short, the travel time of the projectile depends on the distance it needs to travel. If we know this travel time, we can predict where the target will be after that amount of time, and we can come up with a vector pointing from the shooter to the future position of the target. Here’s a diagram to better illustrate the problem:

Each purple line represents a possible path for the projectile to take. A projectile that travels instantaneously would take the path on the very left. A projectile that travels slower would need to take a path more towards the right to compensate for its slower speed. It’s easy to see that for a projectile of speed x, there's only one possible path that it could take ensuring it will hit the target. Each of these paths has a different length, which means a projectile of the same speed will have a different travel time along each one.

Now we have simplified the problem. We know that we’re looking for the travel time of the projectile so that we can know where the target will be and determine what direction to shoot. The new problem is that the travel time depends on the distance the projectile is traveling. This distance depends on how much the target has moved, which in turn, depends on the amount of time elapsed.

To determine the travel time of the projectile, we will consider the diagram a triangle (3 points):

- The first point is the current position of the target. In the example this is at the top left.

- The second point is the position of the shooter. In the example this is at the bottom.

- The last point is the point at which the hit occurs. This is a point along the dotted line.

This triangle is useful because the length of the right side is the distance the projectile needs to travel. Knowing the distance, we can simply divide it by the speed of the projectile to get the travel time.

Now we have simplified the problem even further. Finding the direction to shoot is the same as finding the length of the right side of the triangle. To find this length, we will use the law of cosines:

Side (a) is the length we are looking for. This is the side on the very right. We will consider the top side to be side (b) and the left side to be side (c). We can see that side (c) is constant; it’s simply the distance between the shooter and the original position of the target. Since (A) is the angle between side (b) and side (c), this is also constant. Since the angle is constant we know that -2cos(A) will be constant. We can simplify the equation by expressing it with the constants:

Side (b) is not a constant size. The length of this side is a function of the time elapsed (as we saw in the very first equation). The length of side (a) is also not constant, it’s a function of the time elapsed. We can express these sides as:

Where (s) is the speed of the projectile, (||v||) is the speed of the target, and (t) is the time elapsed since the shot. We can now express the whole equation as a function of (t):

Now we can clearly see that the relation is a quadratic equation where (t) is the variable and all the other values are constant. Solving for (t) is trivial and it gives us the elapsed time. Since this equation is quadratic there will exist two values of (t), one that's negative and the other that's positive. Since in real life time can only progress forward (at least until the device is complete), we're only interested in the positive value of (t).

Edit: As many readers have pointed out, this is only true if we assume that the projectile has a greater speed than the target. If the speed of the projectile is less than or equal to that of the target, the algorithm must be extended to handle each of the two new cases.

Once we know the elapsed time we plug it into the original equation:

This will give us the future position of our target. Then we can simply subtract the shooter’s position from the target’s future position to get a vector pointing towards the target’s future position. Normalizing this vector gives us the direction the shooter needs to shoot. Assuming the shooter can shoot in that direction, and that the target’s acceleration remains null, after (t) seconds the target will be hit.

Here is an example of an implementation in C# straight from Twelve’s codebase:

That concludes the explanation of the interception algorithm used in Twelve. Since the direction of the vectors themselves is not too relevant and we're mainly focused on the length of the sides of the triangle, if you’re really clever this algorithm can easily be extended to function in a 3D environment. Hopefully this helps other programmers struggling with a similar problem.

-Michael