targeting moving objects

This topic is 4203 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

Share on other sites
Quote:
Original post by synth_cat
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.)

Uh...
Try this on for size:

You have the target init position and target velocity. Using this you can get target position as a function of time. (vector function)

Given target position(time) you can get distance from target to shooter per as function of time - targetdist(time) (no sin/cos just dist forumla)

You already know the speed of bullet, but not it's direction, thus you can create a sphere centered on shooter, which represents All possible locations of the bullet per time. - bulletsphere(time) (dist formula again, no sin/cos)

Given targetdist(time) and bulletsphere(time) you can solve for the time of first possible impact (simple system of equations, probly quadratic)

plug that impacttime back into position(time) to get the location of impact
Shooter should aim at that location
negative values for impacttime mean there is no possible way to hit it

Vectors For the Win!

Share on other sites
As an aside, implementing both is a good idea(tm) -- at the least, you can check one against the other. :)

Implementing AP's analytical vector post:

D = initial delta to target
V = target velocity
B = weapon velocity

The position of the target at time t:
P(t) = D + tV

To find out what time the weapon hits, solve:
|P(t)| = t*B (formula 1)
which gives "Time On Target". Once you have "Time On Target", you can find out where to aim, and shoot at it (take the relative position vector, normalize. That is your aiming vector.)

Note:
|P(t)| = sqrt( sum(i from x to z)(Di+tVi)^2 )
Sqrts are evil. Let's get rid of them!

So, square formula 1:
(Dx+tVx)^2 + (Dy+tVy)^2 + (Dz+tVz)^2 = t^2B^2
expand and group:
Dx^2 + Dy^2 + Dz^2 + 2t(DxVx + DyVy + DzVz) + t^2(Vx^2+Vy^2+Vz^2) = t^2B^2

simplify with dot (aka, inner) product:
D.D + 2t D.V + t^2 V.V = t^2 B.B

Shuffle around into a standard form:
D.D + 2t D.V + t^2 (V.V-B.B) = 0

t = {
-D.V +/- sqrt( (D.V)^2 - D.D(V.V-B.B) )
------------------------------------------
D.D
}

which is a family of two solutions. Often (not always) one will be negative. You want to use the smallest postive time from the above pair of solutions.

(Appendix: The inner, or dot, product of two vectors A = (Ax,Ay,Az) and B = (Bx,By,Bz) is denoted A.B, and A.B := Ax*Bx + Ay*By + Az*Bz).

Share on other sites
If you haven't found a satisfactory answer yet, allow me to outline the problem qualitatively and quantatively without using any code (because everybody likes to implement the solution their own way).

Cell1 is trying to extrapolate the motion of Cell2 according to its observed position. Let's suppose that the extrapolation curve S(t) has been determined (I'll get to that later). Here, S is a vector function of time, t. Then the new problem is simple. Cell1 now needs to determine which direction to fire in order for his projectile to intersect the curve, spatially and temporally.
If these cells are moving very quickly compared to the projectile's velocity, the cell will need to solve a set of simultaneous equations to know how far along the curve to aim. However, in real-life situations, it is usually fair to assume that the target will be approximately the same distance away at the moment of impact as it is at the moment of firing.

If this is not the case, you will need to solve (or approximate) the following equation, which, combined, will have the complexity no more than the square of your extrapolation method;

S(t) = X [plus] vtu

t = Time (independent variable)
S = S(t) = Vector position of Cell2 at time t
X = Position of Cell1
v = Speed of projectile (assumed constant, but could be a given function of t)
u = Normalised vector in which Cell1 should fire

If you're working in three dimensions, this gives four scalar equations in four variables (the missing equation is |u| = 1) that can be solved to give you all the needed data.

However, this is a bit of a fuss to solve, so assuming you're happy with the earlier assumption (the cells move slowly compared to the projectile), the equation simplifies and solves so that Cell1 should simply aim at S(d/v), where d is the distance between the two cells and v is the speed of the projectile.

Now all that's left is to determine the extrapolated curve of motion, S(t). This can be as simple or as complicated as you make it. Currently, you are taking S to be constant (and equal to the position of Cell2 at the moment of firing). Clearly, this isn't adequate. Most games these days use the next simplest method: linear extrapolation. Just as the previous posters have shown, all that needs to be measured is the instantaneous velocity of Cell2 at the moment of firing. From here S is defined as

S(t) = S(0) [plus] tw.

where S(0) is the position of Cell2 at the moment of firing, and w is its velocity vector at that time.
This method should do the trick, unless the Cells are able to accelerate very quickly.

If you need more accuracy, you can simply expand on this linear extrapolation by determining further instantaneous derivatives of position and forming a polynomial of the required degree. Alternatives would be exponential or logarithmic extrapolation, but I doubt the problem would require that. After all, the best extrapolation function to use is the one that matches the motion of the cells. If the cells only have the ability to apply constant accelerations in any direction (which is a very common movement method in games) then you should want to go no further than quadratic complexity.

I hope this helps

Share on other sites
Well, thanks a lot for all the replies!

I like the idea of solving a system of two equations where one returns distance from target to player as a function of time and the other returns distance from bullet to player as a function of time.

I haven't worked out the details yet, but I'll post again if I am able to come up with anything.

Thanks again!
-synth_cat

Share on other sites
Well, I've got this new method implemented, but it has a problem: you have to set the value of "v" (which is meant to represent the velocity of my projectile) to a very small number for it to work. Otherwise the targeting "lags", not shooting far enough ahead that the bullet makes contact.

