2D game algorithm to calculate a bullet's needed speed to hit target?

Question

I have a rather simple bird's-view 2D game where tower sprites defend against incoming moving sprites by shooting a bullet at them. My question: How do I calculate the needed bullet speed for the bullet to reach its moving target, provided that the bullet will always have the same defined speed?

I'm using JavaScript and have these sprite variables (among others): sprite.x, sprite.y, sprite.width, sprite.height, sprite.speedX (i.e. velocity), sprite.speedY... so I have the objects originSprite, targetSprite and bulletSprite, all with these type of values, and I need to set the right bulletSprite speed values.

Probably for it to look good, the bullet would start at the outside of the originSprite (or some defined radius, though I guess starting from the originSprite center would also work), but its bullet center would try hit into the center of the targetSprite or so. Note there's no gravity or anything in this world. (Perhaps I should have my sprites variables using angle and velocity but right now I'm using speedX and speedY...)

Thanks so much!

Answer 1

Treat the targets sprite as a straight line in a 2 dimensional room where:

A(time) = (sprite.positionX + sprite.speedX * time, sprite.positionX + sprite.speedX * time)

As your bullet have constant speed you also know:

bullet.speedX^2 + bullet.speedY^2 = bullet.definedSpeed^2

Then you can also calculate a straight line for the bullet:

B(time) = (bullet.positionX + bullet.speedX * time, bullet.positionX + bullet.speedX * time)

And you know that both lines interset somewhere:

A(time) = B(time)

Then it's up to you to solve those equations with your given values and seek a minimum for time.

Answer 2

Some physical insight

1 ) For the target being a "Point Object"

So you have to solve the VECTOR equation

Position_bullet [ time=t₁ > t₀ ] == Position_target [ time=t₁ > t₀ ] -- (Eq 1)

Where the positions are given by the motion (also VECTOR) equations

Position_object [ t ] = Position_object [ t₀ ] + Speed_object * ( t - t₀ )

Now, the condition for the bullet to be able to reach the target is that the Eq 1 has solutions for x and y. Let's write down the equation for x:

X_bullet [ t₀ ] + SpeedX_bullet * ( t - t₀ ) = X_target [ t₀ ] + SpeedX_target * ( t - t₀ )

So for the collision time we have

( t_Collision - t₀ ) = (x_target [ t ₀ ] - x_bullet [ t₀ ] ) / (SpeedX_bullet - SpeedX_target) -- (Eq 2)

As we need solutions with t > t₀, that means that for having an intercept is enough that>

Sign ( x_target[ t₀ ] - x_bullet[ t₀ ] ) = Sign ( SpeedX_bullet - SpeedX_target ) -- (Eq 3)

Which tells us the evident fact that if an object is moving faster than the other, and in the same direction, they will eventually collide.

From Eq 2, you can see that for a given SpeedX_targetthere exist infinite solutions (as already pointed out in other answers) for t and SpeedX_bullet, so I think your specifications are not complete.

I guess (as stated in a commentary I made in another answer) thinking in a "tower defense" kind of game, that your bullets have a limited range.
So you need also another constraint:

Distance [ Position_target [ t_Collision - t₀ ] - Position_bullet [ t₀ ] ] < BulletRange -- (Eq 4)

Which still permits infinite solutions, but bounded by an upper value for the Collision time, given by the fact that the target may abandon the range.
Further, the distance is given by

Distance[v,u]= +Sqrt[ (Vx-Ux)^2 + (Vx-Vy)^2 ]

So, Eq 4 becomes,

(X_target[t_Collision - t₀] - X_bullet[t₀])² + (Y_target[t_Collision - t₀] - Y_bullet[t₀])² < BulletRange² -- (Eq 5)

