🔒 Locked

Target leading in 2D

Started by Mybowlcut Sep 21, 2010 at 3:57 AM 32 replies 10.5k views

Original Post

Sep 21, 2010 at 3:57 AM

I'm trying to make a stationary structure fire a bullet that intercepts a moving target.

At one point I had this code:

PointF Movement::intercept(const PointF& shooter, float bullet_speed,const PointF& target, const PointF& target_velocity){    float a = bullet_speed * bullet_speed - target_velocity.Get_Dot_Product(target_velocity);    float b = -2 * target_velocity.Get_Dot_Product(target - shooter);    float c = -(target - shooter).Get_Dot_Product(target - shooter);    return target + target_velocity * Maths::largest_root_of_quadratic_equation(a, b, c);}

It wasn't accurate enough, so I found this:

bool CalculateAimPoint(const Vector& xP0, const Vector& xV0, const Vector& xP1, float fInterceptSpeed, Vector& xAimPoint){	Vector dP = xP0 - xP1;	float a = xV0 * xV0 - (fInterceptSpeed * fInterceptSpeed);	float b = 2.0f * (dP) * xV0;	float c = dP * dP;	float d = b*b - 4 * a * c;	if (d < 0.0f)	{		return false;	}	d = (float) Maths::Sqrt(d);	float t0 = (-b - d) / (2.0f * a);	float t1 = (-b + d) / (2.0f * a);	float t;	if (t0 > t1)	{		float c = t0;		t0 = t1;		t1 = c;	}	if (t1 < 0.0f)	{		return false;	}	if (t0 >= 0.0f)	{		t = t0;	}	else	{		t = t1;	}	xAimPoint = xP0 + xV0 * t;	return true;}

I figured that xAimPoint would tell me where I'd need to shoot in order to hit the moving target. So I took xAimPoint and did this:

dir = Movement::get_dir_towards(src, xAimPoint);

PointF Movement::get_dir_towards(const PointF& source, const PointF& target){    const float cos_a = (target.y - source.y) / sqrt(pow(target.x - source.x, 2) + pow(target.y - source.y, 2));    const float sin_a = (target.x - source.x) / sqrt(pow(target.x - source.x, 2) + pow(target.y - source.y, 2));    return PointF(sin_a, cos_a);}

The bullet is still not accurate enough. I'm passing in these values to CalculateAimPoint:

PointF xP0 = target_pos;PointF xV0 = target.Get_Direction() * target_speed;PointF xP1 = source_pos;float fInterceptSpeed = projectile_speed + /* source speed would go here, but we're not moving */0;

I'm guessing it's got something to do with fInterceptSpeed? I know this is a really vague post, but that's because it's my last resort before I PAY someone to fix it for me. :)

Cheers.

speciesUnknown

Sep 21, 2010 at 4:07 AM

Are you trying to implement a perfect hit system, or are you doing this for an NPC ai system? if its the latter, then the process is quite simple; you can ignore some variables which we are unable to calculate without a lot of practice. Only use the distance from the shooter to the current position of the target, dont bother to perform instersections and the such. People don't triangulate the new distance in real time. Also, you could use a cone of fire; the moving target is hard to hit so people spray, plus, a cone of fire will also nullify most of the shortcomings of the simplified system.

so the calculation becomes very simple;

bullet_travel_time = length(target_pos - our_pos) / bullet_speed

position_to_aim_at = target_pos + ( normalise(target_direction) * bullet_travel_time )

Mathematical perfection is not only more complex, but unrealistic.

Mybowlcut

Sep 21, 2010 at 4:54 AM

Quote:
Original post by speciesUnknown
Are you trying to implement a perfect hit system, or are you doing this for an NPC ai system? if its the latter, then the process is quite simple; you can ignore some variables which we are unable to calculate without a lot of practice. Only use the distance from the shooter to the current position of the target, dont bother to perform instersections and the such. People don't triangulate the new distance in real time. Also, you could use a cone of fire; the moving target is hard to hit so people spray, plus, a cone of fire will also nullify most of the shortcomings of the simplified system.

so the calculation becomes very simple;

bullet_travel_time = length(target_pos - our_pos) / bullet_speed