I'll briefly explain my method and then post the code (because the error may lie in either one.)

First off, we need to solve two equations (finding the point where distances are the same)

given:

float px,py (player position)
float tx,ty (target position)
float v (velocity of shot (units/second) )
float tmovx, tmovy (the movement of the target)
float dx=tx-px (make things easier to write)
float dy=ty-py

trying to find:

float t (time)

Equation 1 (distance from target to player as a function of time):

d = sqrt( (dx+t*tmovx)^2 + (dy+t*tmovy)^2 )

Equation 2 (distance from bullet to player as a function of time):

d=v*t

Putting these two together, you get

sqrt( (dx+t*tmovx)^2 + (dy+t*tmovy)^2 ) = v*t

(dx+t*tmovx)^2 + (dy+t*tmovy)^2 = v^2*t^2

dx^2+2*dx*t*tmovx+(t*tmovx)^2+dy^2+2*dy*t*tmovy+(t*tmovy)^2 = v^2*t^2

t^2*(tmovx^2+tmovy^2)+t*(2*dx*tmovx+2*dy+tmovy)+dx^2+dy^2 = v^2*t^2

t^2*(tmovx^2+tmovy^2-v^2) + t*(2*dx*tmovx+2*dy+tmovy)+dx^2+dy^2 = 0

As you can see, we now have a quadratic equation we can solve for t.

Here is the code:
//this will be the direction you shoot inD3DXVECTOR2 vec_to_tgt;bool no_solution=false;float x1=player_position.x;float y1=player_position.y;float x2=target.pos.x;float y2=target.pos.y;float t1=0; //possible time valuefloat t2=0; //possible time valuebool use_t1=false; //decide which time value to usefloat v=shot_speed;float tmovx=target_mov.x;float tmovy=target_mov.y;float delta_x=x2-x1;float delta_y=y2-y1;float a=tmovx*tmovx+tmovy*tmovy-v*v;float b=2*delta_x*tmovx+2*delta_y*tmovy;float c=delta_x*delta_x+delta_y*delta_y;if(a && (b*b-4*a*c)>=0){	t1=(-1*b+sqrtf(b*b-4*a*c))/(2*a);	t2=(-1*b-sqrtf(b*b-4*a*c))/(2*a);		//pick which time value to use	if(t1<0 && t2<0)	{  no_solution=true;}	else	{		if(t1<0 || t2<0)		{			if(t1<0)			{ use_t1=false;}			else			{ use_t1=true;}		}		else		{			if(t1<t2)			{ use_t1=false;}			else			{ use_t1=true;}		}	}}else {no_solution=true;}if(no_solution){        //will indicate an error (this never happens)	vec_to_tgt.x=0;	vec_to_tgt.y=1;}else{	if(use_t1)	{		vec_to_tgt=cells[maincell.locked_target].pos+			t1*cells[maincell.locked_target].mov-turret_position;		D3DXVec2Normalize(&vec_to_tgt,&vec_to_tgt);	}	else	{		vec_to_tgt=cells[maincell.locked_target].pos+			t2*cells[maincell.locked_target].mov-turret_position;		D3DXVec2Normalize(&vec_to_tgt,&vec_to_tgt);	}}

I really don't get what the problem is here, but I know for a fact that my shot is moving 1200 units per second, yet the above code only works accurately if I set "v" to something like 10.

Can anyone help me out?

Thanks!
-synth_cat

Share on other sites
Quote:
 float px,py (player position)float tx,ty (target position)float v (velocity of shot (units/second) )float tmovx, tmovy (the movement of the target)

What are the units of tmovx and tmovy?

...

Why did you do everything in one function? Break things down into small logical chunks -- you can test them. Write the "time on target" function that solves for "what are the two times that the bullet can hit the target".

Write a wrapper that returns a success/failure boolean, and gives the lowest positive possible time on target.

Once you have done this, your code gets simpler, the scope of your variables is smaller, and bugs are easier to find.

...

Take a problem with a known solution (like, target stationary 10 units away). Find "time on target". Is the result accurate? Try for a slightly more complex problem -- bullet moving at 1 unit/second, target starts at distance 10, moving towards shooter at 1 unit/second. Result accurate? Try distance 10, moving 1 units/second away, bullet moving at 2 units/second.

Try it with the target moving perpendicular.

Does your "time on target" code pass all of those tests? Some of those tests?

Share on other sites
Quote:
 What are the units of tmovx and tmovy?

They are the basic drawing units of Direct3d. However, the point is that they are the same units that all the other values are in.

I know for sure that this targeting system works fine when targets are stationary; it's just that the bullets aren't shot far enough ahead of the target when the target is moving.

Share on other sites
Quote:
Original post by synth_cat
Quote:
 What are the units of tmovx and tmovy?

They are the basic drawing units of Direct3d. However, the point is that they are the same units that all the other values are in.

I know for sure that this targeting system works fine when targets are stationary; it's just that the bullets aren't shot far enough ahead of the target when the target is moving.

Are they in distance/frame? distance/second? distance/hour?

...

I told you how to debug your problem. Break the "time on target" code away from the rest of the code. Test it in situations where you know the answer, and test it with increasing complexity of problems.

If it fails the tests, you know the problem is with the "time on target" code.

If it passes the tests, you know the problem is probably elsewhere (or your tests aren't good enough! heh).

This is known as "unit testing" -- you break a large chunk of code down into smaller units, and you test each unit, and see if that unit works.

If you want to find your bug, I can tell you how to find it. If you don't do what I ask, what I tell you won't help you.

Good day.