Note that { X_bullet[t₀] , Y_bullet[t₀} is the tower position.

Now, replacing in Eq 5 the values for the target position:

(X_target[t₀] + SpeedX_target * (t-t₀) - X_bullet[t₀])² + (Y_target[t₀] + SpeedY_target * (t-t₀) - Y_bullet[t₀])² < BulletRange² -- (Eq 6)

Calling the initial distances:

Dxt0 = X_target[t₀] - X_bullet[t₀]

and

Dyt0 = Y_target[t₀] - Y_bullet[t₀]

Equation 6 becomes

(Dtx0 + SpeedX_target * (t-t₀) )² + (Dty0 + SpeedY_target * (t-t₀))² < BulletRange² -- (Eq 7)

Which is a quadratic equation to be solved in t-t0. The positive solution will give us the largest time allowed for the collision. Afterwards the target will be out of range.

Now calling

Speed_target² = SpeedX_target² + SpeedY_target²

and

H = Dtx0 * SpeedX_target + Dty0 * SpeedY_target

T_{Collision Max} = t₀ - ( H +/- Sqrt ( BulletRange² * Speed_target² - H² ) ) / Speed_target²

So you need to produce the collision BEFORE this time. The sign of the square root should be taken such as the time is greater than t0

After you select an appropriate flying time for your bullet from the visual 
effects point of view, you can calculate the SpeedX and SpeedY for the bullet 
from  

SpeedX_bullet = ( X_target [ t₀ ] - X_bullet [ t₀ ] ) / ( t_Collision - t₀ ) + SpeedX_target

and

SpeedY_bullet = ( Y_target [ t₀ ] - Y_bullet [ t₀ ] ) / ( t_Collision - t₀ ) + SpeedY_target

2 ) For the target and tower being "Extensive Objects"

Now, it is trivial to generalize for the case of the target being a circle of radius R. What you get, is the equivalent of an "extended range" for the bullets. That extension is just R.

So, replacing BulletRange by (BulletRange + R) you get the new equations for the maximum allowed collision time.

If you also want to consider a radius for the cannons, the same considerations apply, giving a "double extended range

NewBulletRange = BulletRange + R_Target + R_Tower

Unlimited Range Bullets

In the case that you decide that some special bullets should not have range (and detection) limitations, there is still the screen border constraint. But it is a little more difficult to tackle. Should you need this kind of projectile, leave a comment and I'll try to do some math.

Answer 3

Using vectors can make the math around this seem a little simpler. Sylvester seems to be a promising implementation of vectors in JavaScript, but for the purpose of my example, I'll write my own vector functions. I'm also going to assume .x / .y are measured top/left corner.

// this is a "constant"  - representing 10px motion per "time unit"
var bulletSpeed = 10; 
// calculate the vector from our center to their center
var enemyVec = vec_sub(targetSprite.getCenter(), originSprite.getCenter());
// measure the "distance" the bullet will travel
var dist = vec_mag(enemyVec);
// adjust for target position based on the amount of "time units" to travel "dist"
// and the targets speed vector
enemyVec = vec_add(enemyVec, vec_mul(targetSprite.getSpeed(), dist/bulletSpeed));
// calculate trajectory of bullet
var bulletTrajectory = vec_mul(vec_normal(enemyVec), bulletSpeed);
// assign values
bulletSprite.speedX = bulletTrajectory.x;  
bulletSprite.speedY = bulletTrajectory.y;  

// functions used in the above example:

// getCenter and getSpeed return "vectors"
sprite.prototype.getCenter = function() { 
  return {
    x: this.x+(this.width/2), 
    y: this.y+(this.height/2) 
  }; 
};

sprite.prototype.getSpeed = function() { 
  return {
    x: this.speedX, 
    y: this.speedY 
  }; 
};

function vec_mag(vec) { // get the magnitude of the vector
  return Math.sqrt( vec.x * vec.x + vec.y * vec.y); 
 }
function vec_sub(a,b) { // subtract two vectors
  return { x: a.x-b.x, y: a.y-b.y };
}
function vec_add(a,b) { // add two vectors
  return { x: a.x + b.x, y: a.y + b.y };
}
function vec_mul(a,c) { // multiply a vector by a scalar
  return { x: a.x * c, y: a.y * c };
}
function vec_div(a,c) { // divide == multiply by 1/c
  return vec_mul(a, 1.0/c);
}
function vec_normal(a) { // normalize vector
  return vec_div(a, vec_mag(a)); 
}

Answer 4

Compute the distance between shooter and target: dist = sqrt((xt - xs)^2 + (yt - ys)^2)
Divide the x and y distances by the above one: nx = (xt - xs)/dist; ny = (yt - ys)/dist; (normalization of the vector)
Multiply the results by a factor to get n pixels per time unit, ie. a speed in each direction. It should give a constant speed in the wanted direction.