🔒 Locked

Projectile Leading Problem

Started by BlackDragon Nov 25, 2005 at 6:30 PM 14 replies 2.2k views

Original Post

Nov 25, 2005 at 6:30 PM

I am trying find a solution to the problem below. The problem is for a tech test in which we are allowed research the problem in order to find a solution. I am having some trouble trying to figure out what exactly the question is looking for. Given an initial shot position (Spos), a constant shot speed (Sspeed), an initial target position (Tpos), and a constant target velocity (speed + dir) (Tvel) derive the equation for calculating the shot direction (Sdir) such that at some time (t) the shot would hit the target. Be sure to derive an equation for t as well! Write a function to compute these values (Sdir and t). So far all I have come up with is: Tpos - Spos = Dif(the diffrence between the two points) if I normlize the diffrence will that give me the direction vector? And if so then All I would need to do is Dif / Sspeed = t? Thanks

JohnBolton

Nov 25, 2005 at 7:03 PM

The question is asking you to come up with an equation that determines how to hit a moving target.

"derive the equation for calculating the shot direction (Sdir) such that at some time (t) the shot would hit the target"

This means come up with a equation that computes the direction of your shot based on how long it takes for your shot to reach the target and the other stated parameters.

"Be sure to derive an equation for t as well!"

This means come up with an equation the computes how long it takes your shot to reach the target based (apparently) on the direction of the shot and the other stated parameters.

It might help to draw a picture.

dawidjoubert

Nov 26, 2005 at 3:25 AM

You face a problem, which may in some cases may never have an answer.

Consider where T moves faster than the projectile but parallel to it.

A possible approach is to simulate the environment, starting at time T0 and then increasing it with Delta

so
T = 0
Delta = 1

while (abs(Distance(FinalTargetPos,Spos) - R) < DesiredAccuracy)
{
R = T * ProjectileSpeed;
FinalTargetPos = TPos + Tvel*T;
switch of Distance(FinalTargetPos,SPos)
{
> R :Delta++;
< R : Delta /= 2;
== R: Bail
}
}

What you have at the top is a deriviation of Binary Searching, ones that is comple you can simple calculate the Direction Vector like this
Direction = FinalTargetPos - SPos;
----------------------------------------------
The above psuedo doesnt consider accuracy but you may argue that the Target is 10x10x10 and thus an accuracy of +-5 garuantees a hit

JohnBolton

Nov 26, 2005 at 1:30 PM

There is a straightforward solution (and it is nothing like dawidjoubert's), but I doubt being "allowed to research the problem" includes asking someone to give you the answer. So I'm going to let you figure it out.

dawidjoubert

Nov 26, 2005 at 2:31 PM

JohnBolton is correct there is a straight forward method, but why shouldnt we tell you?
-------------------------

[Source]            C   ****^           *****     |G      **** F       A|Spos -------------->Tpos            D[/Source]

[/source]

They Simple want you to solve F, and once you have F u can easily get C
A = Direction of the Target,BEARING OF TARGET, lets for this case say its 90 degrees
D = Distance Spos,Tpos
C = Projectile Speed/Magnitude * T
G = Target Speed/Magnitude * T

Because we have C & G & A we can use the sine rule to get

sin(90) sin(F)
-------- = ---------
C G

asin(sin(90)*G/C) = F

G/C = Target Velocity * T / Projectile Speed * T
thus
G/C = Target Velocity / Projectile Speed

Thus the Angle at which the Shooter must aim is

Angle = asin(sin(90)*Magnitude(TargetVelocity)/ProjectileSpeed);
And then u can simple do more substitution to get T
------------------------------------------------------------------------

Translating this into 3d is what you are left to do.

JohnBolton

Nov 26, 2005 at 2:34 PM

Quote:
Original post by dawidjoubert
JohnBolton is correct there is a straight forward method, but why shouldnt we tell you?

Because he's taking a test and you are helping him cheat.

BlackDragon

Nov 26, 2005 at 9:54 PM

Having someone just straight up give me the answer is not what im looking for. It would do me no good to complete the test and perhaps get a job in which I would not have been able to get using my own knowledge only to get fired a few weeks later. I was looking for help in finding the solution and being able to understand the solution vs just being given a solution.

Thanks

BlackDragon

Nov 26, 2005 at 10:37 PM

This is the solution I have come up with.
Dist = Tpos - Spos
Dir = Tvel - Sspeed
t = Dist / Tvel

Bonehed316

Nov 26, 2005 at 11:29 PM

So far no one is correct.

Angle = asin(sin(90)*Magnitude(TargetVelocity)/ProjectileSpeed);

Wrong because sin(90) = 1, so you are doing useless calculations here. What you are getting is not the angle, but an arbitrary value based on the ratio of the target's velocity and the projectile speed.

Dist = Tpos - Spos
Dir = Tvel - Sspeed
t = Dist / Tvel

Dist is true, but how does that help you? The target is moving. If you aim where it is now, when you get there it wont be there anymore.

Dir is incorrect because sSpeed is a scalar value, and you can not subtract vectors and scalars.

t is wrong because you cant divide vectors either. t is defined as a quadratic function, at^2 + bt + c. I will not give you the specifics, as this is the answer ;)

