Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

In the game I am developing, I have to calculate if my vehicle (1) which in the example is travelling north with a speed V, can reach its target (2). The example depict the problem from atop:

enter image description here

There are actually two possible scenarios: V is constant (resulting in trajectory 4, an arc of a circle) or the vehicle has the capacity to accelerate/decelerate (trajectory 3, an arc of a spiral).

I would like to know if there is a straightforward way to verify if the vehicle is able to reach its target (as opposed to overshooting it). I'm particularly interested in trajectory #3, as I the only thing I could think of is integrating the position of the vehicle over time.

EDIT: of course the vehicle has always the capacity to steer, but the steer radius vary with its speed (think to a maximum lateral g-force).

EDIT2: also notice that (as most of the vehicles in real life) there is a minimum steering radius for the in-game ones too).

share|improve this question

1 Answer 1

up vote 15 down vote accepted

If you can vary your speed (thus your angle of steer) you will always find a solution, starting from the degenerate one where the entity is almost stopped rotating in a little circle until pointing the target.

If you can't vary your speed, you can think about unreachable areas or shadows that you can not reach even using your better steer, if the target is in those areas you cant reach it (unless "overshoot" you can even surpass them and put them out of the shadow area).

Your best steer let you to turn left/right on an arc of a circle, letting you to draw a complete circumference:

shadows

As you can see what is inside one of the two circles cant be reached directly.

A body of mass m that is steering over a curve with radius of curvature r, experiences a radial apparent Centrifugal force caused by the inertial behavior of the body, equal to:

Fc = mV^2/r

where V is the speed of the body (the lenght of the velocity vector); being the acceleration of a body due a force being:

a=F/m

our acceleration is:

a=V^2/r

If we say that am is the maximum acceleration we obtain that:

rm=V^2/am

where rm is the mimimum radius using the maximum acceleration.

When you want to test if the veicle in P moving at speed V can reach the target in T you have to:

1) compute C1 and C2 as:

c1 and c2

2) test the miminum distance of P from C1 and C2 as follow:

radius test

If d is greater than rm this means that T is outside both the shadows and then is reachable by the vehicle simply adjusting the steer under the steer constraint. (to be more precise there is a path under constraints that let the function of distance between T and P be monotonically decreasing)

[UPDATE]

If it possible to change the velocity, is always possible to get an arc (i.e. a velocity/radial accelleration couple) that goes from P to T. This is possible because the radius becomes a truly degree of freedom.

This is a possible construction:

target path

The black line is the axis where the center of circles may lay: it is perpendicular to the current facing of the vehicle and passes through its center of rotation.

The green segment represents the line that is perpendicular to the one that connects the center of the vehicle with the target and passes through the middle of that distance.

The green line crosses the black one exactly at the center of the desired arc. The length of the orange segment tell us the radius of turning that can be achieved by regulating the velocity and turning at maximum steer or regulating both the velocity and the steer to stay under the constraint

share|improve this answer
    
Thank you for having taken the time to write this detailed answer (+1). I need to "study" it a bit, but from a first reading it seems to me that your first statement "you will always find a solution..." is not necessarily true: the existence of a minimum steering radius implies that there always will be a "shadow area" whose limit will define a sort of "orbit" around the target... Or am I wrong? [This is indeed the real problem for me, as the calculation for V=k are straightforward...] –  mac Sep 3 '11 at 16:39
    
@mac if the target is not in the same place of your vehicle, you can slow down so rmin generates a circle small enough to not contain the target. When you are in this condition you can set your velocity so the target lay exactly on your circumference! –  FxIII Sep 3 '11 at 17:01
    
@Fxill - Again, thank you for the update, if it was possible, I would give you a second +1 for the dedication! :) Still, I fail to understand from your explanation how you account for both the acceleration and the initial velocity: the entire problem relies in the fact that over time the velocity will change (arc of a spiral). I am under the impression there might be simply not enough space for the vehicle to slow enough / get a radius small enough to intercept the target... or am I wrong? –  mac Sep 3 '11 at 18:56
    
@mac lets say am = 1 then rm = v^2; if d=|P-T| > 0 the you can choose v^2 < d/2; if d = 0 it means that P = T so you already reached your target... –  FxIII Sep 3 '11 at 20:36
    
Thank you, I tried to code it and it worked! Answer accepted. :) –  mac Sep 5 '11 at 21:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.