3D pathing finding with flying

How can I enable 3D path finding? Basically something like:

CalculateRoute(input_geometry, start_pos, end_pos, variance)


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.

• I would recommend just implementing A*, A* should work in any euclidean space. Commented Feb 13, 2013 at 17:41
• Isn't A* always shortest path? Is it possible to adapt to have some variance in the path (so it's not always the same + shows some randomness?) Commented Feb 13, 2013 at 17:44
• Commented Feb 13, 2013 at 18:07
• Make sure you're not confusing steering/movement with path finding. As you appear to be by linking the red3d article on steering. Commented Feb 13, 2013 at 18:11
• Do you really need 3D pathing? Most games get by with regular A* and setting the unit's height using steering or other heuristics/needs. Commented Feb 13, 2013 at 20:35

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.

(unfortunately it appears the site I got this image from originally has gone under. They still have a video up on Youtube showing this in action though)

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.

• Using this approach, you can only find some path. You can't find the shortest one, you can't impose any constraints on the trajectory, and you suppose the moving object is a zero-size dot. Graph algorithms only work on finite graphs. Even for the much simpler 2D case, when unit can move freely, another methods are usually better, e.g. check out this lecture that mentions some basic methods: userpage.fu-berlin.de/mtoussai/teaching/10-robotics/… Commented Feb 15, 2013 at 21:13
• @Soonts A* will find the shortest path between nodes, not just "some path". It's dependent on your node size and where you pick your points for how short that path can be. You can make the nodes smaller if you want increased precision. You can absolutely limit the trajectory and simulate unit size by limiting the available node transitions (i.e. no sharp u-turns in nodes, no traversing through tiny nodes). Smoother paths is from optimizations after the fact. However, I don't know of any reasonable way to find a path from point A to point B using trajectories alone. Commented Feb 15, 2013 at 21:35
• see this: const.me/tmp/a-star-fail.png A graph algorithm (thick lines): yellow=3+sqrt(2) = 4.41, orange=1+2* sqrt(2) = 3.83, orange is shorter A geometry-based approach (thin straight lines): green= sqrt(5)+sqrt(2)=3.65, red= sqrt(5)+2=4.24, green is shorter. Commented Feb 15, 2013 at 22:50
• If you think the cells are too large here, I can assure you unless your cells are infinitely small (for which you need infinite RAM and CPU), I can come up with an example of the A* failure that leads to totally different path found (keep in mind not only start and end points are in the continuous 2D space, but obstacles as well). Commented Feb 15, 2013 at 22:51
• @Soonts I'd be interested to learn how you're going to use a purely geometry based approach to 3D path finding, and be more efficient than an A* path. You may be thinking about this too hard. Typically, when path finding we're not that worried about finding the absolute mathematically shortest path. There's a balance you have to find between finding the shortest path, and finding it quickly. You've yet to suggest an alternative to finding a shorter path quicker. See this L4D article about optimizing a A* path: valvesoftware.com/publications/2009/… Commented Feb 15, 2013 at 22:58

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.

Havok AI Demo at GDC 2011

The scene with numerous flying AI's

An inverted view of the navigation volume