position_to_aim_at = target_pos + ( normalise(target_direction) * bullet_travel_time )

Mathematical perfection is not only more complex, but unrealistic.

It's for a Tower Defense game, so I'd like pretty good accuracy.

I'll try this code out. Thanks. :)

Mybowlcut

Sep 21, 2010 at 5:03 AM

Ok it sorta works... here's my code after your advice:

float bullet_travel_time = (target_pos - turret_pos).Get_Length() / proj_speed;    PointF target_direction = Movement::get_dir_towards(turret_pos, target_pos);    PointF aim_point = target_pos + (target_direction.Normalise() * bullet_travel_time);    dir = Movement::get_dir_towards(turret_pos, aim_point);

But the bullets still lag behind the target too often. 50% of shots fired at a vehicle moving at a speed of 40 units hit, and 10% of shots fired at a vehicle moving at a speed of 100 units hit. The projectile speed is 200 units.

speciesUnknown

Sep 21, 2010 at 7:30 AM

Quote:
Original post by Mybowlcut
Ok it sorta works... here's my code after your advice:
*** Source Snippet Removed ***

But the bullets still lag behind the target too often. 50% of shots fired at a vehicle moving at a speed of 40 units hit, and 10% of shots fired at a vehicle moving at a speed of 100 units hit. The projectile speed is 200 units.

I see, so you are simulating a highly accurate computerised targeting system, rather than a human aiming a turret. My My algorithm is *designed* to have a flaw in it; the inability of a person to estimate the time the bullet takes to reach the characters ending point, due to our inability to do that calculation in a split second. What you need to do is factor in the error element which is caused by the inability to know how the creature's movement vector will change.

Dk: Distance known: This will let you calculate the travel time for a bullet if it was targeting a stationary target.

Da: Distance actual: This is the actual distance the bullet would have to go to hit the character. This is impossible to know 100% at the time the bullet is fired, since the character may not travel in a straight line.

Mo: Motion Observed; this is the motion of the target that an FPS player would observe, e.g. if he was looking down a scope. This is what human players do when they "lead a target" in a game where bullets have a travel time, such as in BF games. My algorithm is designed to simulate this effect and thus produce something looking more human.

Ma: motion actual, this is the actual movement the target made in the time it took for a bullet to travel along Dk. At the point of the bullet being fired, this is only an estimate based on the assumption that the target will not change course between the shot being fired and the round hitting its target.

The error factor in the travel_time calculation is length(Da - Dk). Faster bullets will nullify this effect, because the target is of a non infidecimal size. In order to compensate for the error, you need to perform this calculation once to get the above diagram; then, you need to compensate for length(Da - Dk). Don't forget, Ma is not set in stone, since in the time it takes the bullet to travel length(Dk) units along Da, the creature could change direction. This is why I mentioned the cone of fire principle.

Sadly, Im not good enough with math to give you the proper formula for this, but you may have already encountered it, so I hope the diagram helps.

Mybowlcut

Sep 21, 2010 at 7:53 AM

Quote:
Original post by speciesUnknown
Quote:
Original post by Mybowlcut
Ok it sorta works... here's my code after your advice:
*** Source Snippet Removed ***

But the bullets still lag behind the target too often. 50% of shots fired at a vehicle moving at a speed of 40 units hit, and 10% of shots fired at a vehicle moving at a speed of 100 units hit. The projectile speed is 200 units.

I see, so you are simulating a highly accurate computerised targeting system, rather than a human aiming a turret. My My algorithm is *designed* to have a flaw in it; the inability of a person to estimate the time the bullet takes to reach the characters ending point, due to our inability to do that calculation in a split second. What you need to do is factor in the error element which is caused by the inability to know how the creature's movement vector will change.

Dk: Distance known: This will let you calculate the travel time for a bullet if it was targeting a stationary target.

Da: Distance actual: This is the actual distance the bullet would have to go to hit the character. This is impossible to know 100% at the time the bullet is fired, since the character may not travel in a straight line.

Mo: Motion Observed; this is the motion of the target that an FPS player would observe, e.g. if he was looking down a scope. This is what human players do when they "lead a target" in a game where bullets have a travel time, such as in BF games. My algorithm is designed to simulate this effect and thus produce something looking more human.

