Jump to content
  • Advertisement
Sign in to follow this  
synth_cat

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 get
D3DXVECTOR2 fire_direction;

bool no_solution=false;

//used to solve the equation
float 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 theta
float a=v*delta_y;
float b=v*delta_x;
float c=((dx2-v)*delta_y-dy2*delta_x);
float sin=0; //sin of theta
float cos=0; //cos of theta

if(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 theta
a=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 this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by synth_cat
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


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 this post


Link to post
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 this post


Link to post
Share on other sites
Want a zero-trig solution?

Given:
D3DXVECTOR2 position_of_shooter
D3DXVECTOR2 position_of_target
D3DXVECTOR2 motion_of_target_per_sec
float 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 this post


Link to post
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!