AI Aiming Problem

My brother and I were working on an aiming problem that was quite interesting and similar to some things we worked on in our AI class. The problem is for two tanks with constant velocity, initial position, and projectile speed for tank 1's weapon (which can be fired from the turret in any direction), where should we aim in order to hit tank 2?

First we can simplify this by calling tank 1's center the origin. Then we just need to find the relative position to aim at. With this assumption tank 2's velocity and position will be relative to tank 1 (which can easily be calculated by tank2.pos - tank1.pos, and tank2.vel - tank1.vel where pos is the position vector and vel is the velocity vector for a tank). We will call tank 2's position x = (x1, x2) and velocty v = (v1, v2). We will call the bullet's speed s.

The solution can be expressed as target y, with

y = x + vt

where t is the time it will take for the bullet to travel that distance. I will not refer to this again, as the interesting part of the problem is finding t. But the algorithm should use this to calculate the position of the target once we find t. (In the game the AI specifies a target and there already exists a function to fire at that target).

It took a lot of work to find the appropriate way to express these relationships (including simplifications) in order to find a solvable equation, but here is the solution. It came from thinking of this in terms of polar form, where each position (bullet and tank2) is expressed as a pair of distance and angle (d, theta). But actually we only need the distance to be equal. Since we can fire in any direction, we can think of our projectile going out in all directions at once.

Assume we fire at time t=0. Then when the distance of the projectile from the origin (tank 1) is equal to the distance of tank2 from the origin, a solution exists. So for the distance of tank 2 relative to tank 1 T2(t)= |x + vt|, and the distance of the bullet of tank 1 relative to itself B(t)=ts, we get

B(t)=T2(t)

ts = |x + vt|

ts = sqrt((x1 + v1t)^2 + (x2 + v2t)^2)

(ts)^2 = (x1 + v1t)^2 + (x2 + v2t)^2

0 = (v1^2 + v2^2 - s^2)t^2 + 2(x1v1 + x2v2)t + x1^2 + x2^2

a = v1^2 + v2^2 - s^2

b = 2(x1v1 + x2v2)

c = x1^2 + x2^2

t1 = -(b - sqrt(b^2 - 4ac))/(2a)

t2 = -(b + sqrt(b^2 - 4ac))/(2a)

And we want the smallest of t1 and t2 that is bigger than 0 and less than the lifetime of the bullet. Also if a = 0 then we have a linear case with solution

t = -(x1^2 + x2^2)/(2*(x1v1 + x2v2)

Anyways, I was proud of myself for being able to find the solution after some work. My brother already tested it and it works better than the previous version, which was to approximate 2 times. First one based on the time it would take for the projectile to reach the tank at its current position. Second the time it would take to reach the position it would be at after that first time. This worked pretty good, but I knew we could find the time exactly (for this simple model).

The problem is still open as this only works for one type of "floating" kind of projectile. Some projectiles take into account gravity, and the arc angle is calculated automatically based on your target. So the time it takes depends on the future position, and the arc needed to reach that. And that time dictates what the future position is. So we have a similar problem, where we could use the solution above to estimate this time, and iterate, but that would only be an approximate solution.