Ma: motion actual, this is the actual movement the target made in the time it took for a bullet to travel along Dk. At the point of the bullet being fired, this is only an estimate based on the assumption that the target will not change course between the shot being fired and the round hitting its target.

The error factor in the travel_time calculation is length(Da - Dk). Faster bullets will nullify this effect, because the target is of a non infidecimal size. In order to compensate for the error, you need to perform this calculation once to get the above diagram; then, you need to compensate for length(Da - Dk). Don't forget, Ma is not set in stone, since in the time it takes the bullet to travel length(Dk) units along Da, the creature could change direction. This is why I mentioned the cone of fire principle.

Sadly, Im not good enough with math to give you the proper formula for this, but you may have already encountered it, so I hope the diagram helps.

Thanks for the awesome diagram and explanation. :) I am pretty crap at maths, hence I can't really do anything with what you've provided. However, the path of the vehicles through the level is calculated once at the start of the game. Using this path (with nodes), could I technically have 100% accuracy?

alvaro

Sep 21, 2010 at 8:11 AM

I have explained this several times in other threads, but here we go again. You want to find the time at which the bullet will hit the target. This time t is such that the distance between the shooter and the target at time t is the speed of the bullet times t.

The position of the target as a function of t is (target+t*target_velocity), so the equation to solve is

distance(target+t*target_velocity, shooter) = t*bullet_speed

Now let's operate on it:

distance(target+t*target_velocity, shooter)^2 = t^2*bullet_speed^2

dot_product(target+t*target_velocity-shooter,target+t*target_velocity-shooter) = t^2*bullet_speed^2

Let's define D := target-shooter

dot_product(D+t*target_velocity,D+t*target_velocity) = t^2*bullet_speed^2

dot_product(D,D)+2*dot_product(t*target_velocity,D)+dot_product(t*target_velocity,t*target_velocity) = t^2*bullet_speed^2

(dot_product(target_velocity,target_velocity)-bullet_speed^2)*t^2 + 2*dot_product(target_velocity,D)*t + dot_product(D,D) = 0

So I basically recovered your Movement::intercept code. Can you provide an example where that code returns a solution that is not accurate enough? Perhaps you are not using it right...

LorenzoGatti

Sep 22, 2010 at 3:14 AM

Maybe you are picking the wrong root of the quadratic equation when they are both positive? You are solving for interception time, so you want the smallest positive root, not the largest one.

Mybowlcut

Sep 22, 2010 at 4:48 AM

Quote:
Original post by alvaro
I have explained this several times in other threads, but here we go again. You want to find the time at which the bullet will hit the target. This time t is such that the distance between the shooter and the target at time t is the speed of the bullet times t.

The position of the target as a function of t is (target+t*target_velocity), so the equation to solve is

distance(target+t*target_velocity, shooter) = t*bullet_speed

Now let's operate on it:

distance(target+t*target_velocity, shooter)^2 = t^2*bullet_speed^2

dot_product(target+t*target_velocity-shooter,target+t*target_velocity-shooter) = t^2*bullet_speed^2

Let's define D := target-shooter

dot_product(D+t*target_velocity,D+t*target_velocity) = t^2*bullet_speed^2

dot_product(D,D)+2*dot_product(t*target_velocity,D)+dot_product(t*target_velocity,t*target_velocity) = t^2*bullet_speed^2

(dot_product(target_velocity,target_velocity)-bullet_speed^2)*t^2 + 2*dot_product(target_velocity,D)*t + dot_product(D,D) = 0

So I basically recovered your Movement::intercept code. Can you provide an example where that code returns a solution that is not accurate enough? Perhaps you are not using it right...

This is an example:

attack_pos = Movement::intercept(turret_pos, proj_speed, target_pos, target.Get_Direction() * target_speed);    turret.Set_Direction(Movement::get_dir_towards(turret_pos, attack_pos));

">Here's a video of the code in action. It is the debug executable, so it's a bit slow, but it shouldn't make a difference.

Edit: Just tested the release executable and it's the same.

[Edited by - Mybowlcut on September 22, 2010 5:48:12 AM]

