views:

356

answers:

3

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?

A: 

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.

Theran
The problem here is that the cost of moving form node to node is going to be irregular if I base node placement off of the mesh. For example if i make a sphere out of quads the quads at the poles are smaller and closer together than those at the equator, which is bad even from an optimization view.
Tom J Nowell
The problem of irregular spacing is easily solved by making the longer segments more expensive. Uneven quad spacing on spheres is solvable by using a subdivided icosahedron. If you have some really big polygons you will want to add extra nodes so your AIs can cut across the corners.
Theran
how would I generate a subdivided icosahedron?
Tom J Nowell
A: 

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.

Randolpho
indeed there is a bigger picture, but I have other 'pictures' that would benefit from knowing this. I agree most games only have one object to pathfind, aka a rectangular heightmap, but in my case this is not true.
Tom J Nowell
+2  A: 

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

zweiterlinde