Jump to content

  • Log In with Google      Sign In   
  • Create Account


Arrive steering behavior


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
14 replies to this topic

#1 dabo   Members   -  Reputation: 148

Like
0Likes
Like

Posted 20 November 2012 - 11:20 AM

Hello everyone,

I am trying to implement the arrive steering behavior that can be found in the book "Programming Game AI by Example". My project is in C# so I had to rewrite the code that came with the book. Below is the relevant part of my steering behavior class.


		public Vector2 SteeringForce { get; private set; }
		public Vector2 Target { get; set; }
		private enum Deceleration
		{
			Fast = 1,
			Normal = 2,
			Slow = 3
		}
		private Vector2 Arrive(Vector2 target, Deceleration deceleration)
		{
			Vector2 toTarget = target - 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, MaxSpeed);
				Vector2 desiredVelocity = toTarget * speed / distance;
				return desiredVelocity - Velocity;
			}
			return new Vector2();
		}
		private Vector2 SumForces()
		{
			Vector2 force = new Vector2();
			if (Activated(BehaviorTypes.Arrive))
			{
				force += Arrive(Target, Deceleration.Fast);
				if (!AccumulateForce(force))
					return SteeringForce;
			}
			return SteeringForce;
		}
		private bool AccumulateForce(Vector2 forceToAdd)
		{
			double magnitudeRemaining = MaxForce - SteeringForce.Length();
			if (magnitudeRemaining <= 0)
				return false;
			double magnitudeToAdd = forceToAdd.Length();
			if (magnitudeToAdd > magnitudeRemaining)
				magnitudeToAdd = magnitudeRemaining;
			SteeringForce += Vector2.Normalize(forceToAdd) * magnitudeToAdd;
			return true;
		}
		public Vector2 Calculate()
		{
			SteeringForce.Zero();
			SteeringForce = SumForces();
			SteeringForce.Truncate(MaxForce);
			return SteeringForce;
		}

And this is how one of my game objects uses the steering behavior class:
		public override void Update(double deltaTime)
		{
			Vector2 steeringForce = SteeringBehaviors.Calculate();
			Vector2 acceleration = steeringForce / Mass;
			Velocity = Velocity + acceleration * deltaTime;
			Velocity.Truncate(MaxSpeed);
			Position = Position + Velocity * deltaTime;
		}

The problem is that I get an oscillating behavior around the target position, the object oscillates less and less and after awhile it stops at the target position. Can anyone see anything in the code I have posted that would cause this oscillating behavior? I fail to see what I have done wrong when I rewrote the code into C# from C++. The samples accompanying the book obviously work so I don't expect any errors in the original code.

I appreciate any help.

Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 12844

Like
0Likes
Like

Posted 20 November 2012 - 01:14 PM

double speed = distance / ((double)deceleration * decelerationTweaker);
  speed = Math.Min(speed, MaxSpeed);
  Vector2 desiredVelocity = toTarget * speed / distance;
  return desiredVelocity - Velocity;


This is fishy. Notice how speed is proportional to distance, but then it gets divided by distance. This means your desiredVelocity is simply toTarget / some_constant. The resulting dynamics are those of an undamped pendulum, so of course you get oscillatory behavior. I don't have the book in front of me to compare the code, but that can't be what they are doing.

Edited by Álvaro, 20 November 2012 - 01:15 PM.


#3 dabo   Members   -  Reputation: 148

Like
0Likes
Like

Posted 20 November 2012 - 03:06 PM

This is a copy paste from the simple soccer example:

Vector2D SteeringBehavior::Arrive(Vector2D TargetPos, Deceleration deceleration)
{
  Vector2D ToTarget = TargetPos - m_pVehicle->Pos();
  //calculate the distance to the target
  double dist = ToTarget.Length();
  if (dist > 0)
  {
	//because Deceleration is enumerated as an int, this value is required
	//to provide fine tweaking of the deceleration..
	const double DecelerationTweaker = 0.3;
	//calculate the speed required to reach the target given the desired
	//deceleration
	double speed =  dist / ((double)deceleration * DecelerationTweaker);	
	//make sure the velocity does not exceed the max
	speed = min(speed, m_pVehicle->MaxSpeed());
	//from here proceed just like Seek except we don't need to normalize
	//the ToTarget vector because we have already gone to the trouble
	//of calculating its length: dist.
	Vector2D DesiredVelocity =  ToTarget * speed / dist;
	return (DesiredVelocity - m_pVehicle->Velocity());
  }
  return Vector2D(0,0);
}


#4 Álvaro   Crossbones+   -  Reputation: 12844

Like
0Likes
Like

Posted 20 November 2012 - 06:09 PM

Oh, actually I misread the code. I thought you were returning the result of that computation directly as force, but you are actually subtracting your current velocity for it, so I guess that's OK.

I am not sure what the problem is. Perhaps you can make a complete small program around the code you posted so we can run it on our own?

#5 dabo   Members   -  Reputation: 148

Like
0Likes
Like

Posted 21 November 2012 - 03:05 AM

Perhaps you can make a complete small program around the code you posted so we can run it on our own?


Ok I will do that when I get home from work.

#6 Álvaro   Crossbones+   -  Reputation: 12844

Like
0Likes
Like

Posted 21 November 2012 - 07:31 AM

I guess it might be a matter of adjusting parameters correctly. The parametrization used in that code is a bit strange to me, but you essentially have a differential equation that looks like a damped harmonic oscillator:

force = -k * (position - target_position) - c * velocity

You'll then compute acceleration as force/mass. The damping ratio is defined as c/(2*sqrt(m*k)). If your damping ratio is under 1, you'll have oscillations. You should aim for a damping ratio of 1 or just a little above. As usual, experimentation is the only way to tell what feels right in your situation.

Of course you can cap the magnitude of the force to some maximum value.

Edited by Álvaro, 21 November 2012 - 07:32 AM.


#7 dabo   Members   -  Reputation: 148

Like
0Likes
Like

Posted 21 November 2012 - 11:24 AM

I guess it might be a matter of adjusting parameters correctly. The parametrization used in that code is a bit strange to me, but you essentially have a differential equation that looks like a damped harmonic oscillator:

force = -k * (position - target_position) - c * velocity

You'll then compute acceleration as force/mass. The damping ratio is defined as c/(2*sqrt(m*k)). If your damping ratio is under 1, you'll have oscillations. You should aim for a damping ratio of 1 or just a little above. As usual, experimentation is the only way to tell what feels right in your situation.

Of course you can cap the magnitude of the force to some maximum value.


Thanks I will look into that.

I have created a minimal program showing the problem, now you can test it yourself. http://www.dabostudios.net/Arrive.zip

#8 ankhd   Members   -  Reputation: 1211

Like
0Likes
Like

Posted 23 November 2012 - 01:38 AM

hello.
Try playing with the DecelerationTweaker Im using 1.3
I only get that problem when the speed is to high.

#9 dabo   Members   -  Reputation: 148

Like
0Likes
Like

Posted 24 November 2012 - 10:43 AM

Thank you for the tip.

I noticed that when I change this line:
Velocity = Velocity + acceleration * deltaTime;

into:
Velocity = Velocity + acceleration;

It appears to work like I expect, it also fixes the seek steering behavior. Can anyone explain this? I thought deltaTime had to be included when calculating both velocity and position. Maybe there is still a problem hidden somewhere.

EDIT: I should add, at higher speeds I need to increase the max force as well.

Edited by dabo, 25 November 2012 - 02:56 AM.


#10 dabo   Members   -  Reputation: 148

Like
0Likes
Like

Posted 25 November 2012 - 03:11 AM

hello.
Try playing with the DecelerationTweaker Im using 1.3
I only get that problem when the speed is to high.


Did you change something else too? Because if I only change the deceleration tweaker to 1.3 I still get the same problem at default max speed 1.6 for example.

#11 Álvaro   Crossbones+   -  Reputation: 12844

Like
1Likes
Like

Posted 25 November 2012 - 04:03 AM

Thank you for the tip.

I noticed that when I change this line:

Velocity = Velocity + acceleration * deltaTime;

into:
Velocity = Velocity + acceleration;

It appears to work like I expect, it also fixes the seek steering behavior. Can anyone explain this? I thought deltaTime had to be included when calculating both velocity and position. Maybe there is still a problem hidden somewhere.


You should definitely keep the multiplication by deltaTime in place. If removing it gives you the behavior you like, you can also get it by dividing the force by deltaTime.

It looks to me like the setup in the code you are using is strange and complicated. I would consider much simpler code, like this (in C++):

Vector2D force_to_arrive(Point2D position, Vector2D velocity, Point2D target_position) {
  const double c = 4.0;
  const double k = 4.0;

  Vector2D position_difference = target_position - position;
  return k * position_difference - c * velocity;
}

Edited by Álvaro, 25 November 2012 - 04:29 AM.


#12 dabo   Members   -  Reputation: 148

Like
0Likes
Like

Posted 25 November 2012 - 05:01 AM

Thank you for your reply.

Yes I thought keeping deltaTime in the calculation was correct. I am just confused as to why the book author's code work but not mine, I don't see any difference and I have tried using the same default values for mass, max force, max speed.

#13 dabo   Members   -  Reputation: 148

Like
0Likes
Like

Posted 26 November 2012 - 12:27 PM

I found a C# implementation of the same example from the book and it had no parenthesis around deceleration * decelerationTweaker like this:

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

When I changed this in my code it appeared to work even with deltaTime:

Velocity = Velocity + acceleration * deltaTime;

I am really confused why I need to remove the parenthesis when all other implementations I have seen (except the one I mentioned above) uses them. I have also tested implementations not from the book and they also result in this oscillating behavior when I use it in my code.

#14 ankhd   Members   -  Reputation: 1211

Like
0Likes
Like

Posted 29 November 2012 - 01:38 AM

Did you change something else too?.

YES.

I also did what you did like this here.
Velocity = Velocity + acceleration;
note I jast added it back then and tryed it. And it has the same problem.

But this is my code here I thik its the way to go.

SteeringForce = SteeringBehaviors->Calculate();

//Acceleration = Force/Mass
D3DXVECTOR3 acceleration = SteeringForce / ComponentMotion->m_dMass;

//update velocity
ComponentMotion->m_vVelocity += acceleration;// * timedelta; REMOVED IT HERE
//make sure vehicle does not exceed maximum velocity

ComponentMotion->m_vVelocity = Truncate(ComponentMotion->m_vVelocity, ComponentMotion->m_dMaxSpeed);
//update the position
ComponentMotion->m_vPos += ComponentMotion->m_vVelocity * timedelta;

#15 dabo   Members   -  Reputation: 148

Like
0Likes
Like

Posted 30 November 2012 - 08:16 AM

Thanks for the reply.

It does decelerate nicely if I remove delta time from the acceleration calculation, but then I get the problem that my object reaches the max speed directly after just one call to Update().




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS