Hi Gamedev.net!

Years ago, I was an active member here and a very enthusiastic game programmer. For the better or worse, life took me in a different direction. I turned away from game programming and have spent the last so-many years studying history and foreign language.

It occurred to me that I have, sitting idle on my hard disc, a fast and robust navigation mesh / path finding implementation based loosely on the Douglas Demyen Triangle-Reduced A* thesis (of which seems to have disappeared from the internet – only the shorter journal article is now available). It was part of a game I was working on years ago, was rewritten from scratch on at least one occasion. Rather than let that work go to waste, I thought I might turn it into a stand-alone C++ library that would be free for non-commercial use.

Features:
* Automated construction of navigation mesh (uses Triangle triangulation library).
* Speed. The implementation is fast, primarily, because only triangles with three neighbours (“keynodes”) are included in the A* search. All other triangles are collapsed into “corridors” and skipped over. In most environments, keynodes account for 1/4 to 1/3 of all triangles in the navigation mesh.
* A single navigation mesh is used to find paths for agents of any size – no need for duplicate navigation meshes.
* It’s paired with a kd-tree system that has some bonus features that could be useful (very fast visibility + swept circle checks against navigation mesh etc).

Shortcomings:
* It’s simple-2D only – does not support overlapping areas or varying-cost terrain types, though the former could probably be implemented without a huge effort.
* The navigation mesh cannot be dynamically updated.
* I doubt I would be able to spend a lot of time developing it further.

Here’s a few screenshots of the implementation finding some very long paths. Time estimates were recorded on my laptop – an Intel i5-2450 2.50GHz processor – in a standard Windows 7 environment, and are the average of 10 000 queries.

Search time: 0.041ms and 0.036ms. Navmesh: 772 triangles, 255 of which are keynodes (pink).

Search time: 0.039ms and 0.025ms. Navmesh: 820 triangles, 251 of which are keynodes.

Search time: 0.069ms and 0.056ms. Navmesh: 1213 triangles, 366 of which are keynodes.

Varying agent sizes pose no problem. Search time for each path: in the range of 0.006ms.

It looks like the need for such a library has lessened due to the appearance of Detour, which didn’t exist when I developed it. In short, I’m just wondering if there would be any interest in this project? I can only really justify putting time into it if it looks like there might be some interest/communal benefit.

Thanks for reading!

In my opinion it's always better when you can pick from more softwares, Detour has also it's disadvantages (and there is a lot of people that won't use it).

I think it's definitely worth it to release it, go for it. And as you probably have wide knowledge in navmesh construction & path-finding, it might be worthy to explain these a little in an article (even though there is a lot of info how to perform path-finding through navmesh, there isn't too much info on construction (+ how to store navmesh data, and how to use it during path-finding)).

Very cool, I would be interested! I had have a path-finding system set up in my game engine, but level designers have to add the waypoints manually. This would definitely be useful to me

Oddly enough I just posted a question asking about something you appear to have tackled, and that is, how are you compensating for the agent radius in the path building since you don't appear to be building the mesh with the agent radius?

As asked here http://www.gamedev.net/topic/642747-navmesh-without-agent-radius-offsets/

Btw, to answer your original question I think there is definitely a spot for this library in the mix, specifically because of the entity size agnostic functionality.