New features:
 Polygon Select Mode
 Automatic neighbor calculating
 Path finding preview
 NavMesh 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 memoryefficient way possible IMO.
I also got around to making a fileformat to store the navigationmeshes 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...
RuinedNavigationMeshFormat:
RuinedNavigationMeshFormat:
Offset

Description

Size

0x00

Header "rNavMesh"

8 bytes

0x08

Number of Vertices (v)

2 bytes (ushort)

0x0A

Number of Polygons (p)

2 bytes (ushort)

0x0C

Vertices

12 bytes (float3) * p

0x0C * v * 12

Polygons 
xp vertices ( ushort[] )
yp neighbors ( ushort[] )

Sp = Sp1 + 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
Pathfinding, Initial Polygons 
Pathfinding, Found Path 
Note : Polygons are stored as a single ushort[] in memory, the actual polygon's data is extracted from this array (Yay! bitwize Shifts)
Hi Larry:
ReplyDeleteI 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!
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:
Delete If you store your indices in a counterclockwise order, you can have convex polygons with a finite amount of points.
 Precalculating 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 bitwise 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 raytest 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 raytests.
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.
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)
Delete