Sign in to follow this  

Generate navmesh for heightmapped terrain

This topic is 2831 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Quote:
Original post by all_names_taken
I 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 this post


Link to post
Share on other sites
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by all_names_taken
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?
I could be misreading, but it sounds to me like a constrained Delaunay triangulation would meet your requirements.

Share this post


Link to post
Share on other sites

This topic is 2831 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this