Implementing Navigation Mesh

I havent come across many online, the book Game Programming Gems 1 has a section on it, and the AI programming wisdom series is bound to have something on it.

http://www.ai-blog.net/archives/000152.html

Is there any paper available online on the actual search in the navmesh (there seems to be plenty on navmesh construction on the other hand)?

An example of a case I can't figure out is when we have an area with several triangles, all being smaller than the player, but together they form a large non-convex polygon that is large enough for a player to pass. Here, it's obviously not acceptable to just automatically create a structure of convex polygons with connectivity info and perform a pure A* or Dijkstra's algorithm for correct results on whether it's possible to walk past that area. Merging triangles into convex polygons is also vulnerable to numerical instability and the order of combining - optimal convex decomposition is NP complete and it's rather upredictable what will happen.

So the path finding algorithm, to be correct, would need to be able to somehow determine that a number of triangles together are enough to allow a player to walk there.

Is this problem handled in professional navmesh path finding solution today, or are simpler methods with more pessimistic approximations of the walkable area used?

A few cases of where this problem would occur:
- the square shaped region of floor in a doorway is wide enough sideways, but not deep enough for a person to stand. If we use a structure of connected convex polys, we'll flag this square as too small (and due to convexity we can't connect this square to the floor of the adjacent rooms).
- a square shaped ventilation shaft making a 90 degree turn. What if our convex combining algorithm links together each of the 2 triangles of the square shaped floor area in the turn of the shaft with one triangle each on the connected shaft tunnels on each side? After doing this, the convexity property would be broken if we tried to combine anything more with either of these 2 polygons constructed, and so the turn may be flagged as impassable even though it's just about passable because neither of two polygons can contain the player alone.
- handling vehicles and different sized creatures
etc

Quote:

Original post by all_names_taken Is there any paper available online on the actual search in the navmesh (there seems to be plenty on navmesh construction on the other hand)?

It is standard, uninteresting graph search. The interesting part is using cheaper graphs: building a navmesh and using one in the first place.

Quote:

An example of a case I can't figure out is when we have an area with several triangles, all being smaller than the player, but together they form a large non-convex polygon that is large enough for a player to pass.

The navmesh consists of salient movement states (position and maybe orientation), not of polygons.

Quote:

Here, it's obviously not acceptable to just automatically create a structure of convex polygons with connectivity info

You don't. Usually, there are two nodes per walkable side of each convex piece of the map.

Quote:

and perform a pure A* or Dijkstra's algorithm for correct results on whether it's possible to walk past that area. Merging triangles into convex polygons is also vulnerable to numerical instability and the order of combining - optimal convex decomposition is NP complete and it's rather upredictable what will happen.

You don't need an optimal decomposition. If you have extra pieces, they only cost you a few unnecessary nodes in the graph; if the graph edges don't correspond to walking through walls the result remains correct.

Quote:

- the square shaped region of floor in a doorway is wide enough sideways, but not deep enough for a person to stand. If we use a structure of connected convex polys, we'll flag this square as too small (and due to convexity we can't connect this square to the floor of the adjacent rooms).

The door EDGES are long enough, as are the projections of one against the other: the agent can stand in a certain interval in the middle of each and slide to the other door edge without turning, provided there are no obstacles outside the door.

Quote:

- handling vehicles and different sized creatures etc

Each would have a different navmesh. What did you expect?

Quote:

Quote: - handling vehicles and different sized creatures etc Each would have a different navmesh. What did you expect?

I may be misinterpreting here, but it's not necessarily the case that you need a different navigation mesh for each object size. (There are ways to use a single navigation mesh while still constructing paths that are tailored to the size of the particular agent in question.)

Quote:

Original post by jyk I may be misinterpreting here, but it's not necessarily the case that you need a different navigation mesh for each object size. (There are ways to use a single navigation mesh while still constructing paths that are tailored to the size of the particular agent in question.)

There are, but they inevitably add complexity: as soon as you have agents with different footprints, the difficulty of determining whether a particular corridor is actually walkable skyrockets, simply by becoming nontrivial. Keeping separate navmeshes for differently sized agents (or, more likely, for a small number of conservative "size" categories) keeps things simple, usually with a pretty small additional memory cost. Of course, in some environments any additional memory cost is dear-bought.

Hi,
Navmeshes have different architectures: they are not always based on triangles or waypoints. The Game Programming Gems series propose a few articles regarding navmesh constitution and navigation(GPG volume 1), and a special case of navmesh and realtime navigation (Jack and Dexter case GPG volume 3).

