0
\$\begingroup\$

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").

enter image description here

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):

enter image description here

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

enter image description here

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:

enter image description here

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?

\$\endgroup\$
2
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ This should work the best, as it is solving the difference between the askers agents and the ones used in the tutorial. \$\endgroup\$ – Kronos Jul 2 '14 at 11:37
  • \$\begingroup\$ In the situation in my question, I think this would constantly push the object in opposing directions. For a while it'll be pushed up (only the upper ray regarded), and when the upper ray is not intersecting the obstacle anymore, the lower ray is regarded, which is below the obstacle's center, so now the entity is pushed downwards. And so on, making jiterry movement and the entity doesn't dodge the obstacle. Do you have a solutio to this? \$\endgroup\$ – Aviv Cohn Jul 2 '14 at 13:00
  • \$\begingroup\$ Added how to solve the jitter \$\endgroup\$ – Thijser Jul 2 '14 at 13:37
  • \$\begingroup\$ In extreme carnage, I send 3 rays. check the code :) sourceforge.net/projects/extremecarnage \$\endgroup\$ – v.oddou Jul 15 '14 at 5:57
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ the cul-de-sac situation is absolutely true. but if you control your environment so that only CONVEX obstacles exist, then this solution is OK ! but if not, you need A* and stuff starts to get complex. \$\endgroup\$ – v.oddou Jul 15 '14 at 5:58
  • \$\begingroup\$ Even with convex obstacles you can create cul-de-sacs, if you place them close enough that the entity can't get through them. And yes, once you add proper pathfinding in a dynamic environment, complexity and cost increase substantially. \$\endgroup\$ – Sergio Jul 15 '14 at 6:28
  • \$\begingroup\$ that's right, you need convex AND enough space \$\endgroup\$ – v.oddou Jul 15 '14 at 6:41

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.