3D pathing finding with flying

Does anyone know of a (free or paid) solution that enables 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 to existing solutions.

-
I would recommend just implementing A*, A* should work in any euclidean space. – placeybordeaux Feb 13 '13 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?) – Geesu Feb 13 '13 at 17:44
– Byte56 Feb 13 '13 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. – Byte56 Feb 13 '13 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. – Sean Middleditch Feb 13 '13 at 20:35

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?

-
Flagged. The answer to the question asked by the topic starter - "Unless your scene is trivial, what you're asking is impossible to achieve in realtime game even on a modern quad-core PC". On the screenshots of Havoc demo posted above you can see many tradeoffs for performance: scene is small, instead of using input geometry some intermediate data is used for pathfinding, navigation volume is small and inaccurate so that voxel data completely fits in CPU cache, etc. – Soonts Feb 15 '13 at 7:54
@Soonts I've removed the portion of your post that advertises your services. That's not what this site is about. If you're looking for work, try the gamedev.net job boards. – Byte56 Feb 15 '13 at 23:03
@Byte56, that's fine, I only wonder why didn't you also remove the portion of the original post where the TS asks for the services? :-) – Soonts Feb 15 '13 at 23:13
@Soonts Done :) – Byte56 Feb 15 '13 at 23:15

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

-

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.

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.

-
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/… – Soonts Feb 15 '13 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. – Byte56 Feb 15 '13 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. – Soonts Feb 15 '13 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). – Soonts Feb 15 '13 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/… – Byte56 Feb 15 '13 at 22:58