Still what is never said upfront is that navmeshes are always tailored to your needs. For example, if all your triangles are smaller than your smallest agent, perhaps should you consider redesigning your navmesh. Another example: I have realized a navmesh with tight turns, but my units used to move too fast to correctly turn (resulting in vehicles bumping against the wall). To solve that problem, I added speed limitation to my navmesh so that vehicles slow down to the limitation and avoid crashing on walls in the turn.

Code regarding navmesh storage and use is not that difficult (as a previous poster said, it is uninteresting graph search). The navigation along that navmesh is: you will find out you must tune your navmesh or vehicle navigation code so that navigation is handled gracefully. This means you will rarely find code that allows you to navigate around a navmesh: it will always be tuned to special cases.

Hope that helps.

Ghostly yours,
Red.

Quote:

Original post by LorenzoGatti The navmesh consists of salient movement states (position and maybe orientation), not of polygons.

That sounds more like waypoint based path finding to me. Isn't the purpose of the navmesh that you can have a large walkable area rather than individual states with connectivity information?

Quote:

Each would have a different navmesh. What did you expect?

A common advantage I've seen mentioned with navmesh over waypoint graph is that it can allow different sized creatures with a single structure. These articles (although it was too long ago that I've lost the sources and so can't give references, which may also mean I'm remembering it wrong) seemed to claim the size of the creature could more or less be provided as an argument to the path finding query.

Also if you don't mind could you please explain more thoroughly how the case with the doorway would work? How would the navmesh construction algorithm correctly determine that this little square is walkable, if it's not large enough to contain the player? Wouldn't that require the algorithm to start at some known point where the player can stand, and then use a flood-fill like approach? But using that with boxes as in the article above, unfortunately, is vulnerable to quantization: what if we place our squares aligned in the wrong way. So that in a narrow tunnel which is only just about passable, 5% of the first square intersects the left wall, and 95% of the second square intersects the right wall. Oops, this tunnel is now flagged as impassable even though it's perfectly walkable. Choosing alignment manually won't help if two tunnels are aligned differently, and enforcing a strict alignment to a grid limits the creativity and flexibility of the level designers a lot. Especially if we want a winding tunnel, which naturally will have great difficulties sticking to the proper alignment all the way.

Quote:

There are, but they inevitably add complexity: as soon as you have agents with different footprints, the difficulty of determining whether a particular corridor is actually walkable skyrockets, simply by becoming nontrivial. Keeping separate navmeshes for differently sized agents (or, more likely, for a small number of conservative "size" categories) keeps things simple, usually with a pretty small additional memory cost. Of course, in some environments any additional memory cost is dear-bought.

I can only speak from my own experience, but I use a single navigation mesh for all agents and haven't found the complexities to be insurmountable. Complexity is certainly *added*, but I don't know that it skyrockets.

For someone who is new to pathfinding or to navigation meshes, it would probably be easiest to use multiple navmeshes (although there is still the issue of geometry expansion to contend with).

My own experience though is that using a single navmesh for all agent sizes is a perfectly viable option.

Quote:

Original post by jyk Quote: There are, but they inevitably add complexity: as soon as you have agents with different footprints, the difficulty of determining whether a particular corridor is actually walkable skyrockets, simply by becoming nontrivial. Keeping separate navmeshes for differently sized agents (or, more likely, for a small number of conservative "size" categories) keeps things simple, usually with a pretty small additional memory cost. Of course, in some environments any additional memory cost is dear-bought. I can only speak from my own experience, but I use a single navigation mesh for all agents and haven't found the complexities to be insurmountable. Complexity is certainly *added*, but I don't know that it skyrockets. For someone who is new to pathfinding or to navigation meshes, it would probably be easiest to use multiple navmeshes (although there is still the issue of geometry expansion to contend with). My own experience though is that using a single navmesh for all agent sizes is a perfectly viable option.

Do you know any links or references to where I could read more about how to navigate different sized creatures using a single navmesh?

Quote:

Do you know any links or references to where I could read more about how to navigate different sized creatures using a single navmesh?

The most comprehensive reference I've found on the subject is this paper.

Quote:

Original post by iuliushide http://www.ai-blog.net/archives/000152.html

Very helpful link. ++rating

Quote:

Original post by jyk Quote: Do you know any links or references to where I could read more about how to navigate different sized creatures using a single navmesh? The most comprehensive reference I've found on the subject is this paper.

Thanks, that answers all my questions and more!