Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I saw this question: Predicting enemy position in order to have an object lead its target. My situation is a little different though.

My target moves, and the shooter moves. Also, the shooter's velocity is added to the bullets' velocities, i.e. bullets fired while sliding to the right will have a greater velocity toward the right.

What I'm trying to do is to get the enemy to be able to determine where they need to shoot in order to hit the player. Using the linked SO solution, unless the player and enemy are stationary, the velocity difference will cause a miss. How can I prevent that?


Here is the solution presented from the stack overflow answer. It boils down to solving a quadratic equation of the form:

a * sqr(x) + b * x + c == 0

Note that by sqr I mean square, as opposed to square root. Use the following values:

a := sqr(target.velocityX) + sqr(target.velocityY) - sqr(projectile_speed)
b := 2 * (target.velocityX * (target.startX - cannon.X)
      + target.velocityY * (target.startY - cannon.Y))
c := sqr(target.startX - cannon.X) + sqr(target.startY - cannon.Y)

Now we can look at the discriminant to determine if we have a possible solution.

disc := sqr(b) - 4 * a * c

If the discriminant is less than 0, forget about hitting your target -- your projectile can never get there in time. Otherwise, look at two candidate solutions:

t1 := (-b + sqrt(disc)) / (2 * a)
t2 := (-b - sqrt(disc)) / (2 * a)

Note that if disc == 0 then t1 and t2 are equal.

share|improve this question
3  
can you please attempt to condense your question. I know you think you need to give really detailed explanations, but really I got about half way through, and felt that I was reading a text book –  gardian06 May 3 '12 at 7:15
    
Can you please use something like sq() instead of sqr()? It makes it really confusing to read. –  Sam Hocevar May 3 '12 at 8:49
    
@gardian06 The code without any explanation involved is at the end of the question. –  Azaral May 3 '12 at 10:41
    
@Sam Hocevar I replaced all of my variable * variable with std::pow(variable,2). –  Azaral May 3 '12 at 10:41
    
If it works when you are stationary and the target moves, but not when you both move, then subtract your velocity from the target's one to get the relative velocity and use that. –  George Duckett May 3 '12 at 11:55
show 19 more comments

5 Answers

up vote 5 down vote accepted

Okay, let's put some sanity into this. I am afraid you are not making it easy at all, your code does not compile, is inconsistent with regards to variable names (playerVelocityX becomes playerXvelocity after a few lines? what is xVelocity?) and is too verbose. It is basically impossible to debug lest you put considerable effort into it.

So, here are the things to fix:

Bullet speed

The bullet speed must be 30, period. There is no need for the computations you are doing: the change of the frame of reference is precisely there to avoid the complexity. You only add the enemy's velocity after you found a solution, when you go back to the main reference frame.

Solution validity

You are not checking that the time solution is positive.

Numerous coding errors

You are testing time1 and time2 but always using time1 in the results.

You do playerXvelocity - yVelocity which is inconsistent.

You are doing / 2 * a instead of / (2.f * a). This is the worst error and it's why everything is going wrong.

You compute shootx and shooty as the final position of the bullet, whereas what you are looking for is the velocity of the bullet.

Fixed code

float const bulletSpeed = 30.f;
/* Relative player position */
float const dx = playerX - enemyX;
float const dy = playerY - enemyY;
/* Relative player velocity */
float const vx = playerVelocityX - enemyVelocityX;
float const vy = playerVelocityY - enemyVelocityY;

float const a = vx * vx + vy * vy - bulletSpeed * bulletSpeed;
float const b = 2.f * (vx * dx + vy * dy);
float const c = dx * dx + dy * dy;
float const disc = b * b - 4.f * a * c;

shouldShoot = false;

if (disc >= 0.f)
{
    float t0 = (-b - std::sqrt(disc)) / (2.f * a);
    float t1 = (-b + std::sqrt(disc)) / (2.f * a);
    /* If t0 is negative, or t1 is a better solution, use t1 */
    if (t0 < 0.f || (t1 < t0 && t1 >= 0.f))
        t0 = t1;
    if (t0 >= 0.f)
    {
        /* Compute the ship's heading */
        shootx = vx + dx / t0;
        shooty = vy + dy / t0;
        heading = std::atan2(shooty, shootx) * RAD2DEGREE;
        /* Compute the bullet's velocity by adding the enemy's velocity */
        bulletVelocityX = shootx + enemyVelocityX;
        bulletVelocityY = shooty + enemyVelocityY;

        shouldShoot = true;
    }
}
share|improve this answer
    
yeah i retyped my code and noticed i messed a few things up. It isn't that inconsistent in my actual code I promise lol! I did notice the "You are doing / 2 * a instead of / (2.f * a)." last night and fixed that. I am going to give your code a try. I came here after about four hours of trying to figure this out and was in quite an irritated state and I think that is why I typed the code so horribly. –  Azaral May 4 '12 at 12:42
    
