Jump to content

Like
11Likes
Dislike
Leading the Target

Peer Reviewed by Madhed, Norman Barrows, Brain


deflection math geometry target leading leading the target
How do you compute where you have to aim to hit a moving target with a finite-speed projectile? This is a common question on gamedev.net's forums. This article presents a procedure to solve this problem and some variations thereof.

2: Adsense

Where should we aim if we want to hit a moving target with a finite-speed projectile? This is one of the recurrent questions from beginner game developers. If we naively aim at the target's current position, by the time our projectile gets there the target will have moved, so we need to aim ahead of the target's current position. The technical name for the technique is "deflection", but most people use "leading the target". Wikipedia page here.

There are several variations of the problem, where perhaps the projectile is a missile that needs to accelerate, or where the shooter is a turret that is currently aiming in some direction and needs time to aim somewhere else... We'll cover the simple case first, and then we'll present a general template for solving variations of the problem.

Plain-vanilla deflection


Let's assume the shooter can aim and shoot anywhere instantly, the target is moving at a constant velocity and the projectile will travel at a constant velocity too. We are given as inputs the target's current position, its velocity and the speed of our projectile. We'll use coordinates where the shooter is at the origin and has zero velocity.

First-order correction


As mentioned before, if we naively aim at the target's current position, by the time the projectile gets there, the target will have moved. We can compute how long it will take for the projectile to get to the target's current position, compute where the target will be then and aim there instead.

Position compute_first_order_correction(Position target_position, Vector target_velocity, float projectile_speed) {
    float t = distance(Origin, target_position) / projectile_speed;
    return target_position + t * target_velocity;
}

This simple piece of code is probably good enough in many cases (if the target is moving slowly compared to the projectile speed, if the target is moving perpendicularly to the shooter-to-target vector, or if we want to sometimes miss because a more precise solution would be detrimental to the fun of the game).

Iterative approximation


For a more precise solution, you could iterate this first-order correction until it converges.

Position iterative_approximation(Position target_position, Vector target_velocity, float projectile_speed) {
    float t = 0.0f;
    for (int iteration = 0; iteration < MAX_ITERATIONS; ++iteration) {
        float old_t = t;
        t = distance(Origin, target_position + t * target_velocity) / projectile_speed;
        if (t - old_t < EPSILON)
            break;
    }
	
    return target_position + t * target_velocity;
}

Computing the answer directly


In the iterative approximation, we would stop if we found a place where old_t and t match. This gives us an equation to solve:

t = distance(Origin, target_position + t * target_velocity) / projectile_speed

Let's do some computations to try to solve it.

t = sqrt(dot_product(target_position + t * target_velocity, target_position + t * target_velocity)) / projectile_speed

t^2 * projectile_speed^2 = dot_product(target_position + t * target_velocity, target_position + t * target_velocity)

t^2 * projectile_speed^2 = dot_product(target_position, target_position) + 2 * t * dot_product(target_position, target_velocity) + t^2 * dot_product(target_velocity, target_velocity)


This is a second-degree equation in t which we can easily solve, leading to the following code:

// a*x^2 + b*x + c = 0
float first_positive_solution_of_quadratic_equation(float a, float b, float c) {
  float discriminant = b*b - 4.0f*a*c;
  if (discriminant < 0.0f)
    return -1.0f; // Indicate there is no solution                                                                      
  float s = std::sqrt(discriminant);
  float x1 = (-b-s) / (2.0f*a);
  if (x1 > 0.0f)
    return x1;
  float x2 = (-b+s) / (2.0f*a);
  if (x2 > 0.0f)
    return x2;
  return -1.0f; // Indicate there is no positive solution                                                               
}

Position direct_solution(Position target_position, Vector target_velocity, float projectile_speed) {
    float a = dot_product(target_velocity, target_velocity) - projectile_speed * projectile_speed;
    float b = 2.0f * dot_product(target_position, target_velocity);
    float c = dot_product(target_position, target_position);
    
    float t = first_positive_solution_to_quadratic_equation(a, b, c);
    if (t <= 0.0f)
        return Origin; // Indicate we failed to find a solution
	
    return target_position + t * target_velocity;
}

