Problems with Obstacle Avoidance steering behavior

Question

I learned how to implement the Obstacle Avoidance steering behavior from this tutorial. The approach depicted in this tutorial (simplified) is this (note that I'm using rectangular OBBs for obstacles, not circles):

The entity that avoids obstacles will have a 'ahead' vector, representing the entity's 'sight'. It will be equal to the velocity vector, but scaled to some length (the "sight distance").

For each entity in the "sight distance" radius from the entity, we check if it contains the the 'edge' of the ahead vector, marked with a red dot (actually the vector itself treated as a point):

For an entity that contains the red dot, we calculate the vector from the center of the entity to the red dot:

This vector (scaled by a scalar MAX_AVOIDANCE_FORCE) is the avoidance force. We apply it on our entity, and it should avoid the obstacle.

However, what happens in practice after applying the force is this:

As you can see, the entity is about to get stuck on the obstacle. That's because it doesn't sense it's about to collide, because the obstacle doesn't contain the edge of the 'ahead' vector.

So: what would be a good solution to this problem? How should I implement the algorithm?

Answer 1

One good solution is to send 2 rays from the upper and lower bound of the object rather then in the middle. You can then use the algorithm you were using before but use collisions for both rays rather then one. Don't forget to set the direction to the correct value of only one ray hits something (that is away from that ray). If both rays hit an object just make a choice (or ask the object what it's upper and lower bounds are and move towards what is closer)

Answer 2

One way to solve this, given you're treating you entity as a point, is increase the size of the avoid targets by the size of the main entity.

With circles you just add you radius to each target.

Also circle targets are quite easy to check if you compare the squared radius. So you don't need to take the root of vector of differences of the points.

some code to demo, if you have a pow function or macro:

#define pow2(a) ((a)*(a))

then for each entity to store a squared version of it's radius:

entX.powrad = pow2(entX.rad)

then to compare the ahead in your picture verse entC you can do:

pointInCircle = (pow2(ahead.x-entC.x) + pow2(ahead.y-entC)) < (this.powrad + entC.powrad)

I'm sure this is simpler than using a square.

Answer 3

If you want to keep your agents as OBBs, then you'll have to do a proper intersection test.

The problem you're having is that you're treating the moving entity as a point, and doing a simple raycast. You'll have to do a sweep test.

If you're sticking with OBBs that can move in arbitrary directions an exact solution will be hard work. This article explain how to do sweep tests but only covers circles and AABBs. This question answers how to do OBB intersection, but doesn't include sweep tests. But an extruded OBB is no longer an OBB, so you'll have to do general convex shape collision, which is harder. Here's a discussion.

Alternatively, you can cheat a little by doing multiple OBB tests, moving the entities a bit each time. Depending on the speed at which they move, two or three tests might be enough (one halfway, one at the end point).

If you don't find an intersection, all is good, the path is clear. If you find one, then you need to find the direction of steering. For that, you can just check which side of the movement direction the obstacle is, by doing some vector math (cross product is your friend). You can use the center point of the obstacle for this, like in your example.

This solution will address your problem but is not perfect. This steering method is fully reactive, and will get in trouble in certain scenarios (like a cul-de-sac).