|
Does anyone know of a (free or paid) solution that enables 3D path finding? Basically something like: I found a good paper on the topic, but I haven't found any solutions via Google or even searching sites like odesk, etc... I know recast/detour is great for ground navigation, but I can't find anything that involves flying/3D space. Any suggestions would be great to existing solutions. |
|||||||||||||||
|
|
A* is the go to for most path finding situations. It's no different with 3D spaces, including flying through the air. Basically, you'll break your game up into nodes. This is called the navigation mesh. These nodes are typically cubes of various sizes. They don't all have to be the same size, you can make large open areas one big cube and the open areas near terrain smaller to have finer precision.
Implement A* to use these nodes for path finding. A* is nice because the node cost can be tailored specifically to your game. You can also give multiple nodes the same cost and randomly choose between them to have variances in flight paths. Once you've found the path, now is when you're going to use the red3d link to implement steering. You'll steer towards each node in your path, until you're "close enough", then start steering to the next node. This will give a smooth flight path between a linear node to node path. This solution is completely free, since you're implementing it yourself. However, I will accept payment for providing the details if you're so inclined. |
|||||||||||
|
|
The equivalent to Navigation Meshes for 3D spaces is Navigation Volumes. Havok AI implements both navigation volumes and a volume pathfinder as shown in their GDC 2011 demonstration. The principle of A* in a volume is the same as A* on a navigation mesh. Since A* will find a path over any graph it doesn't matter if the graph is represented by a point to multiple points, a polygon to multiple polygons, or a volume to multiple volumes. The algorithm will still find a solution if one exists. Some slight nuances that are different with paths found on navigation meshes is how you determine path points at the edge of line segments, at the ends, or maybe at the middle? The same can be true of of navigation volumes, to determine the cost to traverse to the next volume you'll typically have to pick a point within the volume, midpoint/edge/etc. This all essentially boils down to the heuristic part of the A* algorithm you must supply yourself, or use a basic Euclidean distance algorithm. Path Following is not Pathfinding How your AI determines to follow this path is something completely different and is referred to as Path Following. The typical strategy for Path Following is to allow your AI to look ahead of where it's traveling to see if it can short cut the path to make more natural curved movements.
|
||||
|
|
|
There's a lot of information missing from your question. Do you need to find the shortest path? Or all shortest paths (may be infinite)? Or any reasonably optimal path (what criteria)? Or all topologically different paths (always a finite number)? What constraints do you have on the trajectory? For example, no object that has non-zero mass is able to follow an angled path, unless completely stopped at the angle tip. Is the moving object a point, sphere, or more complex object? How's your geometry represented? If it's polygon meshes - is the topology good? (e.g. narrow holes between faces of the mesh are usually completely invisible when rendered, but affect some solid geometry algorithms). How large is your geometry? (both in meters/km and triangles count) How often does it change? What's the CPU and RAM budget for the pathfinding? |
|||||||||||||
|
(unfortunately it appears the site I got this image from originally has gone under. They still have 
