Hi to all, Any one know how to implement a A* algorithm using NavMesh.I had implement the A* Algorithm using Tile based.Its very interesting about articles i read about Navigation Mesh.Some one point me the direction where i can get details about implementation of A* using Navigation Mesh(psuedocode).Thanks in advance ----Rajesh---

One solution is to use the center point of one triangle to the center point of an adjacent as the distance. That + connectivity information is all you really need, plug it into A* and it will find you the shortest route.

Well... almost, if you have very long thin triangles your center points could be badly offset and the distance between center points becomes a bad approximation of the straight line distance. (Think of a vertical triangle strip which is very wide but with very little height to each triangle)

IIRC what I've done in the past to negate this effect is to use the distance between midpoint on one edge and midpoint on another.

Hope this helps,
Cheers,
Martin

The usual approach is to build a rough path (using either triangle centers or edge midpoints, as Martin indicated) and then apply some sort of 'path smoothing' algorithm to make the path more natural.

There are various ways to approach each of these steps. This has actually been discussed here quit a bit in the last few months, so if you search the forum archives for (e.g.) 'navmesh pathfinding', 'string pulling', 'funnel algorithm', etc., you should find quite a few threads (some of which will contain links to articles, papers, etc.).

Actually i used Mahattan Method to calculate H cost before .But how can i do it for traingles or cubes or polygon's.





----Rajesh----

Euclidean distance will be guaranteed to be an underestimate (and so an admissible heuristic).