# How can I use iteration to lead targets?

In my 2D game, I have stationary AI turrets firing constant speed bullets at moving targets.

So far I have used a quadratic solver technique to calculate where the turret should aim in advance of the target, which works well (see Algorithm to shoot at a target in a 3d game, Predicting enemy position in order to have an object lead its target).

But it occurs to me that an iterative technique might be more realistic (e.g. it should fire even when there is no exact solution), efficient and tunable - for example one could change the number of iterations to improve accuracy.

I thought I could calculate the current range and thus an initial (inaccurate) bullet flight time to target, then work out where the target would actually be by that time, then recalculate a more accurate range, then recalculate flight time, etc etc.

I think I am missing something obvious to do with the time term, but my aimpoint calculation does not currently converge after the significant initial correction in the first iteration:

import math

def aimpoint(iters, target_x, target_y, target_vel_x, target_vel_y, bullet_speed):

aimpoint_x = target_x
aimpoint_y = target_y
range = math.sqrt(aimpoint_x**2 + aimpoint_y**2)
time_to_target = range / bullet_speed
time_delta = time_to_target
n = 0

while n <= iters:
print "iteration:", n, "target:", "(", aimpoint_x, aimpoint_y, ")", "time_delta:", time_delta
aimpoint_x += target_vel_x * time_delta
aimpoint_y += target_vel_y * time_delta
range = math.sqrt(aimpoint_x**2 + aimpoint_y**2)
new_time_to_target = range / bullet_speed
time_delta = new_time_to_target - time_to_target
n += 1

aimpoint(iters=5, target_x=0, target_y=100, target_vel_x=1, target_vel_y=0, bullet_speed=100)

• I fail to see how iterative technique can be better than precise quadratic solver, if later is bugfree .. You can always add tweaks to reduce accuracy if you need. – Kromster says support Monica Dec 13 '12 at 12:16
• @KromStern: an iterative technique should fire even when there is no exact solution. – e100 Dec 13 '12 at 12:21
• If there's no exact solution, then where do you fire to? Or is that the goal? – Kromster says support Monica Dec 13 '12 at 13:12
• I meant an iterative technique may be able to fire at the approximated aiming point where a quadratic approach would not find an exact solution. And a near miss may be good enough, e.g. for "explosive" projectiles which will have an area affect. – e100 Dec 13 '12 at 13:26
• If your quadratic doesn't have any roots then surely the best you can do is simple to take the extremum, which will be as close as possible to an actual hit? So you still don't gain anything by using an iterative approximation. – Peter Taylor Dec 13 '12 at 13:48