The general case


There are many variations of the problem we could consider: Accelerating targets, accelerating projectiles, situations where it takes time to aim at a new direction... All of them can be solved following the same template.

The things that could change can be encoded in two functions:
  • position_of_target_at(time)
  • time_to_hit(position)
All we are really doing is finding a time t at which the following equation holds:

t = time_to_hit(position_of_target_at(t))

We then compute where the target will be at time t and aim there.

Just as before, we could do a first-order correction, use iterative approximation or solve the problem directly. It might be the case that an analytical solution can be found, like we did in the previous section, but things can get messy quickly and you may have to resort to a numerical solution.

Conclusion


This article covered three methods to implement deflection in your games: First-order correction, iterative approximation and directly finding the solution. You'll need to use some judgement to decide which one to use. Hopefully this article gives you enough to make an informed decision.

Article Update Log


30 Oct 2015: Initial release
4 Nov 2015: Minor fixes

About the Author(s)

Álvaro Begué is a mathematician and programmer with 15 years of professional experience, but not in games (maybe one day...).

License

GDOL (Gamedev.net Open License)

7 Comments

Nov 02 2015 03:49 PM

This article needs pictures and diagrams to show what is happening mathematically. The math equations should also be equations, not lines of code. It should also show some considerations towards game difficulty and how to compensate for changes in target velocity. What are the pros and cons of the different techniques for target seeking? If a missile can change orientation over time, how does its turning radius affect its tracking capabilities? How does speed play a factor into that? Should the missile AI take speed and tracking capabilities into account when deciding how to pursue a target?

Nov 02 2015 06:30 PM
First of all, thank you for your comment. You bring up lots of things, so I'll answer in one short paragraph for each.

I am a big fan of diagrams. I didn't think about adding them here, but it would probably make things more clear for others, so I will think of what diagrams to add.

In what sense are those "lines of code" not equations? I know most people obscure things by using single-letter names when doing math, but long names are perfectly good. I do a lot of math as part of my job, and I use meaningful names all the time.

Game difficulty is outside the scope of this article.

Discussing pros and cons could be a nice addition; I'll think about what I would write about that.

Missile tracking is not exactly the same problem we are tackling here, although it is a related problem. I will probably not get into that because I want to keep the article relatively short and to the point.
Nov 02 2015 06:42 PM

diagrams and mathematical notation versions of the formulas would be a nice addition.

 

this is basically simultaneous solution of parametric equations, right? its been too long since i did this stuff in school.

 

anyway, i'm signing off on it. but diagrams and math notation would be cool.

Nov 03 2015 11:31 AM

Without the equation how can I know what the code does and if it is correct?

Nov 04 2015 02:34 AM

A great article describing a very useful function with code that can actually be used.

 

I much prefer to see code rather than mathematical equations. I am a programmer and not a mathematician so I appreciate the problem being solved in simple code.

 

If I had the equations, and I could understand them, I would not need a tutorial like this in the first place ^_^

Nov 04 2015 05:14 AM

An article needs to tell its story with pictures, words, formulas, and working code.  This article is a good start on a good topic.  

 

I feel it needs a picture for each situation and a complete set of working code.  The general case, especially, should be expanded.  Or the article should only discuss one of the cases explicitly and not hint at a solution for other cases.

 

For several years, I worked on a 2-D space shooter where agents actively shot at and pursued enemies.  So this topic is something I am glad to see discussed.  It applies not just to the 2-D case, but the 3-D case as well.  I ended up leveraging a lot of that information in a different game called Cannon Clash

 

For the case of a non-rotating shooter, hitting a position in the future has a closed form solution.  

 

For the more general case of a rotating shooter, I know of at least one iterative solution (I could not find a closed form solution) described here (this article is posted on gamedev.net as well).  

Nov 17 2015 11:17 AM
I'd love it if you gave an example of the iterative solution for the general case. I don't think that it is immediately obvious to the reader how you would encode variable acceleration (of either target or projectile) or limited turn rate of the shooter into the form you suggest.

Note: GameDev.net moderates article comments.