# targeting moving objects

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

## Recommended Posts

In my game I have begun work on behavior for my "cells" (things that move around and shoot at eachother.) Their shooting behavior is fairly simple; they more or less just shoot straight at their targets. However, this doesn't always work well because sometimes there is little difference between the speed of a target and the speed of a shot. So I decided to go ahead and write code that a cell could use to determine where it should shoot ahead of its target so that it will make a hit. Given: D3DXVECTOR2 position_of_shooter D3DXVECTOR2 position_of_target D3DXVECTOR2 motion_of_target_per_sec float speed_of_shot Trying to find: D3DXVECTOR2 target (where normalized(target-position_of_shooter) is the direction you need to shoot in.) Of course, you could just solve for the shot direction vector, I suppose. I can't get my head around this problem - does anyone know how to do it? I'm guessing that this must be some sort of quadratic equation - at any rate, there has to be some way that this problem can return no solution (especially if the shoot is slower than the target.) Thanks! synth_cat

##### Share on other sites
I suppose just speeding up your projectile isn't a good solution for you, right? :) If your motion is simple enough, you can just use trig equations to approximate how to lead a target. Can you explain your motion in more detail?

##### Share on other sites
Unfortunately, speeding up the projectile doesn't really work. Of course, if it were fast enough, looking ahead would be completely unnecessary because the target_position you would solve for would be very close to the target's starting position. However, I need slow shots because this game is based on close combat and agility, and shots absolutely must be dodge-able.

There really aren't any more details than what I gave in my last post - this motion is very simple. A cell just creates a shot and gives it a normal telling which direction it should go at its own speed. I should mention that the shot's velocity is completely unaffected by the velocity of the entity that shoots it (keeping this simple.)

##### Share on other sites
Projectile starts at x1, y1, with velocity dx1, dy1. Target starts at x2, y2, with velocity dx2, dy2. We want to find the time t when collision occurs.

Thus, x1 + t*dx1 = x2 + t*dx2; y1 + t*dy1 = y2 + t*dy2.

This is two equations in one unknown; an over-constrained system. As we should expect, because the projectile won't necessarily hit the target - it has to be going in the correct direction (and even then, might not).

We have an unknown angle theta for the projectile, and a known velocity v. dx1 = v * cos(theta); dy1 = v * sin(theta). We are solving for t and theta.

x1 + v * t * cos(theta) = x2 + t * dx2; rearrange to get

