Sign in to follow this  
all_names_taken

Which Navmesh navigation library to choose?

Recommended Posts

Anyone know of a good LGPL, MIT or public domain licensed path finding library for performing path finding on navmeshes? I'd like it to have the following features (ranked from most important to least important): - (necessary) performing path finding for actors of varying sizes, using the same navmesh. - (necessary) find closest navmesh node given a position - (necessary) uses y as the "up" axis - (good to have) support for dynamically re-weighting nodes when dynamic obstacle objects appear, or other team mates go there, in order to avoid congestion - (good to have) perform string pulling, the extended funnel algorithm or similar to improve paths compared to the naive path that goes through the middle of each triangle found by A* (or whichever search algorithm is used by the API) - (good to have) support for adding special teleportation nodes/edges with associated user-decided cost. These can be used to implement e.g. teleportation, elevators, jumping and so on by attaching user defined behavior nodes to them (just need these nodes to be stored in the navigation API to ensure the path computation considers these paths and compares them fairly to alternative paths) - (good to have) debug drawing the navmesh (and maybe also a path) with OpenGL - (not needed at all) distance-based weights for path cost computation may be highly approximate (e.g. use the distance required when going through the midpoint of each triangle), there's no need for fancy cost-correction algorithms for navmeshes with complicated shaping

Share this post


Link to post
Share on other sites
Hi,

Did you look at the game programming Gems book series ?

One comes with a simple Navmesh navigation code (GPG 1), the other comes with an interesting explanation of NavMesh navigation for Jak & Dexter (GPG 3). Implementing the latter by yourself is not that difficult. Of course, it works for continuous worlds with bounds (indoor scenes or outdoor scenes with impassable terrain).

The problem with navmeshes is that they always are tailored to a specific game: there are no jack of all trades. When looking after navmeshes, I quickly found out it was easier to develop and debug a specific navmesh tailored to my game instead of looking for a navmesh library:

- It is simpler to develop for a specific game (indoor/outdoor navmeshes have their own difficulties, tiled / continuous worlds have their own difficulties, ...)

- I have control on my navmesh representation (area based or point based navmesh, generation based on underlying world mesh)

- I have control on my navmesh tuning (I had some agents with velocity troubles which were crashing in tight turns, I added navmesh max speed information to solve this problem for these agents).

Now, if you still are looking for a library, you could look at Recast and Detour at http://code.google.com/p/recastnavigation/. It works for continuous worlds with bounds (indoor scenes or outdoor scenes with impassable terrain) and provides a tool to compute a navmesh from any geometry level.

Hope that helps.

Ghostly yours,
Red.

Share this post


Link to post
Share on other sites
Heh, your title makes it sound like there are multiple choices of libraries when in fact there's probably only one that people use (Recast / Detour). However, this library uses one navigation mesh per actor configuration, so it doesn't fit your requirements.

You may have to roll your own or modify that existing code heavily.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this