• ### What is your GameDev Story?

This topic is 4668 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Ok so I've been scouring the net for an answer to a projectile leading problem. I haven't had much luck finding stuff, but I found a solution here that I would like to know the origins of. This is a really old thread I'm referencing, but it's about all I can find on the subject. The following was contributed by member TerranFury about 4 years ago: I did this quickly, so I may have made a mistake, but I think I solved the 3D equivalent. The solution is a vector of magnitude k, where k is the speed of the projectile. I use C-style struct notation to refer to A (the target) and B (the projectile). A 'v' member is a vector; each vector has x, y, and z component members. Most things should be self explanatory; if you have any questions post them. I think I've fixed any errors... D = B.initpos - A.initpos L = |A.v|2 - k2 G = 2(A.v * D) t = |[G + sqrt(G2 - 4L * |D|)] / (2L)| B.v = A.v - D/t So my question is, where does this derivation come from. How exactly does he arrive at the quadratic equation for this problem? Is there some basic algabraic or geometric principle I'm missing here? Any explanation at all would be very appreciated. Thanks :)

##### Share on other sites
someone knows the answer to this i'm sure. I've seen this equation in a few places, I just want to know where it comes from...bump :)

##### Share on other sites

(My solution is a bit different, but I guess the same principles apply.)
Basically, you have to solve the equation system:

(I)  A + tV = B + tW(II) V.V = k^2("." is dot product, "^" is power)A: initial position of projectile V: velocity vector of projectile (unknown)B: initial position of targetW:  velocity vector of targetk: speed of projectile (scalar)t: time to impact (unknown, scalar)We assume that D has a length > 0 and therefore |t| > 0.Divide (I) by t:A/t + V = B/t + W==> V = (B - A)/t + W = Du + W, where D = B-A and u = 1/tusing (II):==> k^2 = V.V = (D.D)u^2 + 2u(D.W) + (W . W)==> u^2 + 2u(D.W)/(D.D) + [(W.W) - k^2]/(D.D) = 0Solve this quadratic equation for u. Discard  negative solutions. If you still have two solutions, use the larger one (-> smaller t). Then V = Du + W.

##### Share on other sites
I actually found a more intuitive answer to the problem. But i'm still unclear on the derivation. Here's an answer given by jack_1313:

//starting position
//bullet speed
//target position
//target velocity
Vector2D LeadTarget( Vector2D sp, float bs, Vector2D tp, Vector2D tv )
{
Vector2D D = tp - sp;
float E = D.Dot( D );
float F = 2 * tv.Dot( D );
float G = bs * bs - tv.Dot( tv );
float t = ( F + sqrt( F * F + 4 * G * E) ) / ( G * 2 );

return D / t + tv;
}

ok so the first part's easy: Vector2D D = tp - sp; this just makes the vector from the source to the target.

the next line requires pretty good knowledge of dot products and vectors. float E = D.Dot(D);

Dotting a vector with itself will result in the squared magnitude of that vectore (the length squared). So this is the squared distance between the source and the target (squared so we can avoid square roots until the end).

this is where it gets hairy... float F = 2 * tv.Dot(D); so he projects the targets velocity vector onto the vector we just created (D). He then multiplies it by 2. I'm thinking this is just him 'leading' the target (not sure why 2 is the right choice, seems rather arbitrary).

then comes the big dog: float G = bs * bs - tv.Dot(tv); again he dots the vector with itself giving us the squared magnitude of the vector. He then subtracts this squared distance from the squared speed of the bullet. I'm not sure why he does this....(I'm thinking all of this has something to do with Pythag)

then he uses the quadratic equation to find at which point the line segments intersect (quadratic equation returns the root of a polynomial, i.e. when it crosses the x axis, thus making y == 0). When this value is 0, we have an intersection and thus we know the time.

the return value is also baffling me...he divides the original distance by the time at which they would intersect, and then adds to it the targets velocity vector.

Sorry for the long post, but this is a very interesting problem, i'm suprised there's not more discussion on it since it's a fairly common issue (or at least I would think so).

##### Share on other sites
Hmm i remember i solved it once but don't remember exactly how. Anyway, it's not too complicated, i'll re-solve:

First, use coordinate frame where projectile is fired from 0,0
g is gravity (9.8) , t is time, v is velocity, α is angle, c=cos(α), s=sin(α), u is speed of projectile, p is target position (relatively to launch point of course). Later we will use T=tan(α) , don't confuse with time.

We have equations of motion of projectile:
x=v.x*t
y=v.y*t - g*t2/2

so from there we can make equations
v.x*t = p.x
v.y*t - g*t2/2 = p.y
v.x2 + v.y2 = u2

we can rewrite equations as

u*c*t = p.x
u*s*t - g*t2/2 = p.y
c2+s2 = 1

let's try solving it, from first equation we can get t=p.x/(u*c) and substitute into second thus eliminating t
u*s*p.x/(u*c) - g*(p.x/(u*c))2/2 = p.y

p.x*s/c - g*(p.x/(u*c))2/2 = p.y
c2+s2 = 1

