Pathfinding on arbitrary non-rectangular bodies

Question

I have various objects whose surfaces are 3D and non rectangular, such as spheres, pyramids, and various other objects represented by meshes. The mesh is not composed of polygons of equal size and distribution across the surface of the object, nor are they all semi/symmetrical objects like the ideal shapes of cylinders, spheres and cones.

Thus how would I go about engineering or retrofitting a pathfinding algorithm that took arbitrary meshes and generated nodes which could wrap around on themselves in any number of ways?

Answer 1

One (likely the simplest) option is to use a grid based search technique---there are some pretty simple ways to generate multiresolution grid decompositions, label cells as "free" or "collision" and search the resulting grid using something like A* (as Theran mentions).

In general, you may need to use more powerful motion planning techniques, such as probabilistic roadmaps (PRMs) or Rapidly-exploring Random Trees (RRTs). There is quite a lot of academic work in these areas.

As an introduction, you may want to check out a survey paper like this one (PDF).

Answer 2

I realize that you're probably not telling us the bigger picture here and are trying to boil your problem down to 3d scene => directed graph => ??? => pathfind, but have you considered approaching this from a different direction?

Is there no way to pre-compose your directed graph? Most games (I assume this is for a game) don't take the full geometry of every object in a scene into account when they build their search paths. Maybe there's another way?

Anyway, you might find this link useful for your research.

Answer 3

A* search should work just fine in this application. It requires a function which does not overestimate the distance between two points, but the straight-line distance will never be an overestimate of the distance along your surfaces.