I am reading up and am interested in using mesh navigation graphs for path finding. Given that each mesh represents a node on the navigation graph, what are the edges of the mesh navigation graph? Also, how are the edge costs of the mesh navigation graph computed? The diagrams I have seen show the meshes lying adjacent to one another with no edges, unlike the waypoint navigation graph.

It depends on the type of navigation mesh you're implementing (navmesh is such a vague term really). For instance, in TRA* the edges represent the sides of the triangles covering the floor.

In other implementations you could create a node to represent (the centre of) each polygon and add an edge between the nodes of adjacent polygons. The weights of the edges are then the distances between the centroids. Check out Paul Tozour's article on fixing pathfinding once and for all; there are some nice references at the end.

The edge of the navigation mesh cost values are based on the distances to the adjacent node multiplied by the unit difficutly of the terrain being passed thru. It is a summary/approximation of the cost of getting near the nodes 'point' which is usually central to a triangular facet (or grouping of facets)

Many time the Nav mesh is a simplification of the 2D/3D mesh representation used by the graphics display so the simpler Nav mesh is a averaged composit (and maybe a max limiting component if some part of the finer detail would limit movement).

The type of terrain may also be used to limit different kinds of movement (like water versus land) and may even require seperate Nav meshes to handle cases where they overlap.

The slope of the surface versus actual direction of movement may also be utilized (including down a steep cliff being allowed versus up...)
Which the pathfinder may have to take into account (bi-directional edges - different costs for each edge direction)

thanks for the helpful replies :)

For constructing a mesh nav graph representing a room, could I do it using the following way?

- Ask the artist to create meshes representing the walkable areas in the room

- Each mesh represents a graph node and an edge is represented by a straight line between the centre point of 2 adjacent meshes

- Perform A* or dijkstra on the resulting graph

Quote: Original post by Weng
thanks for the helpful replies :)

For constructing a mesh nav graph representing a room, could I do it using the following way?

- Ask the artist to create meshes representing the walkable areas in the room

- Each mesh represents a graph node and an edge is represented by a straight line between the centre point of 2 adjacent meshes

- Perform A* or dijkstra on the resulting graph

That'll be a huge time sink for your artists. You should write code that creates the navmesh from the scene's geometry, and then have the artists tweak it if necessary.

-- Mathieu

I forget if we had stuff on this forum about automatic portal calculation (its probably in the Game programming Gems Books or Game AI books)

Finding 'rooms' -- areas where you can move inside/within the area in a straight line and then identifies the 'portals' which are the interface points/segments between rooms. The whole map is broken up into those areas (some very small)

Those points become nodes for the pathfinding and edges are the straight lines between the portals. Within the room (locally) the path is fairly simple.

Hierarchical Pathfinding might be a keyword that leads to various ways to analyze
the map programatically to build the portal data from the 3D graphical meshes.

A program might be able to do a majority of the map (build the nav mesh) and then allow a human to intervene and custom define the complicated map situations.

Quote: Original post by wodinoneeye
Finding 'rooms' -- areas where you can move inside/within the area in a straight line and then identifies the 'portals' which are the interface points/segments between rooms. The whole map is broken up into those areas (some very small)
...
A program might be able to do a majority of the map (build the nav mesh) and then allow a human to intervene and custom define the complicated map situations.

A navigation mesh is already such an abstraction. In my experience, there's little to gain from having multiple abstraction levels (most of the speedup comes from the first level).