Well, I have the exact same question as described in this 2 year old thread, which never got answered properly. I will try to re-explain it, with a picture: I currently have a triangle Nav Mesh system. Nodes are linked together, and path finding is performed on the graph. Currently, if I have an entity (shown by the brown X), who wants to get to the green point, the path finding algorithm will return the red path. The path finding algorithm is using the centroids of the triangles to determine the minimum distance. The problem is: I need to account for entity radius. I actually want the cyan path to be generated. This is because the radius of the entity (shown in dark blue) is larger than the width of the small corridor. How can I account for this in the searching algorithm? As mentioned in the linked post, it is not as simple as taking the minimum length edge of each triangle and comparing this to the entity radius. This wouldn't work if there was a long, skinny triangle with 1 very small edge, which spanned across a very long distance. Passing through the center of this triangle, I am free from any obstacles, so I should be able to cleanly pass through it. Any ideas on how this could be handled? Thanks a lot.

Thinking about this while I was driving across town, I think it can be solved by looking at the edges passed over. If a traversed edge has a boundary on one side, I need to look at the length of the edge, and compare it to the entity's diameter. I don't foresee any problems with this approach (assuming my nav mesh is constructed properly). It will solve the case presented in my previous post.

If you see any holes in this approach, let me know.

Quote: Original post by Doggan
Thinking about this while I was driving across town, I think it can be solved by looking at the edges passed over. If a traversed edge has a boundary on one side...

There's the danger that part of the entity will pass through the wall on the blocked side (unless you have some local obstacle avoidance system).
Your path would also be smoother if you used the centres of the edges as waypoints rather than the centroids of the triangles, and as you say, your search can discard edges which are shorter that the entity's radius.

Hello Doggan.

It's a tricky issue. You're on the right track, but what you've suggested won't work - I'll hit that in a moment. First, please allow me to recap on the problem for the purpose of clarity.

As you've already discovered, the length of triangle edges do not always correspond to the amount of space the triangle provides for an agent to move through. See this diagram.



In the first figure the edges of the triangle which the circle must pass are clearly longer than the diameter of the circle. Yet it is also quite obvious that the circle would not fit through the tiny gap.

In the second figure I've tried to demonstrate that valid paths through triangles depend not only on where the agent enters a triangle, but also where it exits. Imagine that we begin a search from the agents position and reach the red triangle. Now, it appears that it would be possible to enter the said triangle from the top/left edge and exit from the bottom edge, but it is impossible to enter from the above edge and exit from the top/right edge, despite the fact that both edges are wide enough to accommodate the agent.

The point is that size constraints are not based primarily on a relationship one triangle node an another, but on the way in which we want to move through a triangle node. As such, each triangle needs to store three widths – one for each combination of edges that could serve as the entrance/exit (well, only triangle nodes with three connections really need to store three widths, because triangles with two or one connections can only be transversed in one way). We need to be able to ask the a triangle node “If I have entered from here, and want to exit from here, is there enough space to move through and do that?” The widths can easily be stored in an array in your triangle node structure, where the width of a passage through the triangle corresponds to abs( entry_edge + exit_edge – 3 ).
Thus, when conducting a search and you want to discover whether or not you can legitimately add or modify a neighboring triangle to/on the open list, you take the index of the edge connecting the current triangle node to it's parent and the index of the edge you want to move through to the neighbor, and check whether the corresponding width of your current triangle is larger than your agent.

Determining what those widths are when you compile your navigation mesh is more complicated than you might think. As I've demonstrated in figures 3 and 4, simply looking at the local constraints/edges/conditions of a triangle node is not useful. We need to take into account the features of the mesh beyond the triangle we are examining. Basically, if we want to calculate the width for a triangle (edges: ABC, vertices: abc) for edges A and B which are connected at vertex c, then we need to determine the closest feature of the triangle mesh to c which lies between A and B. If edge C is constrained then this is simply a matter of taking the shortest distance between vertex c and edge C. If unconstrained, then we need to transverse every constrained edge in the triangle mesh (except those that form this triangle), clip it to the region of c, A, B, find the shortest distance between the clipped segment (if it exists) and c, and then take the smallest of all of those distances. This distance should be no larger than the length of A or B (whichever is shorter). (Figures 5 and 6)

The problem now is how you treat the start and end nodes in a search, both of which will only have one entry/exit edge, thus making it difficult to determine width. The start node is easy enough – when you want to add it's neighbors, you simply take the length of the connecting edges as the width. How you treat the end node is up to you, but I am yet to discover a 100% error free way to handle it which also allows me to place my agent's destination within it's radius of a constrained edge.

Also, see the discussion of the issue in this paper, which is probably expressed more concisely than my text in this post.

Hope this helps.
Jackson Allan

[Edited by - jack_1313 on September 23, 2008 7:46:18 PM]

If you're using a predefined node-list you could easily calculate the maximum allowed width between each node. If the path-agent is wider than the allowed width, mark it as invalid and ignore it when searching for a path.

/Robert

Hi,

I solved that problem by adding information to my navigation mesh. I had a few problems like agents navigating too fast around corners and using too small paths.
I added in my navmesh cells a maximum allowed speed and a maximum radius size allowed. When planning the path, the planner ignored all cells which maximum size was inferior to the agent size. When navigating the path, if the agent speed was superior to the allowed speed, its speed was ramped down allowing for smoother turns around sharp corners.

Hope that helps.
Ghostly yours,
Red.

Hello Doggan

For a complete, in-depth discussion of the issue you can see the relevant section of this paper. It's the expanded thesis of the first paper I linked to, and it goes in to a lot more detail. Please note that I have not read the whole thing.

Hope this helps,
Jackson Allan

I haven't had a chance to work on this problem in the past few days, but I will be tackling it again this weekend. Thanks for all of the helpful replies. I will post back later. Thanks again~

Bevel outer (obstacle) edges (in 2d) of navmesh with respect to actor size. Use exact method (see GP gems books) or simplified (like Quake-style brush beveling)
After that, you can treat actor as point and use PoV (Points of Visibility) graph for path finding. This method is very fast for static environment, but require different navmesh instances for each actor size.

[Edited by - Ataman on October 2, 2008 4:34:51 AM]