[General] NavMesh Creation and Pathfinding

**streppel** · 12-17-2011

Hello all,

so i had some trouble myself to get some decent navigation in my bot, so i decided to release my Mapper and the Navigation Class i use.
The Navigation Part itself is completely based on C#: A-Star is born - CodeProject® , where i did only change the Arcs and Nodes attribute of the Graph class to be a List<T> instead an ArrayList to allow parallel processing.

The class will create a Point-Based Nav-Mesh,meaning that it will try to add the points you pass to it to a list of points, if there are no others in the specified range.
after creating this file(NodeList file),you can create a mapfile(basically just a Graph-object that is serialized to a file).
there also is a demo included aswell as the source of the navigation library i used.

If you have any suggestions,please let me know.
And ofc i know,there is recast and detour,but even tho it's a general approach on getting a decent navigation, there are situations,where you don't have the map files(at least not as easily as in wow), or for a small project where you just want some navigation that is better than waypoints,more flexible etc,but wouldn't want to write a wrapper for recast+detour or whatever reason there might be.
For me the first one was the case and this was my solution to get around it and still have a good navigation

Streppel

PS:
Virus Total Scan ofc, and if you still don't trust me,take the source and compile it yourself
VirusTotal - Free Online Virus, Malware and URL Scanner

Edit:
Ok here are 2 Pictures to show you how the process works in general
the points all have the same distance to the next one. as you run with your char ingame and pass those points to the class, it will add them(the red dot would be your char ofc)

[General] NavMesh Creation and Pathfinding-navmesh-mapping-gif

Now as you are done mapping,the CreateMapFromNodeFile method will connect all nodes around the current node in the nodes list, that are within the specified range. as distance in R³ is sqrt((x0-x1)²+(y0-y1)²+(z0-z1)²), and the distance when mapping was 2 yards(default values here,you can use your own of course) the distance would be sqrt(2²+2²+2²),what is equal to 3*sqrt(2),what i rounded to 3.5 just for lazyness reasons.
wo the method will look for available nodes in a distance of 3.5 yards and,if there is one,connect them both.