I tried this in a simple console output and it isn't working. I copy and pasted it into a fresh project. I added the player and enemy variables that are not declared from your code. Inside the if(t0>=0.f) area I added calculating player x,y and bullet x,y after the line should shoot = true; playerX += playerVelocityX*t0; playerY += playerVelocityY*t0; float bulletX = ((cos(heading * DEGREE2RAD)*bulletSpeed + enemyVelocityX) * t0) + enemyX; float bulletY = ((sin(heading * DEGREE2RAD) * bulletSpeed + enemyVelocityY) * t0) + enemyY; Output is P=(84.8069,93.0386) E=(88.3793,105.132) –  Azaral May 4 '12 at 13:20
    
At this point I wouldn't be surprised if I'm just an idiot. I can accept that. –  Azaral May 4 '12 at 13:21
    
In the above example the original data is: playerX = 50, playerY = 100, playerVelocityX = 20, playerVelocityY = -4, enemyX = 145, enemyY = 67, enemyVelocityX = -5, enemyVelocityY = 10. –  Azaral May 4 '12 at 13:22
    
Do not use bulletSpeed at this point. Replace cos(heading * DEGREE2RAD) * bulletSpeed with shootx. Same for shooty. The reason is because the enemy's velocity is added to the bullet's velocity, its speed is no longer exactly bulletSpeed. In fact you do not need the heading variable at all, it's just helpful for debugging. –  Sam Hocevar May 4 '12 at 13:32
show 5 more comments

Here's an example where I devised and implemented a solution to the problem of predictive targeting using a recursive algorithm: http://www.newarteest.com/flash/targeting.html (I had a stationary shooter but the same approach would work for a moving shooter)

I'll have to try out some of the other solutions presented because it seems more efficient to calculate it in one step, but the solution I came up with was to estimate the target position and feed that result back into the algorithm to make a new more accurate estimate, repeating several times.

For the first estimate I "fire" at the target's current position and then use trigonometry to determine where the target will be when the shot reaches the position fired at. Then in the next iteration I "fire" at that new position and determine where the target will be this time. After about 4 repeats I get within a pixel of accuracy.

share|improve this answer
1  
One advantage of this answer is that even if there is no exact solution, the shooter will still fire around the player's position. +1 for that. –  Sam Hocevar May 5 '12 at 13:57
    
huh I hadn't even thought about that, good point –  jhocking May 5 '12 at 14:33
add comment

This is just a 3D geometry problem.

First you need the relative position and the relative velocity of the shooter and the target:

Pos = TargetPos - ShooterPos
Vel = TargetVel - ShooterVel

Then you need to solve the equation:

Pos + t * Vel = t * FireSpeed * [x , +-sqrt(1-x^2)]

For t and x.

That makes:

x = ( PosX + t * VelX ) / ( t * FireSpeed )

( PosY + t * VelY ) / ( t * FireSpeed ) = +-sqrt(1 - (( PosX + t * VelX ) / ( t * FireSpeed ))^2 )
=>
( PosY + t * VelY )^2 / ( t * FireSpeed )^2 = 1 - (( PosX + t * VelX ) / ( t * FireSpeed ))^2
=>
( PosY + t * VelY )^2 + ( PosX + t * VelX )^2 = ( t * FireSpeed )^2
<=>
( Dot(Vel,Vel) - FireSpeed^2 ) * t^2 + 2 * Dot(Vel,Pos) * t + Dot(Pos,Pos) = 0

The last of those equations is a simple quadratic equation, which you should solve. For each positive result you insert the result into the equation:

FireVector = Vel + Pos / t

This should give you every possible fire vector, where t is the time the shot will take.

Note that if FireSpeed is greater than the magnitude of Vel there will be just one solution, but if FireSpeed is smaller there may be two solutions or none at all, or in special cases just a single double solution.

Edit: Better do the maths right or this answer won't be much good.

share|improve this answer
add comment

As you are only working with 2D physics (no Z velocity), this problem can be greatly simplified. The easy way to do this is to stop thinking about both source and target moving relative to world co-ordinates and to just think of the target moving relative to the source (and keep the source stationary).

Vector TargetInitialPosition = new Vector ( target.X - source.X ,
                                            target.Y - source.Y );
Vector TargetApparentVelocity = new Vector( target.velocityX - source.velocityX ,
                                            target.velocityY - source.velocityY );

Normally, a bullet's velocity would be much higher than the shooter's velocity so it is usually assumed that the bullet is independent but there are occasions where this is not true, such as firing out of a helicopter or fighter jet.

Then we need to work out the bullet velocity:

// Your directional vector MUST be normalized...
Vector BulletVelocity = new Vector( source.directionX * Bullet::StaticSpeed + source.velocityX ,
                                     source.directionY * Bullet::StaticSpeed + source.velocityY );

