Sunday, March 23, 2008

Dynamic Obstacle Avodance Integration

hi, this task wasn't easy, a lot of tiny things that needed to be fix - as i said in my last post :)
but now i'm very pleased with the result, i can drop any number of dynamic obstacles in the scene and the bot/entity will navigate around them.
one very important thing is to make your bot move smoothly and try to take shortcuts when possible, if you wont do it your bot will move around obstacles edges while you can see for sure he can take shortcut, this will make him looks very unnatural and robotic.
here is some screenshots that shows the system in action:
* purple lines shows the from the precomputed ai data the bot aware of, this is convex area so the bot knows he can walk in straight line to any other point in that area.
* small green sphere, goal position the bot need to be at the end
* medium green sphere is the point the bot will move to on the path resulting from dynamic obstacles system, this point is the result of path smoothing. the yellow lines is the path around obstacles without smoothing.
* white boxes is dynamic obstacles (dynamic rigid bodies in debug mode), the green lines around them is the expanding edges of their box.

Simple scene (1 area) this is what the bot aware of

One obstacle added and path generated from the system

Few more added and you can see the new path generated

stress test - start of movement

stress test - middle of movement.
if you watch closely you can see the bot is not moving along the yellow lines and take shortcuts where possible, this can be seen from the bot direction toward medium green sphere.

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