Jump to content

  • Log In with Google      Sign In   
  • Create Account


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


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 jack_1313   Members   -  Reputation: 536

Like
0Likes
Like

Posted 18 April 2013 - 12:40 PM

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, 18 April 2013 - 12:53 PM.


Sponsor:

#2 Vilem Otte   Crossbones+   -  Reputation: 1343

Like
0Likes
Like

Posted 23 April 2013 - 03:34 PM

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


My current blog on programming, linux and stuff - http://gameprogrammerdiary.blogspot.com


#3 tedsta   Members   -  Reputation: 258

Like
0Likes
Like

Posted 23 April 2013 - 05:39 PM

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, 23 April 2013 - 05:40 PM.

Current Project

World Storm

 

out our Android app! (My roommate and I)

https://play.google.com/store/apps/details?id=com.drsupersocks.ninja


#4 DrEvil   Members   -  Reputation: 1079

Like
0Likes
Like

Posted 05 May 2013 - 07:58 PM

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/



#5 DrEvil   Members   -  Reputation: 1079

Like
0Likes
Like

Posted 06 May 2013 - 06:32 PM

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.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS