GameDev.net Posting Guidelines (please read before posting)
Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
Posted 13 October 2012 - 12:25 PM
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?
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.
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.
Edited by slicer4ever, 14 October 2012 - 03:26 AM.
Posted 14 October 2012 - 04:05 AM
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.
Edited by slicer4ever, 14 October 2012 - 05:17 AM.
Posted 14 October 2012 - 11:36 AM
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
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.
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.
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.
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
Posted 15 October 2012 - 11:24 AM
Edited by zar2012, 15 October 2012 - 11:25 AM.
Posted 15 October 2012 - 12:34 PM
Edited by slicer4ever, 15 October 2012 - 12:34 PM.
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.
Posted 15 October 2012 - 09:45 PM
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
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).
Posted 16 October 2012 - 08:31 AM
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
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
GameDev.net™, the GameDev.net logo, and GDNet™ are trademarks of GameDev.net, LLC.