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)
  • \$\begingroup\$ 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. \$\endgroup\$
    – Kromster
    Dec 13, 2012 at 12:16
  • \$\begingroup\$ @KromStern: an iterative technique should fire even when there is no exact solution. \$\endgroup\$
    – e100
    Dec 13, 2012 at 12:21
  • \$\begingroup\$ If there's no exact solution, then where do you fire to? Or is that the goal? \$\endgroup\$
    – Kromster
    Dec 13, 2012 at 13:12
  • \$\begingroup\$ 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. \$\endgroup\$
    – e100
    Dec 13, 2012 at 13:26
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Dec 13, 2012 at 13:48


You must log in to answer this question.

Browse other questions tagged .