Sign in to follow this  
Staryon

How to get the angle and speed to reach a movable point

Recommended Posts

Hi all, I'm been trying to find a solution for this but my math skills are not very high and I haven't found anything yet. I hope you guys may give me some ideas. The problem is the following: - We have a 2D scenario. - There are two points in there, A and B. For each point we know its position (x,y), speed (V), and the current direction (0º to 360º) - We know the maximum speed that A can reach. (Vmax) - B may change its direction and speed at any moment. We don't know the maximum speed that B may reach. Problem: We need to know what angle and speed A should follow to reach B in the shortest amount of time possible. The algorithm will be called every second, since B may be changing its position and angle at any time. Any ideas? I really appreciate your help. Thanks

Share this post


Link to post
Share on other sites
Any reason why there is a maximum speed your 'chaser' can travel at?
Are these like cars, or like spaceships?
Inertia? Newtonian Physics?

How drastically can B change its position and direction? does it have simulated angular momentum and torque and acceleration? or is it totally an arcade object that can do crazy things with no prediction at all?

Share this post


Link to post
Share on other sites
Thanks for your answer, haphazardlynamed

Quote:
Original post by haphazardlynamed
Any reason why there is a maximum speed your 'chaser' can travel at?

Yes, because we are going to have different types of chasers at the same time
on the screen. Each chaser will have its own properties such as maximum speed.
(some chasers may be slower that others)
Quote:

Are these like cars, or like spaceships?

Yes, like cars.
Quote:

Inertia? Newtonian Physics?

No, we don't have to worry about that.

Quote:

How drastically can B change its position and direction?

Just imagine you are driving a car. Do you remember the game 'Supersprint'?
Something like that.

Quote:

does it have simulated angular momentum and torque and acceleration?

Simpler than that. No acceleration either.

Quote:

or is it totally an arcade object that can do crazy things with no prediction at all?

Not too crazy. Usually the direction and speed are constant, but it may change
at any moment.

Share this post


Link to post
Share on other sites
If we assume B's direction and speed to remain constant, then I think the following algorithms will give you decent results. I don't guarantee anything, though. [wink]

Here's the pseudo-code:


Vec2 predictPosition(float dt, B b) {
// Assuming b.heading is in radians,
// b.velocity = b.speed * (cos(b.heading), sin(b.heading))

return b.position + b.velocity * dt;
}

float resolveImpactTime(A a, B b, int accuracy) {
float newEstimate = 0;
Vec2 projectedPosition = b.position;

for (int i = 0; i < accuracy; ++i) {
newEstimate = getCurrTime() + mag(projectedPosition - a.position) / a.maxSpeed;
projectedPosition = predictPosition(newEstimate - getCurrTime(), b);
}

return newEstimate;
}

Vec2 computeMovementDestination(A a, B b, int accuracy) {
return predictPosition(resolveImpactTime(a, b, accuracy) - getCurrTime(), b);
}

// To have A move towards B, simply make A move toward the point returned by computeMovementDestination().




A few notes on the method:

1) It assumes B is travelling with constant speed and heading. It should be straightforward to modify the predictPosition() function to take into account angular velocity. To be honest, though, I don't forsee this causing too many problems as long as you call computeMovementDestination() often enough.

2) I have actually used the iterative algorithm contained in resolveImpactTime() in practice before, so I know it works (provided I didn't make any typos). It's not the most efficient algorithm, and I'm sure there's an analytical solution, but it works. You shouldn't need to set accuracy to anything more than 10, at least not in my experience.

3) The code assumes A is just going to move at its maximum speed.

Share this post


Link to post
Share on other sites
OK
so you dont have intertia and stuff like that to worry about
and its a car

this makes it simpler, since you can basically assumme that you move where youre pointed, with no delay or inertia to compensate the angle for or whatever

First of all, if B is moving away from A, then A Must have a max speed greater than B or you Can't ever reach it.
So do this check first, or you'll get NULL solutions.

Id go with:
start by assuming that B won't change direction for now. If we take its current direction and speed, we can parametarize a formula for B's future position as a function of Time.
next assume that A can travel in any direction it wants, at its max speed from current location. Since we haevn't chosen the direction of A Yet, the possible future postion of A is a circle who's radius can be parametarized as a function of Time as well.

So we have two functions of Time now, PositionB(T) and RadiusA(T)
using pythagorean therorm on PositionB, we can convert to a formula of the distance from A to B.
getting: DistB(T)
DistB(T) and RadiusA(T) can now be combined as a system of equations to find the exact time T, which is the earliest possible point that A could reach B. (find the T condition where they match)

if we then plug T back into PositionB(T), we can get the location of this possible interception point. Aim A to steer towards this location at max speed.

Details of the math are left as an exercise... based on the number of variables, this should be solvable.



since your objects will change their paths over time(dont move straight as assumed), the above will need to be recalculated each update
It should converge though.

Share this post


Link to post
Share on other sites
haphazardlynamed,

Thanks for your reply. I'm trying to follow your algorithm and I think I got it, but I still have some problems with the functions.