The problem you're having is that the target has moved by the time the bullet reaches them.

TargetPosition = TargetInitialPosition + TargetApparentVelocity * t
BulletPosition = BulletInitialPosition + BulletVelocity * t
               = BulletVelocity * t

and solve for TargetPosition == BulletPosition because then the bullet would have hit the target. Now you have three unknowns and only two equations. We can remove 't' by taking the first order derivative:

TargetInitialPosition + ( TargetApparentVelocity - BulletVelocity ) * t == 0
dV / dt = TargetApparentVelocity - BulletVelocity

Now to hit the target, you'd want dV/dt == -TargetInitialPosition * k. The constant has to be the same in the X and Y coordinates and is the number of seconds the bullet will take to hit the target.

TargetApparentVelocity.X - BulletVelocity.X == k * -TargetInitialPosition.X
k = ( BulletVelocity.X - TargetApparentVelocity.X ) / TargetInitialPosition.X
----------------------
TargetApparentVelocity.Y - BulletVelocity.Y == k * -TargetInitialPosition.Y
k = ( BulletVelocity.Y - TargetApparentVelocity.Y ) / TargetInitialPosition.Y

make them equal:

( BulletVelocity.X - TargetApparentVelocity.X ) / TargetInitialPosition.X
= ( BulletVelocity.Y - TargetApparentVelocity.Y ) / TargetInitialPosition.Y

or to expand the variables:

( source.directionX * Bullet::StaticSpeed + source.velocityX - target.velocityX + source.velocityX ) / ( target.X - source.X )
 == ( source.directionY * Bullet::StaticSpeed + source.velocityY - target.velocityY + source.velocityY ) / ( target.Y - source.Y )

Then algebra gives you your final equation:

source.directionY = ( target.velocityY * ( source.X - target.X ) - 2 * source.velocityY * ( source.X - target.X ) + ( Bullet::Speed * source.directionX + 2 * source.velocityX - target.velocityX ) * ( source.Y - target.Y ) ) / ( Bullet::Speed * ( source.X - target.X ) )

The next part is messy and it's up to you how you want to implement it in your code, but we just substitute this in and normalize the vector.

sqrt( source.directionX ^ 2 + source.directionY ^ 2 ) == 1

You end up with an equation with just one unknown (source.directionX), and you can solve it for directionX then substitute back in to get directionY.

I haven't tested any of this code and feel free to point out any methematical misstakes I've made, but the theory should be sound :).

Good luck.

share|improve this answer
    
Yes it is only 2D. Reading now. –  Azaral May 3 '12 at 22:59
    
Why are you adding the source velocity to the bullet's velocity? –  Sam Hocevar May 3 '12 at 23:23
    
@SamHocevar That's how physics works. A bullet fired from a gun starts out with a velocity equal to the gun that fired it. It then adds the vector generated by the firing action to this vector. The action is taking place in space so there is no air to change the bullet's velocity. If you fire a gun in space while moving to your right, it will always be in front of you until you change your velocity. –  Azaral May 3 '12 at 23:31
1  
Sorry, it works with examples, it's just hard to abstract it to the general case. Everything down to the (dV / dt = TargetApparentVelocity - BulletVelocity) is theory and the only code you'll need is this final few boxes. The algebra I came up with is way to complicated, but Mathematica was able to solve it. The reason we take the first order derivative is because you don't care how long it takes for the bullet to hit, you just want it to hit. –  tyler.daniels May 4 '12 at 2:22
1  
@Azaral that is not how physics work. In a uniformly moving reference frame you need to subtract the source velocity from all velocities, including the bullet's. If you use the apparent velocity for the target, you need to use the apparent velocity for the bullet, too. –  Sam Hocevar May 4 '12 at 7:18
show 2 more comments

Having a moving shooter is identical to having a stationary shooter. Simply subtract the shooters movement vector from the targets movement vector.

Target [-5,0]
Shooter [4,1]
Target - Shooter = [-5,0] - [4,1] = [-9,-1]

Calculate the firing vector/initial angle, then add the targets movement vector to the bullet like normal.

share|improve this answer
    
If you read my question and looked at the code, you would see I'm already doing this. –  Azaral May 3 '12 at 16:18
    
@azaral yes, and no. you are doing this to get one of your values, and then doing stuff with velocity –  gardian06 May 3 '12 at 16:49
    
@gardian06 can you be more specific? –  Azaral May 3 '12 at 16:59
    
@Azaral I was under the impression that you had a working algorithm for when the shooter was stationary, as was described in the link you provided. If its not working in that case there is a bug in that algorithm that needs sorting before you need to worry about a moving shooter (not that the difference is big, but simpler is easier to debug) –  Daniel Carlsson May 3 '12 at 21:59
    
@DanielCarlsson you know that's a good point I never thought of. I just assumed the algorithm worked. –  Azaral May 3 '12 at 22:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.