Monday, March 3, 2008

Dynamic Obstacle Avoidance

Hi, after setting up some basics in my physics engine i realize that my AI system isn't aware of any dynamic object created from the physics engine so i started to think about some generic solution to solve the problem of dynamic avoidance.
until now, i had some basic dynamic obstacle avoidance inside my steering system that check against obstacles on the way and if it found some, it add avoidance forces so the agent while try to steer around the obstacle (works fine for the bots)
the main advantage of this system is that its very simple to implement and it very fast, the disadvantage is that it tries to steer around one obstacle at a time, so if you have few obstacles one after another, it will steer around the first and return, steer around the second and return and so on (does not look very smart), also it doesn't handle the case where few obstacles block our path, it doesn't find a path that goes a around them (if exists) it just tries to steer around the first on the way but end up bumping against them until they moved (and if they wont move you are stuck)
this is unacceptable when you can have a lot of dynamic objects that moves around and could block our path, so i started to build some generic solution to this problem.
the main idea is that i trace a line from my current position to my current goal position (path line), and any obstacle that founded in my way, added to a list of obstacles.
then i check this list against my path line and build "edges graph"/"path tree" from the bounding edges of intersected obstacles and my path line fractions.
this tree is just a graph containing all the combination paths from my current position to my current goal, so then i found the shortest path in the graph and save it as a local path around the obstacles.
of course this is just a brief of the algorithm, there is a lot of tiny things that you need to consider when creating the graph, and also how you can optimize it so you have only few edges to run the shortest path algorithm on.
after i finish the algorithm i had time only to test it against rigid bodies that i throw inside the scene and it really perform well (still need to add few things here and there), i didn't had time to integrate it into my AI system :(
no pictures/movies maybe next time...
BTW: i today i got game programming gems 7, so i have a lot of things to dig into :)

1 comment:

Mario said...

Hello, realy cool work! I am working on similar engine, so I have some questions. Could I contact you anyway? My icq is 164941164, email kexik at Thank you and keep doing this nice work!