This problem is very complex, and a good physics/calc/math background is required to get to the solution. The iterative method is the easiest way to solve it, and it causes the least amount of dizzyness, but it is also extremely slow in most cases (unless you just get lucky and guess really close on the first divide).

Let me give you this bit of help:

The location of the target at any given time t is going to be tPos + Normal(tVel)*t, which is to say the starting position (tPos) + the velocity of the target (tVel) * the amount of time it moved at that velocity (which is constant, so no worries). The same is true for your projectile, except you dont know the velocity because you dont know its direction (you only know its magnitude). The trick is solving for time first, which proves very difficult without the velocity of the projectile, but it is possible!

You know how to find the location of the target and projectile at a given time t...and you know that when those two equations are equal (or very very near it), they are intersecting! You just need to find a way to get t into a quadratic form, so you can solve it for the correct time. Only one of the answers will be correct. You need a good physics (or calc) background to do this. There is also the case where they will never intersect, which you will need to find as well. As my physics teacher always said, "It's easy if you were paying attention, but if you weren't, you're going to fail!"

dawidjoubert

Nov 27, 2005 at 6:01 PM

Thanks for that insight, im glad to see that it is a very complex question which means im not a complete idiot (my binary/iterative thingy could work), how ever i will continue on my quest to solve this.

NOTE:U are wrong, in some cases there will be 2 possible answers, consider the Target moving faster than the projectile.

Imagine it will move closly past the SHootingPosition, then there will be 2 possiblities

A : Head on, The Projectiles Vector's head will point towards the Targets Vectors Head

B : Collsion Course, the two vectors will look in relatively the same direction and thus the Target will actually hit the projectile

How ever Bonehed316 i would greatly appreciate it if someone would post the solution once BlackDragon has solved it.

PS I didnt know he was doing an exam, must prob not have read the topic properly

Bonehed316

Nov 27, 2005 at 9:51 PM

B is only true if the targets velocity is lower than the projectile speed, otherwise they will never intersect. But in more cases than not, if the targets velocity is larger than the projectile speed, the projectile will never intercept the target.

BlackDragon

Nov 27, 2005 at 10:13 PM

