**0**

# Help with Obstacle Avoidance Behavior

###
#1
Members - Reputation: **137**

Posted 13 October 2012 - 12:25 PM

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?

###
#2
Crossbones+ - Reputation: **4084**

Posted 13 October 2012 - 05:31 PM

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.

###
#3
Members - Reputation: **137**

Posted 14 October 2012 - 12:46 AM

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.

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.

###
#4
Crossbones+ - Reputation: **4084**

Posted 14 October 2012 - 03:24 AM

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.

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.

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

**Edited by slicer4ever, 14 October 2012 - 03:26 AM.**

###
#5
Members - Reputation: **137**

Posted 14 October 2012 - 04:05 AM

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.

###
#6
Crossbones+ - Reputation: **4084**

Posted 14 October 2012 - 05:11 AM

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.

**Edited by slicer4ever, 14 October 2012 - 05:17 AM.**

###
#7
Moderators - Reputation: **2558**

Posted 14 October 2012 - 11:36 AM

**Dave Mark**- President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling

Co-advisor of the GDC AI Summit

Co-founder of the AI Game Programmers Guild

Author of the book, **Behavioral Mathematics for Game AI**

**Blogs I write:**

**IA News**- What's happening at IA |

**IA on AI**- AI news and notes |

**Post-Play'em**- Observations on AI of games I play

*"Reducing the world to mathematical equations!"*

###
#8
Members - Reputation: **137**

Posted 15 October 2012 - 01:49 AM

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.

###
#9
Members - Reputation: **137**

Posted 15 October 2012 - 02:01 AM

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.

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

###
#10
Moderators - Reputation: **2558**

Posted 15 October 2012 - 08:50 AM

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.

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

**Dave Mark**- President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling

Co-advisor of the GDC AI Summit

Co-founder of the AI Game Programmers Guild

Author of the book, **Behavioral Mathematics for Game AI**

**Blogs I write:**

**IA News**- What's happening at IA |

**IA on AI**- AI news and notes |

**Post-Play'em**- Observations on AI of games I play

*"Reducing the world to mathematical equations!"*

###
#11
Members - Reputation: **137**

Posted 15 October 2012 - 11:24 AM

**Edited by zar2012, 15 October 2012 - 11:25 AM.**

###
#12
Crossbones+ - Reputation: **4084**

Posted 15 October 2012 - 12:34 PM

**Edited by slicer4ever, 15 October 2012 - 12:34 PM.**

###
#13
Members - Reputation: **137**

Posted 15 October 2012 - 02:38 PM

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.

###
#14
Moderators - Reputation: **2558**

Posted 15 October 2012 - 09:45 PM

**Dave Mark**- President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling

Co-advisor of the GDC AI Summit

Co-founder of the AI Game Programmers Guild

Author of the book, **Behavioral Mathematics for Game AI**

**Blogs I write:**

**IA News**- What's happening at IA |

**IA on AI**- AI news and notes |

**Post-Play'em**- Observations on AI of games I play

*"Reducing the world to mathematical equations!"*

###
#15
Members - Reputation: **137**

Posted 16 October 2012 - 01:43 AM

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?

###
#16
Moderators - Reputation: **2558**

Posted 16 October 2012 - 08:31 AM

**Dave Mark**- President and Lead Designer of Intrinsic Algorithm LLC

Co-advisor of the GDC AI Summit

Co-founder of the AI Game Programmers Guild

Author of the book, **Behavioral Mathematics for Game AI**

**Blogs I write:**

**IA News**- What's happening at IA |

**IA on AI**- AI news and notes |

**Post-Play'em**- Observations on AI of games I play

*"Reducing the world to mathematical equations!"*