Hello, I was referencing these URLs: http://www.gamedev.net/community/forums/topic.asp?topic_id=401165 http://www.gamedev.net/community/forums/topic.asp?topic_id=312251 however, neither of these algorithms seem to be working. First of all, 'a' is the speed of the target minus the speed of the bullet -- this means that even if both are moving in different directions, if their velocity lengths are equivalent, a is 0, which causes a divide by 0 later on. I simply cannot get a correct value from this equation. Any advice? I solved it to this: P0 = Target Position P1 = Player Position P2 = New Position V0 = Target Velocity V1 = Bullet Speed t = time P2 = P0 + (V0 * t) P2 = P1 + (norm(P2 - P1) * v1 * t) but that's unsolvable. The problem is that bullet speed appears to be misused everywhere, but the bullets VELOCITY is it's speed times the vector to where the target will be... which we obviously don't know. The equations as shown before though from other threads don't work at ALL in my simulation. [Edited by - Ameise on October 26, 2009 1:31:29 AM]

P0 = Target Position
P1 = Player Position
P2 = New Position

V0 = Target Velocity
s = Bullet Speed (I can't get myself to call a speed "V")

t = time


The way I think about it,

P2 = P0 + t * V0
distance(P2,P1) = t * s

Now you substitute the first expression for in the second and solve for t. You get

dot(P2-P1, P2-P1) = t^2 * s^2
dot(P0-P1 + t*V0, P0-P1 + t*V0) = t^2 * s^2
dot(P0-P1, P0-P1) + 2*dot(P0-P1, V0)*t + dot(V0,V0)*t^2 = s^2*t^2
(dot(V0,V0)-s^2)*t^2 + 2*dot(P0-P1, V0)*t + dot(P0-P1, P0-P1) = 0

In the case where the bullet and the target have the same speed, the term in t^2 is 0, so you are left with a first-degree equation. The solution is single then, and it's

t = -dot(P0-P1, P0-P1)/(2*dot(P0-P1, V0))

Sorry my code didn't consider this case. Bullets are faster than targets in all the examples I was thinking about when I wrote it.

So, when the bullets speed is greater than the targets velocity length, use the function that has the Divide afterwards, and when it is less than or equal, use this function?

Yeah, because if you are flying towards an object your bullet speed will be higher than his velocity possibly, which is why you should use a relative speed, I suppose.

Was getting really weird bugs though... like... even when I set the bullet speed to faster than it, the system whacked out.

Ahh, I see now that I have time to fully read your reply.

If my projectile is slower than the target, but can hit it, that means that either the target is not moving away from me (hence is staying at the same distance or moving towards me)... hence there is only one place I can aim to hit it, whereas if the projectile is FASTER than the target, I can have multiple places at which to aim possibly.

The reason it's bad to assume the projectile is slower is that if it's being fired from a moving platform (IE, a spacecraft), it inherits its parent object's velocity.

So, is this correct:

iif ProjectileSpeed != targetVelocity.length()
t = (sqrt(dot(P0-P1, P0-P1)*s^2-dot(P0-P1, P0-P1)*dot(V0,V0)+dot(P0-P1, V0)^2)+dot(P0-P1, V0))/(s^2-dot(V0,V0))
OR
t = -(sqrt(dot(P0-P1, P0-P1)*s^2-dot(P0-P1, P0-P1)*dot(V0,V0)+da^2)-dot(P0-P1, V0))/(s^2-dot(V0,V0))

else
t = -dot(P0-P1, P0-P1)/(2*dot(P0-P1, V0))

What if the projectile speed is less than the target's speed, though... do we still use the second-order functions? Or do we use a modified version thereof?

Also, is the return of dot(x,y) a float or a vector? I see a lot of dot(foo) * dot(bar), and I'm wondering if I am multiplying the floating point result or a resultant vector.

[Edited by - Ameise on October 26, 2009 10:00:12 AM]

I haven't read your equations to check their accuracy: I just tried to derive correct ones myself.
Let P10 be the position of the agent moving at a constant velocity, V1. Let P20 be the position of the target which is moving at a constant velocity, V2. The agent agent fires a bullet with a known velocity equal to V( magnitude ). The question is: in which direction should the agent fire the bullet to hit the moving target? When will the bullet hit the target?

Let V3 be the velocity vector of the bullet. We then have for its motion:

P3 = P10 + ( V1 + V3 ) * t (1)

The target motion is described by:

P2 = P20 + V2 * t (2)

When the bullet hit the target, we have: P3 = P2. Which is equivalent to:

P10 + ( V1 + V3 ) * t' = P20 + V2 * t' (3)

If we project this equation along the "x-axis", we have:

P10x + ( V1x + V3x ) * t' = P20x + V2x * t'
=>

V3x = ( P20X - P10x ) / t' + ( V2x - V1x )

or

V3x = dPx / t' + dVx (4)

with dP = P20 - P10x and
dV = V2 - V1

Similarly( "y-axis" projection )

V3y = dPy / t' + dVy (5)

Of course, dividing by t' can only be done when it's different from zero.

We know the magnitude of the bullet velocity, hence:

(V3x)^2 + (V3y)^2 = V^2 (6)

(4) and (5) in (6) yield:

( dPx / t' + dVx )^2 + ( dPy / t' + dVy )^2 = V^2 * t'^2
=>...=>

( dVx^2 + dVy^2 - V^2 ) * t'^2 + 2 * ( dVx * dPx + dVy * dPy ) * t' + ( dPx^2 + dPy^2 ) = 0

or

A * t'^2 + 2 * B * t' + C

with

A = ( dVx^2 + dVy^2 - V^2 )
B = ( dVx * dPx + dVy * dPy )
C = ( dPx^2 + dPy^2 )

A second degree equation with respect to t'

The two solutions are:

t' = ( - B +- sqrt( delta ) ) / A

with delta = B^2 - A * C

If delta is strictly superior to zero, there will be two distinct roots. Logically there should only be one positive root in that case( the bullet cannot hit the target along the same direction twice): so the valid root is the positive one.
Having found t', we plug it into equations (4) and (5) to find, V3x and V3y.

There's no need to make assumptions on the magnitude of the velocities of the agent, the target and the bullet: if delta is strictly inferior to zero, then the bullet cannot possibly hit the target.

I've checked the accuracy of the equations with:

P1 = (0,0)
V1 = (0,0)
P2 = (10,10)
V2 = (1,-1)
V = 4

t' = 10 / sqrt(28)
V3x = sqrt(28) + 1
V3y = sqrt(28) - 1

P3x = P2x ~= 11.89m
P3y = P2y ~= 8.11m

Quote:Original post by johnstanp
If delta is strictly superior to zero, there will be two distinct roots. Logically there should only be one positive root in that case( the bullet cannot hit the target along the same direction twice): so the valid root is the positive one.

I thought the same thing the first time I solved this problem, but it's not true. There are situations where a target can be hit by firing at two different locations.

Quote:There's no need to make assumptions on the magnitude of the velocities of the agent, the target and the bullet: if delta is strictly inferior to zero, then the bullet cannot possibly hit the target.

Yes, but if the speeds of the target and the bullet are the same, trying to naively solve the second-degree equation results in a division by zero, because the formula degenerates to a first-degree equation.

Quote:Original post by Ameise
If my projectile is slower than the target, but can hit it, that means that either the target is not moving away from me (hence is staying at the same distance or moving towards me)... hence there is only one place I can aim to hit it, whereas if the projectile is FASTER than the target, I can have multiple places at which to aim possibly.

There can be two valid places to hit a target that is moving faster than your bullets. I can try to provide a numeric example later if you want.

Quote:The reason it's bad to assume the projectile is slower is that if it's being fired from a moving platform (IE, a spacecraft), it inherits its parent object's velocity.

Careful there. What I did assumed a non-moving firing platform. If the firing platform is moving, use a frame of reference where it's not moving.

Quote:So, is this correct:[...]

Yes, that seems correct.

Quote:What if the projectile speed is less than the target's speed, though... do we still use the second-order functions? Or do we use a modified version thereof?

Use the second-degree equation.

Quote:Also, is the return of dot(x,y) a float or a vector? I see a lot of dot(foo) * dot(bar), and I'm wondering if I am multiplying the floating point result or a resultant vector.

It's a scalar ("float", as you say).

Just for fun, if we wanted to add in angular momentum in change in direction, how much more complicated would this equation become?

Quote:Original post by alvaro

Quote:Original post by johnstanp
If delta is strictly superior to zero, there will be two distinct roots. Logically there should only be one positive root in that case( the bullet cannot hit the target along the same direction twice): so the valid root is the positive one.

I thought the same thing the first time I solved this problem, but it's not true. There are situations where a target can be hit by firing at two different locations.

Yes, I forgot to look back at what B is actually: a dot product...So when it's negative and when 0 < A * C < B^2, there are two positive roots...

Knowing that:
A = ( dVx^2 + dVy^2 - V^2 )
B = ( dVx * dPx + dVy * dPy )
C = ( dPx^2 + dPy^2 )

This would do the trick:

dV = ( 10, -10 )
dP = ( 100, 135 )
V = sqrt(198)
C = dP.dot(dP) = 28225
A = dV.dot(dV) - V.dot(V) = 200 - 198 = 2

B = -350
B^2 = 122500
A * C = 56450

Let
P1 = (0m,0m)
P2 = (100m,135m)
V1 = (11.5m/s,4.56m/s)
V2 = (21.5m/s,-5.44m/s)
V = sqrt(198)m/s

delta = B^2 - A * C = 66050
sqrt(delta) = 257.002
t'1 = ( 350 + 257.002 ) / 2 = 303.501 sec
t'2 = ( 350 - 257.002 ) / 2 = 46.499 sec

V3x = dPx / t' + dVx
V3x1 = 10.3295m/s
V3x2 = 12.1506m/s

V3y = dPy / t' + dVy
V3y1 = -9.5552m/s
V3y2 = -7.0967m/s

P3(t'1) = (6625.42683m,-1515.076992m)
P2(t'1) = (6625.2715m,-1516.04544m)

P3(t'2) = (1099.7292494m,-117.9540133m)
P2(t'2) = (1099.7285m,-117.95456m)

Quote:

Quote:There's no need to make assumptions on the magnitude of the velocities of the agent, the target and the bullet: if delta is strictly inferior to zero, then the bullet cannot possibly hit the target.

Yes, but if the speeds of the target and the bullet are the same, trying to naively solve the second-degree equation results in a division by zero, because the formula degenerates to a first-degree equation.

I was leaving when I posted: I didn't reread myself...I thought about it on my way home. And the first thing I was going to do was to edit my post, in case nobody already noticed the mistake.

[Edited by - johnstanp on October 26, 2009 4:23:34 PM]