• 13
• 18
• 19
• 27
• 10

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

This topic is 4311 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 on other sites

Quote:
 Original post by haphazardlynamedAny 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 on other sites
Quote:
 Original post by JBourrieCraig W Reynolds has all the answers

Could you be more concrete? I checked that website but there are tons of articles.

Thanks

##### 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 on other sites
Quote:
Original post by Staryon
Quote:
 Original post by JBourrieCraig W Reynolds has all the answers

Could you be more concrete? I checked that website but there are tons of articles.

Thanks

Steering behaviors

##### 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 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.

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 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.