Hi Harold, I know that people at Utrecht University (The Netherlands) are actively working on the type of problems you describe. Maybe their corridor map method is something for you:
"Current applications require a path planner that is fast (to ensure real-time interaction with the environment) and flexible (to avoid local hazards). In addition, paths need to be natural, i.e. smooth and short. We propose a new framework, the Corridor Map Method, which meets these requirements. " check out some publications here: http://people.cs.uu.nl/roland/index.html good luck, Gerwin On Sat, Mar 28, 2009 at 1:46 PM, Harold Comere <osgfo...@tevs.eu> wrote: > 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 > > > > > > _______________________________________________ > osg-users mailing list > osg-users@lists.openscenegraph.org > http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org > _______________________________________________ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