alvaro

Sep 22, 2010 at 8:08 AM

Well, that's not what I meant by an example. Put a breakpoint in the function and see what parameters it's being called with for the first bullet. Then let's see what the three coefficients of the quadratic equation are, and what the resulting root is. If you are not sure if the numbers make sense, you can post them here and I'll help you.

Mybowlcut

Sep 23, 2010 at 3:25 AM

Quote:
Original post by alvaro
Well, that's not what I meant by an example. Put a breakpoint in the function and see what parameters it's being called with for the first bullet. Then let's see what the three coefficients of the quadratic equation are, and what the resulting root is. If you are not sure if the numbers make sense, you can post them here and I'll help you.

Sorry, was a bit rushed yesterday.

Quote:
parameters (in order) passed to intercept():

turret_pos = {x=140.00000 y=290.00000 }
proj_speed = 200.00000
target_pos = {x=62.500000 y=193.99261 }
target_direction = {x=0.00000000 y=1.0000000 }
target_speed = 40.000000

variables in intercept():

a = 38400.000
b = 7680.5908
c = -15223.668

inside largest_root_of_quadratic_equation():

(b + sqrt(b * b - 4 * a * c)) / (2 * a) = 0.73754294077555338

return value of intercept():

attack_pos = {x=62.500000 y=223.49432 }

I have no idea what those variables in intercept/largest_root_of_quadratic_equation mean (and considering my limited knowledge of maths, it's not important/practical for me to know), so if you could take a look and see why they are giving bad results, I'd be very appreciative. :D

Cheers.

alvaro

Sep 23, 2010 at 7:36 AM

Quote:
Original post by Mybowlcut
variables in intercept():

a = 38400.000
b = 7680.5908
c = -15223.668

inside largest_root_of_quadratic_equation():

(b + sqrt(b * b - 4 * a * c)) / (2 * a) = 0.73754294077555338

No: It is
(-b + sqrt(b * b - 4 * a * c)) / (2 * a) = .53752758[/quote]

You should really try to get yourself familiar enough with the Math to find this type of problem on your own. You could have verified yourself that 0.73754294077555338 is not even remotely a root of a^2*t^2 + b*t + c.

Mybowlcut

Sep 23, 2010 at 9:01 AM

Quote:
Original post by alvaro
Quote:
Original post by Mybowlcut
variables in intercept():

a = 38400.000
b = 7680.5908
c = -15223.668

inside largest_root_of_quadratic_equation():

(b + sqrt(b * b - 4 * a * c)) / (2 * a) = 0.73754294077555338

No: It is
(-b + sqrt(b * b - 4 * a * c)) / (2 * a) = .53752758

You should really try to get yourself familiar enough with the Math to find this type of problem on your own. You could have verified yourself that 0.73754294077555338 is not even remotely a root of a^2*t^2 + b*t + c.

Hm... pretty sure I copy-pasted it so I don't really know how I got that wrong, but I've corrected it. It doesn't seem to make a difference. Another example:

Quote:
attack_pos = {x=0.00000000 y=0.00000000 }
turret_pos = {x=140.00000 y=290.00000 }
proj_speed = 200.00000
target_pos = {x=62.500000 y=189.46248 }
target_direction = {x=0.00000000 y=1.0000000 }
target_speed = 40.000000

a = 38400.000
b = 8043.0020
c = -16114.043

(-b + sqrt(b * b - 4 * a * c)) / (2 * a) = 0.55147778828938798
attack_pos = {x=62.500000 y=211.52159 }

As for maths:

It's analogous to a plumber telling a mechanic he should learn how to repair drain pipes - the mechanic is a mechanic, he wants to fix vehicles. Game programming is a hobby for me. I left high school early to study graphic design which is what I thought I wanted to do, then realised that they taught game development courses at University. I am about to finish a double major (Games Programming/Software Engineering), but my scores for units with math involved are woeful.

I'm OK with this and accept that my time for learning advanced maths has passed; I've tried but I just have no interest at this age (21 :D).

tldr? I suck at "complex" maths and accept it; I have no interest in it and admittedly rely on others for help with the odd difficult subject (most of my games don't require a lot of math).

alvaro

Sep 23, 2010 at 10:12 AM

I believe your code is now working correctly. If you shoot towards (62.500000,211.52159) with a speed of 200, you'll hit your target.

Sorry, if you are not willing to put the effort to understand second-degree polynomial equations, I don't know why I should be willing to help you further.

Mybowlcut

Sep 23, 2010 at 5:20 PM

Quote:
Original post by alvaro
I believe your code is now working correctly. If you shoot towards (62.500000,211.52159) with a speed of 200, you'll hit your target.

Sorry, if you are not willing to put the effort to understand second-degree polynomial equations, I don't know why I should be willing to help you further.

Then please don't. If you feel everyone must understand every bit of maths they are using, then you've got a long way to go in your teaching. :)

For anyone else who is interested, the bullets still miss. I'm guessing alvaro's formula is correct and the problem is elsewhere? Could it be timing issues?

alvaro

Sep 23, 2010 at 7:27 PM

Quote:
Original post by Mybowlcut
Quote:
Original post by alvaro
Sorry, if you are not willing to put the effort to understand second-degree polynomial equations, I don't know why I should be willing to help you further.

Then please don't. If you feel everyone must understand every bit of maths they are using, then you've got a long way to go in your teaching. :)

