Arrive steering behavior

I bought a book called Programming game AI by example and I am trying to implement the arrive steering behavior. The problem I am having is that my objects oscillate around the target position; after oscillating less and less for awhile they finally come to a stop at the target position. Does anyone have any idea why this oscillating behavior occur? Since the examples accompanying the book are written in C++ I had to rewrite the code into C#. Below is the relevant parts of the steering behavior:

private enum Deceleration
{
Fast = 1,
Normal = 2,
Slow = 3
}

public MovingEntity Entity { get; private set; }

public Vector2 SteeringForce { get; private set; }

public Vector2 Target { get; set; }

public Vector2 Calculate()
{
SteeringForce.Zero();

SteeringForce = SumForces();

SteeringForce.Truncate(Entity.MaxForce);

return SteeringForce;
}

private Vector2 SumForces()
{
Vector2 force = new Vector2();

if (Activated(BehaviorTypes.Arrive))
{
force += Arrive(Target, Deceleration.Slow);

if (!AccumulateForce(force))
return SteeringForce;
}

return SteeringForce;
}

private Vector2 Arrive(Vector2 target, Deceleration deceleration)
{
Vector2 toTarget = target - Entity.Position;

double distance = toTarget.Length();

if (distance > 0)
{
//because Deceleration is enumerated as an int, this value is required
//to provide fine tweaking of the deceleration..
double decelerationTweaker = 0.3;

double speed = distance / ((double)deceleration * decelerationTweaker);

speed = Math.Min(speed, Entity.MaxSpeed);

Vector2 desiredVelocity = toTarget * speed / distance;

return desiredVelocity - Entity.Velocity;
}

return new Vector2();
}

{
double magnitudeRemaining = Entity.MaxForce - SteeringForce.Length();

if (magnitudeRemaining <= 0)
return false;

return true;
}


This is the update method of my objects:

public void Update(double deltaTime)
{
Vector2 steeringForce = Steering.Calculate();

Vector2 acceleration = steeringForce / Mass;

Velocity = Velocity + acceleration * deltaTime;

Velocity.Truncate(MaxSpeed);

Position = Position + Velocity * deltaTime;
}


If you want to see the problem with your own eyes you can download a minimal example here.

I'm sure your steering code is fine, however there are some values you need to change to get it to work properly. There are a few factors to steering that need to be accounted for to successfully stop the first time.

If your mass is too high or your acceleration is too low the object will oscillate. The object won't have the power it needs to stop its self before overshooting the target. This can be solved by increasing the acceleration available for stopping, or by increasing the stopping distance.

Well, looking at your steering code, it is a little strange. There's no point in your arrival where the acceleration will point away from the target. That's fairly critical for slowing down. You can easily test this by manually taking some values and plugging them into your code, calculating the values by hand as you step through your code. You'll find that currently your code just decreases your acceleration more and more as you approach the target. You need to go negative at some point to stop your entity.

You need to define a distance at which to start slowing down. You'd likely want to decide this distance based on the entity's max speed and max acceleration. The distance it starts slowing down is the maximum distance required to stop with full acceleration away from the target. See the pseudo code below to get an idea of how to implement steering like that. The difference is that the below only uses speed, not acceleration, so you'll need to update it accordingly:

target_offset = target - position
distance = length (target_offset)
ramped_speed = max_speed * (distance / slowing_distance)
clipped_speed = minimum (ramped_speed, max_speed)
desired_velocity = (clipped_speed / distance) * target_offset
steering = desired_velocity - velocity


You can find more excellent steering examples here. Including the arrival behavior. Finally, this paper has more information on how to actually implement these algorithms.

• Thank you that makes sense, since I want to be able to stop pretty hard I thought I would increase the max force. I set max force to 100 and max speed to 16, when logging the force used each time step it never seems to use more than what max speed is set to and this happens when the object is standing still and is about to start moving for the first time -> desiredVelocity.Length() = max speed and Entity.Velocity = 0. If increasing max force doesn't make the object use all the force it needs to stop in time what should I do? – dbostream Nov 25 '12 at 17:01
• What do you mean when you say the "difference" is the pseudo code only uses speed not acceleration? different oppose to what? my current code uses speed as well. I tried to implement code in my arrive method from the pseudo code and objects do stop if I use a very big slowing_distance, but then it takes ages to reach the target. Looking at your second link, that animation shows pretty much how I want it but I cannot get anywhere near that sharp deceleration. If my object would max the use of force when decelerating I believe I could start slowing down much closer to the target like I want. – dbostream Nov 30 '12 at 12:12
• I mean that it only uses velocity. So it will produce your desired velocity, but you still need to figure out the acceleration to use. You can do simple and just use the difference in your current speed and target speed as your acceleration, or something more complex to try to use the maximum acceleration possible. Seems like you'll wan to do the latter, since you've been wanting short start/stop distances. – MichaelHouse Nov 30 '12 at 15:08
• Ok I will see if I can come up with something to make use of more force if there is any available, because as I mentioned earlier right now if max speed is for example 16 no more force than 16 is used even if I set max force to 100 it seems. One thing I noticed when I was playing around a bit was that when I remove deltaTime from the velocity calculation the object decelerates nice and sharp with my original code. However this change also means my objects reach max speed after just one Update() call which is bad. I think deltaTime should be there I just found the result interesting. – dbostream Nov 30 '12 at 18:18

Your arrive behaviour keeps on triggering unless the moving entity has exactly hit the target. This is fine if your time delta and/or your velocity are so small that the position delta in Update won't overshoot your target, unfortunately, this is not the case at first. This results in the oscillation you see before the moving entity finally stops moving.

To fix this, add an arrival threshold parameter, and change Arrive like this:

// Tweak this threshold parameter to prevent oscillation.
double arrivalThreshold = 0.1;
double distance = toTarget.Length();

if (distance > arrivalThreshold)

• I still get the oscillating behavior, I tried many different threshold values. Also the book uses the distance > 0 comparison and apparently it works. Thanks for trying to help. – dbostream Nov 25 '12 at 12:53