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

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?

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.

Quote:Original post by JBourrie
Craig W Reynolds has all the answers

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

Thanks

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:



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.

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.

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!

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?



2. In the predictPosition function, when you do

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.