# Generate navmesh for heightmapped terrain

## Recommended Posts

Seeing as heightmaps are a special case of a general polygon soup level, are there any faster and/or simpler navmesh generation algorithms for it? I know of the voxel based navmesh generation algorithm (how does it detect if a surface has a too steep slope btw), but would it be faster to use the terrain triangles/quads as a starting point and use a heuristic to merge them together to form a navmesh? I remember that the navmesh by definition needs to be a Delaunay triangulation of the walkable area (or A* through it won't work properly for several rather common special cases). Are there any heuristics that will form a Delaunay triangulation that could be used for this? Or should I stick with the voxel based approach? Fast generation is somewhat important since the terrain will be calculated at runtime.

##### Share on other sites
Emergent    982
Quote:
 Original post by all_names_takenI remember that the navmesh by definition needs to be a Delaunay triangulation of the walkable area[...]

Not as far as I know. Generally a navmesh can't have t-junctions, but it doesn't have to be a Delaunay triangulation. That said, a Delaunay triangulation is a particular kind of triangulation that happens not to have any t-junctions.

A heightmap does have the "no t-junctions" property, so you should be good there. As a first step, think about when you can walk from one triangle to another. They need to share an edge (in which case the corresponding nodes in the navmesh will be connected), and the angle between then needs to be less than a certain number. To determine this last part, all you need to do is look at the dot product of their normals... [EDIT: Or, alternatively (and probably better), a triangle is simply walkable IFF the up component of its unit normal is greater than a threshold.]

In principle, you could merge triangles to form larger polygons now, etc. I'm personally not familiar with any "standard" ways to do this (a number of ways come to mind), but it seems like a perfectly reasonable thing to be doing.

[Edited by - Emergent on March 16, 2010 8:15:57 AM]

##### Share on other sites
Schrompf    1035
I don't see why you don't just navigate on the height map directly. You have regular tiles for which you can determine the walkability very quickly. You could A* on them without any preprocessing. Or maybe set a flag "walkable" on each tile which also accounts for trees, walls and other obstacles - a quick way to automatically navigate around obstacles, too.

Maybe you worry about the node count that this approach causes. In that case you could also join 2x2 tiles recursivly if all 4 are walkable. This creates T junctions at first, but those could be removed by subdividing the neighbouring edges in a second pass. This should be doable very quickly because the regular tile structure of a heightmap spares you from expensive neighbour searches.

##### Share on other sites
Edit: ok it turns out they don't need to be Delaunay. The triangulation however needs to be such that its triangles do not contain points which do not lie on some edge between the walkable and unwalkable area of the map. Moreover, all endpoints on such edges need to be included in some triangle in the triangulation.

If the first condition doesn't hold, characters larger than the size of the heightmap quads won't be able to path find at all.

What heuristics could be used to get this guarantee for sure, and as close to Delaunay quality as possible so as to minimize the navmesh number of nodes?

##### Share on other sites
jyk    2094
Quote:
 Original post by all_names_takenEdit: ok it turns out they don't need to be Delaunay. The triangulation however needs to be such that its triangles do not contain points which do not lie on some edge between the walkable and unwalkable area of the map. Moreover, all endpoints on such edges need to be included in some triangle in the triangulation.If the first condition doesn't hold, characters larger than the size of the heightmap quads won't be able to path find at all.What heuristics could be used to get this guarantee for sure, and as close to Delaunay quality as possible so as to minimize the navmesh number of nodes?
I could be misreading, but it sounds to me like a constrained Delaunay triangulation would meet your requirements.