• Advertisement
Sign in to follow this  

Interest in a (TR)A* Navigation mesh / Pathfinding Library?

This topic is 1721 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

 

pathfind1.png

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

 

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

 

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

 

pathfind4.png
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!

Edited by jack_1313

Share this post


Link to post
Share on other sites
Advertisement

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)).

Share this post


Link to post
Share on other sites

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 biggrin.png

Edited by DrSuperSocks

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement