I'm having some problems with obstacle avoidance and I was wondering if it had anything to do with the length of each of the rays around the agent?

Should my feeler rays be the same length in all directions or proportionally longer in the direction of the agent's velocity?

I currently extend all the rays, regardless of their direction, based on the agent's velocity:



/// <summary>
/// Steers the agent to avoid moving obstacles lying in its path
/// </summary>
/// <returns></returns>
private Vector3 ObstacleAvoidance()
{
List<RayCastResult> results = new List<RayCastResult>();
Vector3 steeringForce = new Vector3();

// Feeler length is proportional to the agent's velocity
float speed = agent.Velocity.Length();
float ooMaxSpeed = 1f / agent.MaxSpeed;
float feelerLength = speed * ooMaxSpeed * minFeelerLength;
feelerLength += minFeelerLength;

// For each one of the agent's feelers
for (int i = 0; i < numFeelers; ++i)
{
// Clear the list in preparation for the new ray cast
results.Clear();

if (game.Space.RayCast(feelers, feelerLength, results))
{
float earliestTime = float.MaxValue;
EntityCollidable entityHit = null;
int index = 0;

int numHit = results.Count;

for (int ii = 0; ii < numHit; ++ii)
{
EntityCollidable e = results[ii].HitObject as EntityCollidable;

// Ignore non EntityCollidables
// Ignore feeler collision with the agent
// Keep the earliest time of collision
if (e != null && e.Entity.Tag != agent && results[ii].HitData.T < earliestTime)
{
earliestTime = results[ii].HitData.T;
entityHit = e;
index = ii;
}
}

if (entityHit == null)
{
// Nothing to avoid
continue;
}
else
{
// [2.5D]
Vector3 offset = agent.Position - results[index].HitData.Location;

// 'PerpendicularComponent' method
float projection = Vector3.Dot(offset, agent.Forward);

Vector3 avoidance = offset - (agent.Forward * projection);
avoidance.Normalize();
avoidance *= agent.MaxSpeed;
avoidance += agent.Forward * agent.MaxSpeed * 0.75f;
avoidance -= agent.Velocity;

steeringForce += avoidance;
}
}
}

return steeringForce;
}


However, this produces violent shaking of the agent and not smooth obstacle avoidance:

Video of shaking behaviour


Should I take the dot product of the ray direction and the direction of the velocity and only extend by a multiple of the dot product? (Values less than 0 would be 0)

Easy answer to question... how do YOU do it when YOU navigate? What do YOU care about?

I would care about my velocity relative to the velocities of the objects around me. Is that what you are getting at?

Also, why my AI is constantly jerking from side to side when avoiding obstacles?

The jerking motion is caused by corners falling in the gaps between rays - use more rays (try 30 instead of 10) or concentrate your 10 rays in the direction of travel.
I'd use variable length rays, longer at the front and shorter at the back and sides. See Red3D for more ideas.

The jerking motion is caused by corners falling in the gaps between rays - use more rays (try 30 instead of 10) or concentrate your 10 rays in the direction of travel.

I've upped the number rays to 100 and recorded video with a better frame rate which I have uploaded on YouTube here.

The jerking motion is still there and I'm unsure why as I would have thought 100 rays would be overkill.

The movement of the AI using path finding (without obstacle avoidance) is very smooth as it uses SLERP-ing between orientations:



// Linear movement
Vector3 force = steering.Update(gameTime);
entity.LinearVelocity += force;

// Angular movement
if (entity.LinearVelocity.LengthSquared() > MathTools.EPSILON)
{
// Store current orientation before calculating new orientation
//currentOrientation = entity.Orientation;

// Calculate new orientation based on current velocity
Matrix rotation = new Matrix();
rotation.Forward = Vector3.Normalize(entity.LinearVelocity);
rotation.Up = Vector3.UnitY;
rotation.Right = Vector3.Cross(rotation.Forward, rotation.Up);

destOrientation = Quaternion.CreateFromRotationMatrix(rotation);
destForward = rotation.Forward;
}

// Calculate turn rate
float angleBetweenVelocities = MathTools.UnsignedAngleBetween3DVectors(entity.OrientationMatrix.Forward, destForward);

// Only turn if the angle between the current forward and the new forward is greater than 0 (allowing for numerical errors)
if (angleBetweenVelocities > MathTools.EPSILON)
{
// Limit the interpolation amount based on the turn rate
float maxTurnAngle = turnRate * dtSeconds;
float amount = MathTools.Clamp(maxTurnAngle / angleBetweenVelocities, 0f, 1f);

// Set new orientation using SLERP
entity.Orientation = Quaternion.Slerp(entity.Orientation, destOrientation, amount); //currentOrientation
}


What else could be the cause?

100 rays should certainly do it. OK, so I was wrong about the corners...
Looking at the video I wondering if it's not because of your variable ray length - that seems twitchy too... How does it behave if you fix the ray length to max_velocity*2?
PS I found this pdf on fuzzy navigation some of which you might find interesting.

I'll take a look at the pdf you linked to see if that gives some insight into the problem.

If I keep the ray length constant in all directions:


float feelerLength = agent.MaxSpeed * 2f;


then it makes no difference to the twitchy movement.

I'm completely out of ideas as to how to solve this one. It seems especially odd that this would occur considering that I've ported the obstacle avoidance method from the Steer/Red3D source code.

You're trying to move forwards along a certain path -- why do you care about objects that are behind or beside you?

You care about objects that are in front of you, or that are going to be in front of you.

Concentrate your rays to the front and sides of the object, focussing particularly in front. Unless you're planning on very sudden drastic turns or reversing you shouldn't care what's behind you at all; you'll find out about those things when/if you turn around.


To me it looks like the shaking in your current implementation is the result of your agent reacting to objects that aren't in the way; because you're casting a ray to the side the agent detects that there is an object next to it and attempts to steer away from it, even though it would not have hit said item simply by continuing it's current path.

To me it looks like the shaking in your current implementation is the result of your agent reacting to objects that aren't in the way; because you're casting a ray to the side the agent detects that there is an object next to it and attempts to steer away from it, even though it would not have hit said item simply by continuing it's current path.

I've uploaded another video here showing the agent with all the rays concentrated in the direction of the current velocity. The agent still shakes from side to side but I think I have an idea of what might be causing it.

In my code all the feelers are iterated through and the closest object for each feeler will have an affect on the velocity. The problem is that the effect on the velocity will be the same whether the object is 10 units away or 1 unit away:



Vector3 offset = agent.Position - results[index].HitData.Location;

// 'PerpendicularComponent' method
float projection = Vector3.Dot(offset, agent.Forward);

Vector3 avoidance = offset - (agent.Forward * projection);
avoidance.Normalize(); // Same force no matter what distance.
avoidance *= agent.MaxSpeed;
avoidance += agent.Forward * agent.MaxSpeed * 0.75f;
avoidance -= agent.Velocity;

steeringForce += avoidance;


How can I use the length of the offset to scale the avoidance force correctly and should the 'steeringForce' be an accumulation of all the avoidance forces for all the objects in contact with every feeler?

Do you realize you can get a lot of mileage out of shooting one feeler ray per frame in a random direction in a cone in front of you? This 100 rays thing seems like incredible overkill and certainly won't scale very well.