• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Mohsen Zarsanj

Help with Obstacle Avoidance Behavior

15 posts in this topic

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?
0

Share this post


Link to post
Share on other sites
[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?
[/quote]

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

Share this post


Link to post
Share on other sites
[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?
[/quote]

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

Share this post


Link to post
Share on other sites
[quote name='zar2012' timestamp='1350197179' post='4989991']
[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?
[/quote]

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 Edited by slicer4ever
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
[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.
[/quote]

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
0

Share this post


Link to post
Share on other sites
[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.
[/quote]

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

Share this post


Link to post
Share on other sites
[quote name='slicer4ever' timestamp='1350213114' post='4990014']
[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.
[/quote]

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

Share this post


Link to post
Share on other sites
[quote name='zar2012' timestamp='1350287375' post='4990297']
[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.
[/quote]

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

Share this post


Link to post
Share on other sites
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? Edited by zar2012
0

Share this post


Link to post
Share on other sites
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. Edited by slicer4ever
0

Share this post


Link to post
Share on other sites
[quote name='slicer4ever' timestamp='1350326054' post='4990466']
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.
[/quote]

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

Share this post


Link to post
Share on other sites
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).
0

Share this post


Link to post
Share on other sites
[quote name='IADaveMark' timestamp='1350359156' post='4990601']
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).
[/quote]

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?
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0