Help with Obstacle Avoidance Behavior

Hi everyone. I'm facing some issues while implementing the steering behaviors such as wall or obstacle avoidance. I share these issues with you as some questions and hope you could help me.

1 - Why do we need to use wall or obstacle avoidance at all when we use A* search algorithm as we know that it ignores obstacle nodes in the search.

2 - the implementation of obstacle avoidance I've accomplished is the one explained in the book Programming Game AI by Examples which use steering behaviors for a 2D space. Shoud I take advantages of raycast or collision detection instead for implemening such a behavior in a 3D space or that one is enough?

3 - Any obstacle avoidance behavior explanation I've seen either in the book or on the Internet assumes that the obstacles are circles. what about for rectangular obstacles? Is there any differences in the calculations?

1. A* is a great pathing system for a known environment, if you can design your system in a way that A* is fine enough for avoidance systems, then by all means, solely use A*.

however, sometimes A* can only be used for generating an overview of the path to take, but doesn't describe how the object should reach a node, particularly for highly dynamic scenes, where an fixed A* grid is simply not precise enough. At the end of the day, it's upto you to choose how your objects well get from point A to point B.

2. I can not comment, as i've not read the book.

3. a circle is used because that is simply the shape which you will always end up with. since obstacle avoidance relies on generating one(or two) points that allow's your avoiding obstacle to avoid the other object, you've successfully generated a circle(which is a center point, and a radius, the radius is the distance from the center, to this arbitrary point.)

since any object well have to be decomposed into a circle to be successfully avoided, then it's simpler to only work with circle's when presenting the idea.

[quote name='zar2012' timestamp='1350152727' post='4989846']
Hi everyone. I'm facing some issues while implementing the steering behaviors such as wall or obstacle avoidance. I share these issues with you as some questions and hope you could help me.

1 - Why do we need to use wall or obstacle avoidance at all when we use A* search algorithm as we know that it ignores obstacle nodes in the search.

2 - the implementation of obstacle avoidance I've accomplished is the one explained in the book Programming Game AI by Examples which use steering behaviors for a 2D space. Shoud I take advantages of raycast or collision detection instead for implemening such a behavior in a 3D space or that one is enough?

3 - Any obstacle avoidance behavior explanation I've seen either in the book or on the Internet assumes that the obstacles are circles. what about for rectangular obstacles? Is there any differences in the calculations?

1. A* is a great pathing system for a known environment, if you can design your system in a way that A* is fine enough for avoidance systems, then by all means, solely use A*.

however, sometimes A* can only be used for generating an overview of the path to take, but doesn't describe how the object should reach a node, particularly for highly dynamic scenes, where an fixed A* grid is simply not precise enough. At the end of the day, it's upto you to choose how your objects well get from point A to point B.

2. I can not comment, as i've not read the book.

3. a circle is used because that is simply the shape which you will always end up with. since obstacle avoidance relies on generating one(or two) points that allow's your avoiding obstacle to avoid the other object, you've successfully generated a circle(which is a center point, and a radius, the radius is the distance from the center, to this arbitrary point.)

since any object well have to be decomposed into a circle to be successfully avoided, then it's simpler to only work with circle's when presenting the idea.
[/quote]

Thanks for answering slicer4ever.
but what if we have a rectamgular cube with a long length and short width in the middle of the room? should we consider it as a wall? in this case we can't determine any circle since the length and the width are not the same size.

[quote name='slicer4ever' timestamp='1350171112' post='4989923']
[quote name='zar2012' timestamp='1350152727' post='4989846']
Hi everyone. I'm facing some issues while implementing the steering behaviors such as wall or obstacle avoidance. I share these issues with you as some questions and hope you could help me.

1 - Why do we need to use wall or obstacle avoidance at all when we use A* search algorithm as we know that it ignores obstacle nodes in the search.

2 - the implementation of obstacle avoidance I've accomplished is the one explained in the book Programming Game AI by Examples which use steering behaviors for a 2D space. Shoud I take advantages of raycast or collision detection instead for implemening such a behavior in a 3D space or that one is enough?

3 - Any obstacle avoidance behavior explanation I've seen either in the book or on the Internet assumes that the obstacles are circles. what about for rectangular obstacles? Is there any differences in the calculations?

1. A* is a great pathing system for a known environment, if you can design your system in a way that A* is fine enough for avoidance systems, then by all means, solely use A*.

however, sometimes A* can only be used for generating an overview of the path to take, but doesn't describe how the object should reach a node, particularly for highly dynamic scenes, where an fixed A* grid is simply not precise enough. At the end of the day, it's upto you to choose how your objects well get from point A to point B.

2. I can not comment, as i've not read the book.

3. a circle is used because that is simply the shape which you will always end up with. since obstacle avoidance relies on generating one(or two) points that allow's your avoiding obstacle to avoid the other object, you've successfully generated a circle(which is a center point, and a radius, the radius is the distance from the center, to this arbitrary point.)

since any object well have to be decomposed into a circle to be successfully avoided, then it's simpler to only work with circle's when presenting the idea.
[/quote]

Thanks for answering slicer4ever.
but what if we have a rectamgular cube with a long length and short width in the middle of the room? should we consider it as a wall? in this case we can't determine any circle since the length and the width are not the same size.
[/quote]

you can always get a circle from any shape, simply take the furthest point from the center, and you have a circle which encapsulates the object.

does that circle accurately bound the entire object? not exactly, does the collision avoidance system work decent enough? that's up to you. so if you want a better refined circle, you could construct an eclipse, which can be used pretty decently with only a few modifications to the general collision avoidance algorithm

