Calculating Target Lead
Author
Ok, unfortunately my maths ability isn't the best, otherwise I could probably work this out on my own, so I have come here for a gentle hand or pointer to some information.
I am trying to calculate the "leading" hint in a 3D space game I'm writing.
Ship A is flying along. I can read it's speed and direction at any time.
Ship B (the player) is at another point in space, looking at ship A.
How do I caculate the point where the player should aim his gun in order to hit ship A?
If Ship A were 10km directly in front of the player, heading right at 90 degrees to the player at say 100 m/s, and the players bullet flies at 1km/s, it would take the bullet 10s to reach where Ship A was 10s ago, now a km behind it.
so if the player were to aim at whatever angle {10,1} forms, it would now take longer to reach Ship A, so the player would actually need to aim even further to the right.
I'm a little perplexed by this one, does anyone have any suggestions?
Thanks in advance.
another example :
http://members.gamedev.net/oliii/ai_aim.zip
trying to put it quickly, it's a second order equation.
you have a target moving in a linear fashion
P(t) = P + V * t
you have your ship, at position O, and moving at speed |w|
unknowns is t, the time of interception, and the point of interception P(t).
at time of interception t, the position of the target and your current original position (imagine the ship being stationary) will be at distance equal to (w * t).
||P(t) - O|| = (w * t)
So, working with squared distances, you have
(P(t) - O)^2 = (w * t)^2
develop and you have :
((P - O) + V * t)^2 = (w*w) * t^2
((P - O) + V * t)^2 - (w*w) * t^2 = 0
that's a second order equation in the form a.t^2 + b.t + c = 0
where
a = (V.V)-(w*w)
b = (P-O).(V) * 2
c = (P-O).(P-O)
to solve it, d = b^2 - 4*ac
if(d < 0) there is no solution. i.e., The target moves too fast.
else you have two solutions.
t0 = (-b - sqrt(d)) / (2*a)
t1 = (-b + sqrt(d)) / (2*a)
If t0 and t1 are both negative, it means the target is moving behind the ship.
else the time of interception would be the minimum positive value between t0 and t1.
t = (t0 < 0.0f)? t1 : (t1 < 0.0f)? t0 : min(t0, t1);
then the point of interception is simply :
Pintercept = P + V * t, and you can display a crosshair there to tell the ship where to fire to hit the target, and try to align the ship with that point if it's for AI.
If both t0 and t1 are positive, they are both valid times of interception. You don't necessary have to choose the smallest of the two. For example, if the largest gives you the least deviation with your current ship direction, that might be a better candidate. The time to interception will be greater, but your ship will have to move less to align towards the point of interception, which may or not be better depending on what you want to achieve.
If it's bullets, it's the same thing, except you want w to be the speed of the bullet.
Also, this algo is exactly the same for 2D or 3D. It's just 3D vector equations.
[Edited by - oliii on August 1, 2007 5:39:41 AM]
http://members.gamedev.net/oliii/ai_aim.zip
trying to put it quickly, it's a second order equation.
you have a target moving in a linear fashion
P(t) = P + V * t
you have your ship, at position O, and moving at speed |w|
unknowns is t, the time of interception, and the point of interception P(t).
at time of interception t, the position of the target and your current original position (imagine the ship being stationary) will be at distance equal to (w * t).
||P(t) - O|| = (w * t)
So, working with squared distances, you have
(P(t) - O)^2 = (w * t)^2
develop and you have :
((P - O) + V * t)^2 = (w*w) * t^2
((P - O) + V * t)^2 - (w*w) * t^2 = 0
that's a second order equation in the form a.t^2 + b.t + c = 0
where
a = (V.V)-(w*w)
b = (P-O).(V) * 2
c = (P-O).(P-O)
to solve it, d = b^2 - 4*ac
if(d < 0) there is no solution. i.e., The target moves too fast.
else you have two solutions.
t0 = (-b - sqrt(d)) / (2*a)
t1 = (-b + sqrt(d)) / (2*a)
If t0 and t1 are both negative, it means the target is moving behind the ship.
else the time of interception would be the minimum positive value between t0 and t1.
t = (t0 < 0.0f)? t1 : (t1 < 0.0f)? t0 : min(t0, t1);
then the point of interception is simply :
Pintercept = P + V * t, and you can display a crosshair there to tell the ship where to fire to hit the target, and try to align the ship with that point if it's for AI.
If both t0 and t1 are positive, they are both valid times of interception. You don't necessary have to choose the smallest of the two. For example, if the largest gives you the least deviation with your current ship direction, that might be a better candidate. The time to interception will be greater, but your ship will have to move less to align towards the point of interception, which may or not be better depending on what you want to achieve.
If it's bullets, it's the same thing, except you want w to be the speed of the bullet.
Also, this algo is exactly the same for 2D or 3D. It's just 3D vector equations.
[Edited by - oliii on August 1, 2007 5:39:41 AM]
Author
Thanks so much for the info guys!
I don't fully understand what you have presented but I can see that it is quite clear, so I'm off brushing up on my linear algebra and calculus.
I don't fully understand what you have presented but I can see that it is quite clear, so I'm off brushing up on my linear algebra and calculus.
Author
Ok I have a question or two after refreshing some of my math...
I assume that P(t) is a polynomial function.
I assume that |w| is an absolute value, not a vector!
|P(t) - O| = w * t
um.. I'm not sure what this means exactly. Did O get transformed from a vector to something else?
a = (V.V)-(w*w) // Is V.V a dot product?
I'm slowly working this out!
I assume that P(t) is a polynomial function.
I assume that |w| is an absolute value, not a vector!
|P(t) - O| = w * t
um.. I'm not sure what this means exactly. Did O get transformed from a vector to something else?
a = (V.V)-(w*w) // Is V.V a dot product?
I'm slowly working this out!
I should have written.
||P(t) - O|| = (w * t)
w is speed. It's a positive, real number.
||P(t) - O|| is the norm of the vector (P(t)-O), or equally, the distance between vector P(t) and O.
-> so, if your missile/bullet travels at constant speed w, after time t, the distance between your target at time t (P(t)) and from where the bullet originated (vector O) should be (w * t).
P(t) is a polynomial of the first order. It's a linear vector equation.
(V.V) is a dot product. V^2 = V.V
To make things simpler, the terms of the original equation are squared. if distance from A to B = d, then distance SQUARED of A to B = d^2.
Similarly, you can use the same system of equation if you want to consider acceleration (for example, gravity).
if target is accelerating...
P(t) = P = V * t + 0.5 * A * t^2
if bullet is accelerating...
distance = (w * t + 0.5 * a * t^2)
that brings you to solving a fourth order polynomial equation. So kinda more complicated.
EDIT : Fixed the original post.
||P(t) - O|| = (w * t)
w is speed. It's a positive, real number.
||P(t) - O|| is the norm of the vector (P(t)-O), or equally, the distance between vector P(t) and O.
-> so, if your missile/bullet travels at constant speed w, after time t, the distance between your target at time t (P(t)) and from where the bullet originated (vector O) should be (w * t).
P(t) is a polynomial of the first order. It's a linear vector equation.
(V.V) is a dot product. V^2 = V.V
To make things simpler, the terms of the original equation are squared. if distance from A to B = d, then distance SQUARED of A to B = d^2.
Similarly, you can use the same system of equation if you want to consider acceleration (for example, gravity).
if target is accelerating...
P(t) = P = V * t + 0.5 * A * t^2
if bullet is accelerating...
distance = (w * t + 0.5 * a * t^2)
that brings you to solving a fourth order polynomial equation. So kinda more complicated.
EDIT : Fixed the original post.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
