Hello I want to implement pathfinding with a navigation mesh but haven't been able to find much information on the details of implementation, must of what I've found is with regards to the theory. Are there any articles/resources on the subject? Thanks.

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:

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.

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.