well I understand that but let me clarify my problem.
suppose there is a cube with 10 unit long and 2 unit width. when the agent is walking along this cube, it must be way at least 2 units away, but if I use a circule, it walks at most 5 units away when it reaches the middle of the cube. I think it would make more problems with rectangular obstacles bigger this assumption.

well I understand that but let me clarify my problem.
suppose there is a cube with 10 unit long and 2 unit width. when the agent is walking along this cube, it must be way at least 2 units away, but if I use a circule, it walks at most 5 units away when it reaches the middle of the cube. I think it would make more problems with rectangular obstacles bigger this assumption.

yes, you don't have to decompose the cube the way i did, that's just generally the simplest solution.

to use your example in a better light, if you take a line from your avoider, to it's destination, and it intesects the barrier, then you need to get two points that create a perpindicular line from the obstacle, so, with the cube, you can fire a ray from the center of the obstacle, towards the perpendicular directions, and take those points as your obstacle radius, this gives you a variable sized circle based on the direction of the avoider, to the obstacle.

but as you can see, we still end up with a circle, regardless of how the object is decomposed, this is why the papers give solutions in terms of circles, the solution generally requires a point of some distance away from the obstacle in order to avoid collision, and since a circle defines such a shape, that's why it's used as the agent which is presented, since it's simple, and easy. it's up to you to select an algorithm which can accurately decompose the object.

if you look up the RVO2 library, and look at the source code, it has an algorithm for decomposing non-circle objects to generate the obstacle cone's.

This circle discussion is odd. If you are shooting rays for detection of objects -- static or dynamic -- then any convex hull that can register a hit will do.

This circle discussion is odd. If you are shooting rays for detection of objects -- static or dynamic -- then any convex hull that can register a hit will do.

Yes I can shoot rays to detect objects but the problem comes after it finds an obstacle. actually I don't have any algorithm to avoid it.

[quote name='zar2012' timestamp='1350209138' post='4990009']
well I understand that but let me clarify my problem.
suppose there is a cube with 10 unit long and 2 unit width. when the agent is walking along this cube, it must be way at least 2 units away, but if I use a circule, it walks at most 5 units away when it reaches the middle of the cube. I think it would make more problems with rectangular obstacles bigger this assumption.

yes, you don't have to decompose the cube the way i did, that's just generally the simplest solution.

to use your example in a better light, if you take a line from your avoider, to it's destination, and it intesects the barrier, then you need to get two points that create a perpindicular line from the obstacle, so, with the cube, you can fire a ray from the center of the obstacle, towards the perpendicular directions, and take those points as your obstacle radius, this gives you a variable sized circle based on the direction of the avoider, to the obstacle.

but as you can see, we still end up with a circle, regardless of how the object is decomposed, this is why the papers give solutions in terms of circles, the solution generally requires a point of some distance away from the obstacle in order to avoid collision, and since a circle defines such a shape, that's why it's used as the agent which is presented, since it's simple, and easy. it's up to you to select an algorithm which can accurately decompose the object.

if you look up the RVO2 library, and look at the source code, it has an algorithm for decomposing non-circle objects to generate the obstacle cone's.
[/quote]

Thank you. I will look at the source code to see what I get.

[quote name='IADaveMark' timestamp='1350236161' post='4990089']
This circle discussion is odd. If you are shooting rays for detection of objects -- static or dynamic -- then any convex hull that can register a hit will do.

Yes I can shoot rays to detect objects but the problem comes after it finds an obstacle. actually I don't have any algorithm to avoid it.
[/quote]

If you graph out the relatively small set of scenarios on paper, it's not hard to figure out what your agent should do. (The answer is turning away from the object until you are parallel to the surface of the object you detected. This takes 2 rays, by the way.)

I got what you said but just a little problem: which way to turn? I mean suppse there is an agent moving straight ahead in the forward direction to reach a target and between them lies an obstacle. now at a certain distance the agent detects the obstacle and decieds to turn away. which way should it turn? right or left?

if you draw a straight line between the avoider's center, and the obstacle's centers, then take the line from the avoider to it's destination, whichever side the line is on relative to the center line, is the side you should turn toward.

if you draw a straight line between the avoider's center, and the obstacle's centers, then take the line from the avoider to it's destination, whichever side the line is on relative to the center line, is the side you should turn toward.

Well that's interesting. I'm going to try it and see what the result will be. thanks.

Shoot random rays in a cone ahead of you. 1 per frame. If it hits, immediately shoot another one straight forward. The orientation of the two points where the two rays hit (if the 2nd one hits at all) gives you a picture of whether the obstacle is angled toward or away from your immediate direction of travel. It also gives you an approximate angle that the object is oriented at. Therefore, you could choose to turn far enough to align parallel to the object (or farther).

Shoot random rays in a cone ahead of you. 1 per frame. If it hits, immediately shoot another one straight forward. The orientation of the two points where the two rays hit (if the 2nd one hits at all) gives you a picture of whether the obstacle is angled toward or away from your immediate direction of travel. It also gives you an approximate angle that the object is oriented at. Therefore, you could choose to turn far enough to align parallel to the object (or farther).

Well I understand all you said except the first sentence. "Shoot random rays in a cone ahead of you". what's "in a cone" supposed to be?

You only need worry about stuff you might run into -- which is in front of you, right? If you send out a ray from center front of your agent with endpoints a certain distance in front of you (based on your current speed is good) with locations that are just a bit wider than you are, you are going to pick up stuff that you are potentially going to run into... not just directly in front, but with your "shoulders" as well.