[osg-users] 3D accurate pathfinding

Jan Ciger jan.ciger at gmail.com
Sat Mar 28 13:07:58 PDT 2009


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Harold,

Harold Comere wrote:
> Hi jan, gdh
> 
> Thank you for replies.
> 
> I have looked what's path-planning and Corridor map method. But it
> look likes to common path finding algorithms with huge preprocessing
> offline step to build a graph. One problem should be that
> path-planning seems to work good and fast in 2D with "small" areas.
> But i would like to do it in 3D with very large areas and a good
> precision ( because the user might want to go from any point to a
> small component in the satellite for example, so the algorithm have
> to find a path to go to the satellite then to navigate in it to reach
> the component ). With path planning i think there will be too much
> avaible paths referenced, it should take to much memory.

Well, tough - either you pre-process and store the thing in a database
or you do not want to do path planning and use some local search method
instead, however then you are going to have to live with imperfect path
and stupid movement - e.g. agents getting trapped.

However, you were asking about having an exact path before, so I am
afraid that you want to both have your cake and eat it.

> Another problem is that i can not dissociate static and dynamics
> objects. Everything in the scene is potentially moveable. The user
> can decide to open a door, or move anything in the scene, so any
> precomputed graph become erroneous.

That is why you use hierarchical planning and deal with the changes
locally.

> So i dont think that "static", with préprocessing, path-finding /
> path-planning is suitable in my case. Maybe am i wrong, i dunno..

Yes, you are. Please, do look up some material on this first - path
planning is widely published topic. You are "optimizing" and dismissing
 things without having sufficient background knowledge on this. Trust me
here - I had to deal with path planning on a large scale (think a whole
city ...) before.

> Ideally, i want to compute everything i need, only when the "goto"
> function is called. Then it considers actual state of the scene. Then
> we can perform test collision while camera is moving on the found
> path to avoid collision with any dynamic objet wich came after path
> computation.

Sorry, but your "scene" (be it graph or whatever) needs to come from
somewhere. You are asking for global path, for that you need information
about the major part of the scene, if you need optimal path, then whole
scene. So you need some preprocessed data - to calculate that on the fly
is way too expensive. Some kind of local exploration technique has no
chance to give you the data neither - it cannot "see around corners", so
you may never even discover the way towards your target.

Pathplanning for navigation is a very hard task - there have been books
written about these problems. Do not expect a cheap and simple solution
- - there isn't one.

Regards,

Jan

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mandriva - http://enigmail.mozdev.org

iD8DBQFJzoOen11XseNj94gRAiCWAKC7aAx+SWi3F8hUIw5rB9ORIIUakQCeN16z
SpVZ379Jy3Qf0/Qt97fLEy0=
=WAyT
-----END PGP SIGNATURE-----



More information about the osg-users mailing list