0
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Acceleration is not constant. + acceleration at start, 0 at middle and - acceleration at end. I am not very smart so can you show an sample implementation? \$\endgroup\$ – user62462 Mar 6 '15 at 6:29
  • \$\begingroup\$ @user62462: Then please correct with 2 constants: maxspeed and acceleration in your question. \$\endgroup\$ – Pieter Geerkens Mar 6 '15 at 6:30
  • \$\begingroup\$ They are constants in the sense the variable itself is constant. I believe however, the values used in calculation is not uniform across the path. \$\endgroup\$ – user62462 Mar 6 '15 at 6:32
  • \$\begingroup\$ @user62462: I have directed you to the necessary mathematical tools - now it is up to you to actually write the program. \$\endgroup\$ – Pieter Geerkens Mar 6 '15 at 6:35
  • \$\begingroup\$ I have googled those formulas as well but I do not know how to utilize them. If I did, then I dont need to ask this question. They do say the devil is in the implementation details. \$\endgroup\$ – user62462 Mar 6 '15 at 6:37
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer. Is accel = constrain((desired_vel - current_vel)/timestep, -maxaccel, maxaccel) the same as how I have been using the steeringForce in my calculation? It is the first time I have seen a divide by timestep. For the time estimate, what if the object is already moving in some arbitrary direction at the start? \$\endgroup\$ – user62462 Mar 6 '15 at 16:39
  • \$\begingroup\$ First, steeringForce is actually an acceleration. There is no mass here, so no force. Second, the division by timestep is critical. Ideally, after you execute this.velocity += this.steeringForce * dt;, then the new velocity is the desired velocity. This happens precisely when this.steeringForce * dt == desired_vel - this.velocity, i.e. when this.steeringForce == (desired_vel - this.velocity)/dt!! However, we are very unlikely to be able to apply such a big acceleration, hence the constrain. This error could cause overshoots because without the dt, you won't slow fast enough! \$\endgroup\$ – user41442 Mar 7 '15 at 7:24
  • \$\begingroup\$ If the character starts with some velocity, then it is unlikely you will be able to calculate a closed form for the time of arrival. You could work with an estimate derived from these equations plus some adjustment factors or simulate the motion with large timesteps. \$\endgroup\$ – user41442 Mar 7 '15 at 7:25
  • \$\begingroup\$ I cannot use the divide by timestep because I need to support a timestep of 0. However, I realized that line is basically equivalent to setting the length of acceleration vector to either -max acceleration, 0 or +max acceleration and I have worked out a solution for my problem 1. I think I ll start another question for problem 2. Thanks for your help. \$\endgroup\$ – user62462 Mar 7 '15 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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