Could you give me more details about how to calculate RadiusA(T)?
The max speed should be included there, right?

nilkn, I'm still studying your algorithm. I'll get back to you later.

Thanks you guys!

Share this post


Link to post
Share on other sites
nilkn

Sorry about these questions, because I know they are too basic, but as I said I'm very new with all this.

1. Is Vec2 something like this?


struct
{
float x;
float y;
float heading;
}




2. In the predictPosition function, when you do

return b.position + b.velocity * dt;



Should I calculate that for x and y ? I'm not sure how to make that operation if 'position' has 2 coordinates (x,y)

3. Is mag(A) = sqrt (x*x + y*y ) ?

Sorry about these stupid questions :(

I think if I got an answer to these questions it will be easier for me to understand your algorithm.

Share this post


Link to post
Share on other sites
Quote:
Original post by Staryon
Could you give me more details about how to calculate RadiusA(T)?
The max speed should be included there, right?


Radius is just the possible distance A can travel, with no information about the direction it is pointed.
So maxSpeedA*Time = radius.

In reality, since this is a car, and cars cannot make sharp turns instantly, rather than a circle of possible locations A can reach, it is probably really a irregular shape like a Cardiod (heart shape) or some kind of oval.
But since this calculation is going to be repeated each gameloop, the approximation should be good enough. If you want to be safer about it, you can Under-Estimate the radius of A's interception circle... and multiply it by .9 or something to give a saftey margin.


Regarding Vectors
generally, a Vector does not include a 'heading' value, but if you want to save that information too, it shouldn't hurt. Just make sure the heading really matches up with the x,y information when they change.

Share this post


Link to post
Share on other sites
haphazardlynamed, thanks for the explanation. I think I'm getting closer.

PositionB(T) = Vb * T
RadiusA(T) = Vmaxa * T
DistB(T) = sqrt ( (Xa-Xb)^2 + (Ya-Yb)^2 )

Now I need to combine RadiusA(T) and DistB(T) but I cannot find the way of getting T from DistB(T)
Do you know what I'm missing?

Thanks. I really really appreciate all your help.




Share this post


Link to post
Share on other sites
You need to break up the PositionB function into X and Y components and plug its parts into your Distance forumula (subsititute Xb and Yb), then Distance will have a T variable.

From there, if you equate DistB and RadiusA... you should be able to simplfy it to Quadratic Forumla.

Share this post


Link to post
Share on other sites
Quote:
Original post by Staryon
Is this correct?

PositionB(T) = ( Xb+V*T , Yb+V*T )

So

DistB(T) = sqrt ( (Xa-(Xb+V*T))^2 + (Ya-(Yb+V*T) )^2 )


Assuming that 'V' is a vector like the one you asked about earlier.
what you want is the individual x and y coord pieces, not the entire vector in that formula

so
PositionB(t)= (Xb+V.x*t , Yb+V.y*t)

DistB(T) = sqrt ( (Xa-(Xb+V.x*T))^2 + (Ya-(Yb+V.y*T) )^2 )



RadiusA(T)= maxSpdA*T

equate:

RadiusA(T)=DistB(T)
maxSpdA*T=sqrt ( (Xa-(Xb+V.x*T))^2 + (Ya-(Yb+V.y*T) )^2 )
maxSpdA^2*T^2 = (Xa-(Xb+V.x*T))^2 + (Ya-(Yb+V.y*T) )^2
maxSpdA^2*T^2 = Xa^2 -2(Xb+V.x*T) + (Xb+V.x*T)^2 + Ya^2 -2(Yb+V.y*T) +(Yb+V.y*T)^2
maxSpdA^2*T^2 = -2V.x*T + (Xb+V.x*T)^2 -2V.y*T +(Yb+V.y*T)^2 + Xa^2 -2Xb + Ya^2 -2Yb
maxSpdA^2*T^2 = -2V.x*T + Xb^2 + 2(V.x*T) + V.x^2*T^2 -2V.y*T + Yb^2 +2V.y*T +V.y^2*T^2 + Xa^2 -2Xb + Ya^2 -2Yb
maxSpdA^2*T^2 = + V.x^2*T^2 +V.y^2*T^2 -2V.x*T + 2(V.x*T) -2V.y*T +2V.y*T + Xa^2 -2Xb + Ya^2 -2Yb + Xb^2 + Yb^2

0 = +V.x^2*T^2 +V.y^2*T^2 -maxSpdA^2*T^2 +Xa^2 +Ya^2 +Xb^2 +Yb^2 -2Xb -2Yb
This is Quadratic, solve using Quadratic Formula


You might want to work all that out separatly to doublecheck, since I Probably made mistakes...

Share this post


Link to post
Share on other sites
Quote:
Orignal post by Staryon
nilkn, I'm still studying your algorithm. I'll get back to you later.


My algorithm is similar to what is being illustrated in this image from the article JBourrie linked you to:



We are, of course, interested in the Pursuit path, not the Evade path. My method is to move A not towards B's current position, but towards where we predict B will be if it continues moving in a straight line until we hit it.

This is a difficult problem to solve analytically. Although I'm sure it's possible, I instead opted to use a simple numerical algorithm to compute how far forward in time we should project B's position. We then use this time value to actually compute the projected future position of B, and move A towards this point.

Quote:
Orignal post by Staryon
1. Is Vec2 something like this?


Yes, Vec2 simply referred to any valid class representing a 2-dimensional vector. In most cases, however, it would not contain a heading member. I also assumed the class had overloaded operators appropriate for a vector.

Quote:
2. In the predictPosition function, when you do

return b.position + b.velocity * dt;

Should I calculate that for x and y ? I'm not sure how to make that operation if 'position' has 2 coordinates (x,y)


Yes. b.position and b.velocity are vectors, so that code could be expanded into:


Vec2 predictedPosition;
predictedPosition.x = b.position.x + b.velocity.x * dt;
predictedPosition.y = b.position.y + b.velocity.y * dt;

return predictedPosition;


The value dt represents how far forward in time to project B's position.

Quote:
3. Is mag(A) = sqrt (x*x + y*y ) ?


Yes.

Keep in mind that the code snippet I posted was pseudo-code. It was intended to illustrate the concepts using code, not as a piece of code ready to copy-and-paste into your project.

Share this post


Link to post
Share on other sites
haphazardlynamed,
Thanks a lot for you effort and taking the time for doing those calculations. I am going to try to do the same thing by myself.
I think I finally understand how to do it! I will let you know how was everything tomorrow.

nilkn,

Quote:

Keep in mind that the code snippet I posted was pseudo-code. It was intended to illustrate the concepts using code, not as a piece of code ready to copy-and-paste into your project.


Yes, It's just I want to understand the whole algorithm before trying to code anything.

Just one more thing, when you say
b.velocity = b.speed * (cos(b.heading), sin(b.heading))

what operation do you mean with (cos(b.heading), sin(b.heading))?

Thanks for your help!!

Share this post


Link to post
Share on other sites
Quote:
Original post by Staryon
Just one more thing, when you say
b.velocity = b.speed * (cos(b.heading), sin(b.heading))

what operation do you mean with (cos(b.heading), sin(b.heading))?

Thanks for your help!!
(cos(b.heading), sin(b.heading)) is a vector. In code it would look like:
vector2 direction;
direction.x = cos(b.heading);
direction.y = sin(b.heading);
b.velocity = b.speed * direction;

Share this post


Link to post
Share on other sites
I'm back.

nilkn,

Today I'm trying your method. I think at this moment I understand both of them *THANKS A LOT TO YOU AND TO haphazardlynamed* , but I still have a couple of questions about yours.

1. I'm not sure about the getCurrTime() function. What should it return?
Should it return the number of seconds elapsed since you started the process?

2. Just for testing, I have implemented your pseudocode in C++.
This is how looks like.


struct stVelocity
{
float x;
float y;
};

struct stPosition
{
float x;
float y;
};

struct Car
{
stPosition position;
float speed;
float heading;
float MaxSpeed;
};

Car a;
Car b;
int T;
int accuracy;

stPosition predictPosition ( float dt, Car b )
{
stVelocity temp;

temp.x = b.speed * cos(b.heading);
temp.y = b.speed * sin(b.heading);

stPosition predictedPosition;
predictedPosition.x = b.position.x + temp.x * dt;
predictedPosition.y = b.position.y + temp.y * dt;

return predictedPosition;
}

float resolveImpactTime ( Car a, Car b, int accuracy )
{
float newEstimate = 0;
stPosition projectedPosition;
projectedPosition.x = b.position.x;
projectedPosition.y = b.position.y;

stPosition Aux;

for ( int i=0; i< accuracy; ++ i )
{
Aux.x = projectedPosition.x - a.position.x;
Aux.y = projectedPosition.y - a.position.y;
newEstimate = T + sqrt( Aux.x*Aux.x + Aux.y*Aux.y ) / a.MaxSpeed ;

projectedPosition = predictPosition( newEstimate - T, b);
}

return newEstimate;
}

stPosition computeMovementDestination( Car a, Car b, int accuracy )
{
return predictPosition( resolveImpactTime( a, b, accuracy) - T, b );
}







And I have added some test data like this:


accuracy = 5;
b.position.x = 0;
b.position.y = 1000;
b.speed = 40;

a.position.x = 0;
a.position.y = 0;
a.MaxSpeed = 40;

// 1 degree = 0.0174532925 radians
b.heading = 270 * 0.0174532925;

stPosition res;
res = computeMovementDestination( a, b, accuracy );







In that example, B is going South (270º) and A and B are going at the same speed. If A is located in (0,0) and B is located in (0,1000)
Shouldn´t they meet at (0,500)?
For some reason, the results that I get are (1.192488E-05,0)
I think Y shouldn´t be zero... because that´s the starting point of A

I think there is a problem when both have the same speed or A's maximum speed is slower that B's current speed.
Do you think there is something wrong with the algorithm?

Thanks

[Edited by - Staryon on May 25, 2006 1:56:51 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this