t = (x2 - x1) / (v * cos(theta) - dx2) (notice, when the denominator is 0, it's because the particles have the same x velocity component and will never collide, so that makes physical sense)

Similarly,

t = (y2 - y1) / (v * sin(theta) - dy2)

Assuming there is a solution, we can equate the two expressions for t, and rearrange:

(v * sin(theta) - dy2)(delta_x) = (v * cos(theta) - dx2)(delta_y)

where delta_x = x2 - x1, delta_y = y2 - y1.

Substitution based on (sin^2(z) + cos^2(z) = 1) lets us get a quadratic expression for cos(theta) (or sin(theta)), and then we can take acos (or asin) to get the angle.

(v * s - dy2)(delta_x) = (v * (1 - s^2) - dx2)(delta_y), where s = sin(theta)

(v * delta_y)s^2 + (v * delta_x)s + ((dx2 - v) * delta_y - dy2 * delta_x) = 0.

Bust out the quadratic equation and you're good to go. From sin(theta), you can calculate dx1 and dx2, substitute back in, and find t. Discard negative, >1 (since you will pass the value to asin), or complex solutions; a lack of solutions means the projectile can't hit the target with its current speed. You may need to sanity-check which quadrant to fire in, since the sign of sin(theta) doesn't uniquely identify that. Alternatively, repeat the calculation for cos(theta), since the sign of *both* values taken together will uniquely identify the quadrant.

##### Share on other sites
And because every good solution deserves another:

Have the shooter aim at the target.

Now have the shooter do a "microsim" of the bullet and the target, advancing time until the bullet passes by the target (or the target outruns the bullet too much).

Ok, how much did I miss by? The target is 5 degrees left of where I shot.

Try again! Shoot 5 degrees left this time (random adjustment centered on the 5 degrees).

Run Microsim. Nope, still 1 degree off. Try again.

Run Microsim. A hit! Ok, that is where the guy should aim.

----

The complexity of the Microsim is up to you.

If there are random elements in your Microsim (say, cover, or the exact choice of angle), you might want to run the Microsim more than once on each pass.

Microsiming a number of random directions close to where you want to shoot can help deal with "I can't hit that target because of the thin wall that just happens to be in the way of his centre" & the like.

----

The advantage of a method like the one above is that you can easily add complexities to the game -- bullets that accellerate, decellerate, turn, start to factor in the accelleration/decelleration/turning of the target, non-uniform environmental effects that change weapon/character trajectories, or any other complex detail -- and the microsim code doesn't get that much harder to write.

Meanwhile, all such details make an analytic solution harder and harder to get right.

The disadvantage is, an analytic solution tends to take a rather small number of CPU cycles -- a simulation based search can take much longer.

##### Share on other sites
Thanks for all the help so far!

I've tried to implement your approach, Zahlman. However, it isn't working completely right for some reason. It only works when the target is in a certain quadrant relative to the position the shot is being fired from. I really don't see why it should do this - I run the whole quadratic equation for both the sine and cosine of theta.

Here's my code:

//this is what we're trying to getD3DXVECTOR2 fire_direction;bool no_solution=false;//used to solve the equationfloat x1=player_pos.x;float y1=player_pos.y;float x2=cells[target].pos.x;float y2=cells[target].pos.y;float v=shot_speed;float dx2=cells[target].mov.x;float dy2=cells[target].mov.y;float delta_x=x2-x1;float delta_y=y2-y1;//parameters for quadratic equation to get sine of thetafloat a=v*delta_y;float b=v*delta_x;float c=((dx2-v)*delta_y-dy2*delta_x);float sin=0; //sin of thetafloat cos=0; //cos of thetaif(a && (b*b-4*a*c)>=0){	sin=(-1*b+sqrtf(b*b-4*a*c))/(2*a);	vec_to_tgt.y=sin;}else {no_solution=true;}//reset parameters and solve for cosine of thetaa=delta_x*v;b=delta_y*v;c=( -1*delta_x*(v-dy2)-delta_y*dx2);if(a && (b*b-4*a*c)>=0){	cos=(-1*b+sqrtf(b*b-4*a*c))/(2*a);	vec_to_tgt.x=cos;}else {no_solution=true;}if(no_solution){   //didn't work - have to use something else...}

I have no idea what the problem is here.

As you see, I only use -b+sqrt(b^2-4ac) - I don't look at -b-sqrt(b^2-4ac). Is it necessary for me to look at both? If so, I have no idea how I could tell which solutions were the right ones.

Does anyone know why this isn't working?

Thanks!
-synth_cat

##### Share on other sites
Quote:
 Original post by synth_catIt only works when the target is in a certain quadrant relative to the position the shot is being fired from. I really don't see why it should do this

And that is why Trig functions should be avoided at all costs in favor of a purely vector based approach...

too many special cases when you change quadrants and something changes sign...
I'm going to bet that at some point you are using tan arctan or your sin and cos are producing a relationship identical to tan arctan

##### Share on other sites
Quote:
 And that is why Trig functions should be avoided at all costs in favor of a purely vector based approach...too many special cases when you change quadrants and something changes sign...I'm going to bet that at some point you are using tan arctan or your sin and cos are producing a relationship identical to tan arctan

Unfortunately, a vector-based approach is quite impossible here (Zahlman's solution appears to be the only viable way to do this, and I've already received the same answer from an engineer friend.)

I understand why using sin() and cos() causes quadrant problems (believe, me, it's happened to me many times.) However, there is no reason why this problem should occur when have solved for both sine and cosine separately. The quadrant problem should only ever occur when you solve for either sine or cosine and then use that answer to solve for the other.

The problem has to be in my code - does anyone see it? I suspect the problem may lie in the cosine-finding section, but I can't put a finger on it.

Thanks for any help!
-synth_cat

##### Share on other sites
Want a zero-trig solution?

Given:
D3DXVECTOR2 position_of_shooterD3DXVECTOR2 position_of_targetD3DXVECTOR2 motion_of_target_per_secfloat speed_of_shot

Simply do a loop around "estimated time to hit" until it converges:

float get_time_on_target(  D3DXVECTOR2 target_relative_location,  D3DXVECTOR2 target_movement,  float speed_of_shot,  int max_iterations,  float required_accuracy){  float estimated_hit_time = 0;  bool done = false;  while(max_iterations-- && !done) {    // assuming our time on target guess is accurate, where will the target be?    D3DXVECTOR estimated_location = target_relative_location+ target_movement*estimated_hit_time;    // how far away will the target be?    float extimated_distance = |estimated_location|;    // ok, assuming that distance, how long will the bullet take?    float new_estimated_hit_time = extimated_distance/speed_of_shot;    // are we close enough?    float off_by = new_estimated_hit_time - estimated_hit_time;    if (|off_by| < required_accuracy) {      done = true;    }    // repeat until we get close enough, or we run out of aiming time:    estimated_hit_time = new_estimated_hit_time;  }  return estimated_hit_time;}

Given the time_on_target, you can quite easily aim your weapon:

D3DXVECTOR2 weapon_aim_from_time(  D3DXVECTOR2 target_relative_location,  D3DXVECTOR2 target_movement,  float time_on_target){  D3DXVECTOR2 = target_relative_location + target_movement*time_on_target;  return target_relative_location/|target_relative_location|;}

Stitched together:
D3DXVECTOR2 firing_solution(  D3DXVECTOR2 target_relative_location,  D3DXVECTOR2 target_movement,  float speed_of_shot,  int cycle_limit = 100,  float time_accuracy = 0.0001){  float time_on_target =    get_time_on_target(      target_relative_location,      target_movement,      speed_of_shot,      cycle_limit,      time_accuracy    );    return weapon_aim_from_time(    target_relative_location,    target_movement,    time_on_target  );}

Improvements:
You can change the "required_accuracy" parameter in time_on_target to be in units of distance rather than time.

You can change the "time on target" code to use more than just velocity -- accelleration and jerk (2nd and 3rd derivatives) are easy to add (unlike the trig solutions)

Time on target can take into account terrain that modifies bullet and target velocity.

...

Analytical answers can be much more accurate and take less CPU, but they are a pain to write and get accurate, and their complexity balloons as you add more parameters to the problem you are trying to solve.

And how often, honestly, are your actors going to aim their guns at each other?

The solution above is in the same family as "newton's method" for finding the roots of an equation. You could speed up convergence, probably, by using newton's method.

##### Share on other sites
Thanks, NotAYakk!

However, I really want the analytical solutionto work for this problem - I guess it's as much a matter of personal taste as anything. I know that it has to be possible...

Thanks,
synth_cat

1. 1
Rutin
42
2. 2
3. 3
4. 4
5. 5

• 9
• 27
• 20
• 9
• 20
• ### Forum Statistics

• Total Topics
633395
• Total Posts
3011653
• ### Who's Online (See full list)

There are no registered users currently online

×