So somehow you managed to convince yourself that I am the one with a problem here. Priceless.

speciesUnknown

Sep 23, 2010 at 7:55 PM

Looking at the video, it occurs to me that the turret appears to be shooting at the top left hand corner of each enemy.

Mybowlcut

Sep 24, 2010 at 2:52 AM

Quote:
Original post by alvaro
Quote:
Original post by Mybowlcut
Quote:
Original post by alvaro
Sorry, if you are not willing to put the effort to understand second-degree polynomial equations, I don't know why I should be willing to help you further.

Then please don't. If you feel everyone must understand every bit of maths they are using, then you've got a long way to go in your teaching. :)

So somehow you managed to convince yourself that I am the one with a problem here. Priceless.

I didn't say I don't have a problem. My problem is that I missed out on 2 years of high school maths. That's the problem I have. The problem that you have is that you apparently can't help someone out without spouting condescending nonsense about how they aren't making an effort. Please just stop posting if you're not going to help.

Quote:
Original post by speciesUnknown
Looking at the video, it occurs to me that the turret appears to be shooting at the top left hand corner of each enemy.

It's funny that you should mention this haha. That was the case until recently when I realised it looked a bit odd and changed it. This is what it looks like now:

Quote:
target.position = {x=50.000000 y=274.68997 }
target.size = {x=25.000000 y=25.000000 }

PointF target_pos(target.Get_Centre());

PointF Game_Entity::Get_Centre() const{    return Geometry::get_centre<float>(position, to_point_type<int, float>(size));}

template<typename T>    Point<T> get_centre(const Point<T>& position, const Point<T>& size)    {        return Point<T>(position.x + size.x / 2, position.y + size.y / 2);    }

The above results in the centre of the target being:

Quote:
target_pos = {x=62.500000 y=287.18997 }

That result looks correct to me, which leaves me confused as to why it's still missing.

Mybowlcut

Sep 24, 2010 at 3:40 AM

I debugged and had a closer look just to make sure the centres of the entities were being calculated properly after what you noted. The size of the turret (the part of the tower that rotates, not the tower itself) was not being read from the .xml file properly. I fixed this and the tower became slightly more accurate.

I had another look at my code and saw this:

PointF turret_pos(unit_centre + turret_centre);

Which is so wrong haha. I changed it to this:

PointF turret_pos(turret_owner.Get_Position() + turret_centre);

">And now it works perfectly! :D Well, technically I should try and figure out a way to determine if the vehicle is about to turn, because sometimes the bullets will miss in this scenario, but that's getting a bit pedantic.

Thanks for your help! If you didn't mention that top left corner thing, I'd still be trying to figure this out.

BlackShark33

Sep 24, 2010 at 6:38 AM

Very cool, im also working on a tower defense, im not as far along as you are, but im going to run into this issue eventually, would you mind posting the code with the fix?

Id greatly appreciate it!

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.