if i recall correctly i spotted s/c = tan(α) and decided to solve for tangent.
********************** some useful identity
before doing that we need to find how to get c^2 from tangent so we can then replace c^2 by some expression with only tangent it it:
tan(α) = sin(α)/cos(α) = sqrt(1-cos2(α))/cos(α) = sqrt(1/cos2(α) -1)
so
1/cos2(α) - 1 = tan2(α)
Just lovely, even better, we eliminate the division too!
1/cos2(α)=tan2(α)+1
******************

Let, to shorten things a little, T=tan(α) . We won't use time anymore so that shouldn't be confusing.

so we get
p.x*T - g*p.x2/(2*u2) * 1/c2 = p.y
then finally
p.x*T - g*p.x2/(2*u2) * (T2+1) - p.y = 0

-g*p.x2/(2*u2) * T2 + p.x*T - (p.y+g*p.x2/(2*u2)) = 0

and we have

A=-g*p.x2/(2*u2)
B=p.x
C=-(p.y+g*p.x2/(2*u2))

T= (-B (+-) sqrt(B2 - 4*A*C))/(2*A)

Simplify as you feel like.
Then, to get velocity vector take (1,T) , normalize it, and multiply by speed.
Note: it is unlikely that above contain mistakes, but i'll probably recheck it later to make sure. If you wish you can write unit-test to make sure.

edit:
whoops, i gave solution to wrong problem.[lol]

You're just shooting at moving target, without any gravity? that's very easy. In fact i've been misleaded by mention of ballistics etc. Will post next one.

I never make stupid mistakes, only very, very clever ones... -- Dr Who.
edit: fixed missing square root typo
edit: and another typo in same place.

[Edited by - Dmytry on April 7, 2006 2:26:49 AM]

##### Share on other sites
Whoops, i misunderstood what you want. I thought you have gravity and want to find firing angle...[lol]
if you just want shooting at moving target without any gravity, that's actually quite easy. We just get ray-sphere intersection in the end(it's kind of sort of intuitive really).

We need to find some v that for some time t both equations is true:
v . v = speed^2
v*t=target_p+target_v*t;
divide both sides[of second equation] by t and let u=1/t

v . v = speed^2
v=target_p*u+target_v;
It's just ray-sphere intersection; combine equations and you get
|target_p*u+target_v|2=speed2

All allowed values of v is on sphere with center in 0,0,0 and radius speed; we just need to find point on this sphere that is point of intersection of sphere with line (target_p*u+target_v). If you can derive ray-sphere intersection yourself, problem solved.
edit: and there's derivations for ray-sphere intersection.
|target_p*u+target_v|2=speed2
unroll magnitude squared into dot product
(target_p*u+target_v).(target_p*u+target_v)=speed2
open braces (vector algebra there) we get quadratic
(target_p . target_p)*u^2 + 2*target_p.target_v * u + target_v.target_v - speed2 = 0
so we get
A=target_p . target_p
B=2 * target_p.target_v
C=target_v.target_v - speed2
and just plug into quadratic and simplify.
Then when you have u use
v=target_p*u+target_v;

[Edited by - Dmytry on April 2, 2006 12:06:53 PM]

##### Share on other sites
Quote:
 Original post by DmytryA=-g*p.x2/(2*u2)B=p.xC=(p.y+g*p.x2/(2*u2))T= (-B2 (+-) (B2 - 4*A*C))/(2*A)I never make stupid mistakes, only very, very clever ones... -- Dr Who.

I'm more interested in the gravity model but should the final derivation not read:

T= (-B2 (+-) sqrt(B2 - 4*A*C))/(2*A)

##### Share on other sites
Quote:
Original post by niX@BB
Quote:
 Original post by DmytryA=-g*p.x2/(2*u2)B=p.xC=(p.y+g*p.x2/(2*u2))T= (-B2 (+-) (B2 - 4*A*C))/(2*A)I never make stupid mistakes, only very, very clever ones... -- Dr Who.

I'm more interested in the gravity model but should the final derivation not read:

T= (-B2 (+-) sqrt(B2 - 4*A*C))/(2*A)

whoops, typo! [lol]

##### Share on other sites
Whoops seems I've spotted another typo...

Quote:
 C=(p.y+g*p.x2/(2*u2))

C=-(p.y+g*p.x2/(2*u2))

I'm still trying to get these equations working- I'll try posting some of the source I've derived from this post tomorrow.

##### Share on other sites
lol. i'm is not sure it all works now so i'll be writing test. Actually i wasn't very carefull as it was written just to give idea on the derivations assuming person already has all the working code.
edit: another typo. instead of -B^2 in quadratic there of course should be -B , (i spotted it when i were writing code for test. i usually check things when writing to the code) In my defense, it is rather painful to write B< sup >2< /sup > in the HTML and even more painful to look through, so i were copypasting 2
Another thing, p.x must be positive (which, though, comes automatically if you're working in 3D and are using horizontal distance).

[Edited by - Dmytry on April 7, 2006 3:10:08 AM]

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 9
• 15
• 14
• 46
• ### Forum Statistics

• Total Topics
634060
• Total Posts
3015300
×