typedef struct Vector{	float x;	float y;	float z;}Vector;void main(){	Vector Tpos;		//Target's starting Pos	Tpos.x = 5.0f;	Tpos.y = 0.0f;	Tpos.z = 5.0f;		Vector Spos;		//Shooter's Pos	Spos.x = 0.0f;	Spos.y = 0.0f;	Spos.z = 0.0f;	float Sspeed = 1.0f;	//shot speed	Vector Tvel;	Tvel.x = -1;	Tvel.y = 0;	Tvel.z = 0;	int t = 0;	float dist  = -999.0f ;	while(dist != Sspeed * t)	{		//update the targets Postion at time (t)		Tpos.x += Tvel.x;		Tpos.y += Tvel.y;		Tpos.z += Tvel.z;		dist = sqrt(((Tpos.x - Spos.x) * (Tpos.x - Spos.x)) + 			((Tpos.y - Spos.y) * (Tpos.y - Spos.y)) + 			((Tpos.z - Spos.z) * (Tpos.z - Spos.z)));				cout << "At Time "<< t << " the Distance is "<< dist << endl;		t++;	}	cout << "At Time " << t << " the bullet would be able to hit the target"<< endl;}

This is what I have come up with to solve for t. I think im on the right track, the next step would be to figure out the angle Spos needs to be facing to hit Tpos at its new location?

Trienco

Nov 28, 2005 at 1:10 AM

This is nothing but random musings and twisted ideas, but here it goes.

They showed an interesting experiment on TV involving a crossbow, a falling melon and the question where you would have to aim at to hit it in flight. Answer: at the melon itself. Both are subject to gravity and it happens to just fit very nicely. The faster the bolt the higher it flies and the sooner it hits.

Now, could that be transfered to the problem? Or would it fall apart where we replace acceleration (gravity) with a constant velocity?

dawidjoubert

Nov 28, 2005 at 4:59 AM

Trienco the example you gave is perfectly correct, how ever consider someone throwing the melon.

You wouldnt have to worry about gravity because ass you say it is applied equally to both objects, how ever you would have to consider the velocity of the melon as soon as it leaves the persons hand, there after it has 0 Acceleration (assuming that you exempt gravity)

-Dawid Joubert

--BlackDragon--
Your iterative method works except it has limits.

First Limit it will only work for problems with whole numbers, instead try the following code.

Secondly your program will go into an infinite loop if the target is moving away from the projectile at a greater speed , thus the projectile will never be able to catch the target!
-
Try this instead it is way faster and will always return the answer if it exists

[Source]#include <windows.h>					// Include the much need windows.h#include <iostream>						// Include our c++ standard header#include <fstream>						// Include this to use ifstream#include <stdio.h>#include <stdarg.h>#include <math.h>#include <iostream>						// Include our c++ standard header for Coutusing namespace std;typedef struct Vector{float x;float y;float z;}Vector;float Distance(Vector v,Vector r){	Vector f;	f.x = v.x - r.x;	f.y = v.y - r.y;	f.z = v.z - r.z;	return sqrt(f.x * f.x + f.y * f.y + f.z * f.z);}float Magnitude(Vector v){	return sqrt(v.x * v.x + v.y * v.y + v.z * v.z);}Vector Normalize(Vector v){	float m =  Magnitude(v);	v.x /=  m;	v.y /=  m;	v.z /=  m;	return v;}void main(){	srand(2);	/* Generate Random Target Position */	Vector Tpos;	Tpos.x = rand()- RAND_MAX/2;	Tpos.y = rand()- RAND_MAX/2;	Tpos.z = rand()- RAND_MAX/2;	// Spos Is always 0,0,0	// Set Projectile Speed to a Constant //	float Sspeed = 2.0f;//shot speed	Vector Tvel;	/* Generate Random Target Velocity with a Mangnitude/Speed of 1.0 */	Tvel.x = -float(rand())/float(RAND_MAX);	Tvel.y = -float(rand())/float(RAND_MAX);	Tvel.z = -float(rand())/float(RAND_MAX);	Tvel = Normalize(Tvel);	float t;	// Minimum Time is if both objects fly directly towards each other!	float MinTime = Magnitude(Tpos) / (Magnitude(Tvel) + Sspeed);	// Maximum Time is if the Target is fly exactly away from the projectile and	// then the projectile must catch it	float MaxTime = Magnitude(Tpos) / (Sspeed - Magnitude(Tvel));	t = (MinTime + MaxTime)/2.0f;	float dist;	float Accuracy = 1.0f;	float inc = t / 2.0f;	int its = 0;	do 	{		its++;		//update the targets Postion at time (t)		Vector newT;		newT.x = Tpos.x + Tvel.x * t;		newT.y = Tpos.y + Tvel.y * t;		newT.z = Tpos.z + Tvel.z * t;		dist = Magnitude(newT);		if (dist > Sspeed * t)		{			// Increase T			t = t + inc;			inc = inc / 2.0f;		}		else if (dist < Sspeed * t)		{			// Decrease T			t = t - inc;			inc = inc / 2.0f;		}		cout << "At Time "<< t << " the Distance is "<< dist << endl;	} while(abs(dist - Sspeed * t) > Accuracy);	cout << "At Time " << t << " the bullet would be able to hit the target"<< endl;	cout << "Iterations : " << its << endl;}[/Source]

[/source][/source][/source][/source][/source][/source]

For highter accuracy try changing all floats to doubles

Regards
----- EDIT --------
You might want to set a Max Iterations limit, at which it will exit, to find the needed time to get a solution simple uses this.

2^I = INT_MAX / Accuracy
Where I is the iterations, note that this is the longest time

[Edited by - dawidjoubert on November 28, 2005 9:59:03 AM]

Fingers_

Nov 28, 2005 at 7:08 PM

The asin() method will give you the correct solution in all possible cases, and an easy way to detect impossible cases (if the value you're feeding to asin is greater than 1, it's impossible to hit the target).

dawidjoubert

Nov 28, 2005 at 8:19 PM

So your saying this : asin(sin(90)*G/C) = F is correct?

Anyways, the estimate program is quite a good example of Binary Iterative searching :-)

--------------------------------------------

Now Fingers the next thing for him to do is convert his 3d problem to a 2d problem which can be done because if take 3 coordinates Spos,Tpos,Tpos+Tvel*1 and use that to construct your plane then your all done :-)

Topic Locked

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