Need some help with math steering behavior stopping on destination point

Question

I have implemented a movement system based on steering behaviors: http://gamedevelopment.tutsplus.com/series/understanding-steering-behaviors--gamedev-12732 where each object has vec2 position, velocity, desiredPosition with 2 constants: maxspeed and acceleration. In each game step, the object's position is updated as follows:

vec2 desiredVel = this.desiredPos - this.position;
desiredVel.truncate(this.maxSpeed);

vec2 steeringForce = desiredVel - this.velocity;
steeringForce.truncate(this.acceleration);

this.velocity += this.steeringForce * dt;
this.velocity.truncate(this.maxSpeed);

this.position += this.velocity * dt;

The problem is stopping. I have been stopping by using a scaling factor that reduces the desiredVel when the object is within a certain distance of the target position:

var dist = desiredVel.length;
if (dist < this.maxSpeed * this.maxSpeed / this.acceleration){
    this.desiredVel *= dist/this.maxSpeed;
}

This goes between the desiredVel calculation and steering force calculation.

Unfortunately, this method is not very exact. Sometimes the object will overshoot its destination and sometimes it will slow down way before the destination is reached. Is there a way to make the object stop on the destination point? That is, it should not overshoot nor slow down prematurely.

Edit: and yes I have seen the arrival section in the link I posted above and it shares this same inexactness. What I want I guess is for the path to look more realistic. That is the object accelerates at the start of path to its max speed then it decelerate at the right timing so that it stops at the destination exactly. (or close enough)

And 2ndly, I also want to know the time it takes for an object to reach from pointA to pointB before the object takes its path. The maxspeed and acceleration is constant and there are no other forces acting on the object within the path. How can i calculate the time?

Answer 1

When acceleration a is constant, use the High School kinematics equations:

1. v = u + a t
2. delta-d = u t + a t ^2 / 2
3. v^2 - u^2 = 2 d (delta-d)
4. delta-d = (v + u) / 2 t

where:

• u is the unitial velocity (sic)
• v is the vinal velocity (sic)
• t is the elapsed time
• delta-d is the displacement from starting position to ending position.

Answer 2

The two equations you are looking for are:

t * v_0 - 0.5 * a * t^2 = d
v_0 - a * t = 0

where t is the elapsed time, v_0 is the optimal velocity, a is maximum acceleration, and d is the distance to the target.

The trick is in interpreting these formula. First, we assume we are in 1D by applying and acceleration to zero any component of velocity that does not lie along the line to the target. Thus our character will move directly towards the target. However, if it just went at maxspeed, it would not be able to stop when it reached the target, would overshoot and thus "orbit".

The solution to these formula tells us v_0 (and t, but ignore that for now), such that if we were to immediately start decelerating at rate a, starting from speed v_0 and at distance d from our target, then we would arrive exactly there with velocity zero. We call this the optimal speed because it is the fastest we can move at distance d and still be able to slow down enough to arrive at velocity zero. Any slower, and we are wasting time not going as fast as we should be, and (crucially) any slower and we will be going too fast to slow down in time. This justifies our use of the term "optimal velocity".

This suggests an algorithm to control our character: look at the current distance, and use it to compute the optimal velocity. If we are far from our target, this may be much higher than our maximum speed, in which case just set the desired velocity to min(v_0, maxspeed). Then, apply an acceleration to bring our velocity to the desired velocity, something like:

accel = constrain((desired_vel - current_vel)/timestep, -maxaccel, maxaccel)

recalling that desired_vel, current_vel, and accel are all 1D quantities along the line between the target and the current position. You need to convert the acceleration back to 2D before you apply it by multiplying by a unit vector pointing towards the target. The division by timestep is required, both to ensure the correct physical units, and to ensure the character accelerates as quickly as possible.

Pragmatically, the solutions are v_0 = sqrt(2 * d * a), t = sqrt(2 * d / a), and this formula might result in slightly too high of a speed due to inexact integration (Euler isn't very exact). Thus as a tweak you might do desired_speed = min(maxspeed, v_0) * 0.98, to ensure you have a little bit of slack in the speed. This results in the character taking a tiny bit more time to reach the target, but also results in fewer overshoots due to integration error. You might consider expanding the definition of what it means to be "at" the target by some small radius to get the character to stop making tiny corrective accelerations, especially if some logic or behavior depends on them "reaching" their destination.

The time estimate is a bit trickier, because the maximum speed and any motion not toward the target complicate things. If you are close enough to the target that you can go desired_vel, then t is the time to arrive. If you are further away, the total time depends on how long it will take to get to maxspeed, how far you travel at maxspeed, and how long you decelerate for. Starting from a stop, the path will actually be symmetric in velocity, so for two points that are far apart (long enough for the character to accelerate to maxspeed), the time can be calculated as:

T = t_a * 2 + (D - 2 * d_a) / maxspeed
t_a = solve for t when v_0 = maxspeed
d_a = solve for d when v_0 = maxspeed

For shorter distances, when D < 2 * d_a, T = 2 * (solve for t when d = D/2), because we accelerate for half the time and distance, then decelerate for the other half of time and distance. Each half effectively has the same d, t, and v_0. Note both of these time calculations rely on solving the first set of equations in different ways.