[osg-users] 3D accurate pathfinding

Harold Comere osgforum at tevs.eu
Sat Mar 28 05:46:53 PDT 2009


Hi all,

First, my english is not fluent, so i apologize for all mistakes i will do and hope i will success to explain my problem :)

Well, i'm currently working on a project where i have to implement any kind of efficient real time pathfinding in osg scene.
The goal is to go from a space point to another one ( or to an osg node but it is similar ) avoiding collisions and detecting when there is not path to go there.

The real problem is that :
1) Algorithm must work for static scene but could be extended easily to dynamic scenes.

2) Algorithm must work in some specific kind of situation :
- In space, huge empty areas and some complex "small" objects as satellite.
- In pipe network. It means able to pass through pipes if needed.
- In a factory, lot of rooms ( and why not pipes :p )

3) The algorithm must return a path, or nothing if no path found, then the camera will follow the path, that to have to do computations once.

Well, i worked on it for about 2 weeks now and i didnt found any efficient way to do it.

Static / Dynamic constraint prevents preprocessing that build any kind of graph to use common path finding algorithm ( as A* and other ).
For a dynamic scene a way to use pathfinding algorithms could be to build the pathfinding graph each time the "goto" function is called. But to get an accurate path finding detection, we have to consider the whole scene ( specially in factory case ), that is pretty hard to do it in interactive time.

Pipes network constraint prevents of working with bounding volumes ( bounding sphere, AABB, OBB, convex hull ). I didnt succeed to find a way to build hierarchical space subdivision that could help greatly with geometry collision detection.

A simple way to solve my issue could be ray tracing collision detection. But this dont guarantee to find a good path, and it make hard to detect there is not path... And after some tests, using the osg::LineSegmentIntersector take about 5 ms on my scene, so i use only 200 rays to find a path it already cost 1s that's to much for real time application needs.
Maybe by specifing to the IntersectionVisitor only the node where is the camera, could be reduce computing times, but i dont think that's a suitable solution..

Well, i'm a bit stuck and lack of ideas for now ...
I have began to use osg 2 weeks ago, so maybe is there any kind of osg cool stuff wich could be usefull to do it that i ignore ?

Thanks for your attention :)

Regards,
Harold

------------------
Read this topic online here:
http://forum.openscenegraph.org/viewtopic.php?p=9392#9392








More information about the osg-users mailing list