Thursday, May 10, 2012

Nav-Mesh Editor Part-3

Okay, making more progress on nav-meshes!
New features:
  • Polygon Select Mode
  • Automatic neighbor calculating
  • Path finding preview
  • Nav-Mesh file format ( *.rnm)
I made some more additions to the editor, mostly to make creating these meshes easier. I had to do all the work associated with making a model editor, except my "polygons" can have up to 15 sides ( expandable to 18). All of the navigation data is stored in the one of  the most memory-efficient way possible IMO.

I also got around to making a file-format to store the navigation-meshes in! I call it "Ruined Navigation Mesh" format - original and ironic I know. These files are also VERY size efficient.
For all of you out there familiar with XNA, I've written my own importer and processor...


Header "rNavMesh"
8 bytes
Number of Vertices (v)
2 bytes (ushort)
Number of Polygons (p)
2 bytes (ushort)
12 bytes (float3) * p
0x0C * v * 12
Polygons -
xp vertices ( ushort[] )
yp neighbors ( ushort[] )
Sp = Sp-1 + 4 + xp + yp

Data stored in memory as a single ushort[]

One of the great things about just reading data directly from the file is that XNA can compress *.rnm files automatically!

So in other words, all that's left to do with this is to actually make the meshes, and program some AI to use them :P

Path-finding, Initial Polygons 
Path-finding, Found Path 

Note : Polygons are stored as a single ushort[] in memory, the actual polygon's data is extracted from this array (Yay! bit-wize Shifts)


  1. Hi Larry:

    I am a newbie game programmer. Recently I start to work on implementing navmesh algorithm. But I have three problems that could not be solved. the first one is how to generate the navmesh programmtically. then how to know which polygon the character is currently in. and the last one is how to calculate the g,h and f in A* algorithm for a navmesh. maybe using funnel algorithm? would u please share some experience? Thx!

    1. I represent the navigation mesh very similarly to how you would represent a 3d model. I have a list of points representing the vertices and a list of "polygons." A polygon keeps track of its indices and its neighbor polygons. A couple of tricks to know are:
      - If you store your indices in a counterclockwise order, you can have convex polygons with a finite amount of points.
      - Pre-calculating neighbors is easy, just find polygons that have two or more of the same indices.

      I went a little crazy with my implementation, and brought the size of each polygon to a minimum, using bit-wise operations to retrieve data from a ushort[] - all my polygons are just really ushort arrays; then I wrote my own file format to store all this data.

      Now once you have your polygons, to figure out which one the player is on, you do a downward ray-test against the polygons.
      Since all polygons are convex, they can be represented by triangles where the first point of the polygon is the first point of each triangle. There are several little optimizations you can do to decrease the number of ray-tests.

      Next, when using A*, you can use the distance between polygons to figure out the estimated cost. Then just keep track of the total cost for each movement, finding the path with the lowest total movement cost.

    2. Thanks a lot Larry. I will start try implementing the method since this weekend. Maybe in the beginning I will just make a simple editor to draw the navmesh rather than generating them programmatically. (voxelization and triangulation drives me a little bit a crazy)