Once I had my nav mesh generator down, I plugged in Mikko Mononen's Stupid Simple Funnel algorithm code just to see how well it copes with my input. It didn't take long before I started coming across more and more situations where it fails miserably.

The algorithm is not complicated on paper and I don't think I'm misreading it either, but at least his implementation (and description) of it seems inherently broken. Consider the following example, which utterly fails to produce a valid path, because none of the consecutive portals cause the edges to cross at any point, making it seem as though the direct path is always passing through the middle of each portal.

[attachment=28070:funnelfailpost.png]

Nav mesh nodes are not shown here, but a) yellow lines denote portals, b) the red notched chain is the path,

c) the green circle is the start and the yellow is the goal, while d) the green line is the funneled path, which clearly cuts

through solid. Following the algorithm along the portals it's pretty clear why - the left and right vectors never cross,

even though the path takes a pretty harsh turn. The blue lines are the nav mesh outline. Note that parts of the wall have

been intentionally filtered (those not surrounded by blue lines) and are not part of the nav mesh to start with.

In short, before I dive headlong into Demyen's thesis and spend time on implementing it myself, does the deque version described therein avoid such situations? Because it seems to me based purely on the description of the algorithm itself that it needn't necessarily cope any better. Which in turn raises the question - what's all the fuss with the funnel algorithm?

As a sidenote - if you scroll all the way down, a poster actually calls Mononen out on this, but he fails to reply to that particular comment.

PS - reading around on the net seems to suggest that shrinking the nav mesh for each agent size is the simplest way to go, but Demyen and this guy seem to try it the harder way. Does anyone have a comment on what the performance impact is like in practice?

I myself have implemented Mikko's funnel algorithm and it works just fine in my version (albeit, my nav mesh is restricted to quads which may not be aligned). Your description of the "failure case" in the example isn't correct. I don't recall the exact details of the algorithm, but you are basically setting an apex and then walking the left and right sides to succeeding portals until the left or right cross the other.

When the left/right crosses you've found a new apex point which needs to be a part of the path.

Are you sure you understand or have implemented the algorithm correctly? Mikko's algorithm simply backtracks a few points to avoid having to use the deque at all which is an annoying data structure to have to use for something so simple.

Edit:

Sorry didn't catch your description under the image since clicking the image just blows it up and I never saw the text under it. It's not enough to go off of to know if you understand the algorithm fully, but the left and right legs definitely do cross in this example.

Check out 2.2.4 Funnel in this document if you want another description http://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/shortest-homotopic-paths.pdf

I myself have implemented Mikko's funnel algorithm and it works just fine in my version (albeit, my nav mesh is restricted to quads which may not be aligned). Your description of the "failure case" in the example isn't correct. I don't recall the exact details of the algorithm, but you are basically setting an apex and then walking the left and right sides to succeeding portals until the left or right cross the other.

When the left/right crosses you've found a new apex point which needs to be a part of the path.

Off the top of my head I it seems that quads are guaranteed to generate a valid funnel due to their inherently regular topology. In the case I presented above, just take a piece of paper and follow the left and right edges from the initial apex and you'll notice that due to the elongated shape of the triangles the left and right edges never cross and therefore never generate a new apex before the goal is reached. Unless I'm reading it totally wrong, the algorithm simply can't cope with input like this, which is why I started the topic in the first place.

Could you please try and elaborate on where my description fails? I'd much rather this is a fault on my part than that the algorithm is inherently flawed :).

I myself have implemented Mikko's funnel algorithm and it works just fine in my version (albeit, my nav mesh is restricted to quads which may not be aligned). Your description of the "failure case" in the example isn't correct. I don't recall the exact details of the algorithm, but you are basically setting an apex and then walking the left and right sides to succeeding portals until the left or right cross the other.

When the left/right crosses you've found a new apex point which needs to be a part of the path.

Off the top of my head I it seems that quads are guaranteed to generate a valid funnel due to their inherently regular topology. In the case I presented above, just take a piece of paper and follow the left and right edges from the initial apex and you'll notice that due to the elongated shape of the triangles the left and right edges never cross and therefore never generate a new apex before the goal is reached. Unless I'm reading it totally wrong, the algorithm simply can't cope with input like this, which is why I started the topic in the first place.

Could you please try and elaborate on where my description fails? I'd much rather this is a fault on my part than that the algorithm is inherently flawed .

I'm not sure how the topology works out here to guarantee a funnel? Maybe we are misunderstanding:

The squares are all nav mesh nodes and there are tiny red and blue markings which indicate the endpoints and midpoints of portals.

I will try to remind myself of the exact details of the algorithm and do a step by step sample through your case (Maybe I'm wrong! But I'm fairly certain your case is not a failure... but I should probably check, shouldn't I?).

Ah ha! Yes, I worked through your example and I think what you were referring to is when you get to this case:

And it had me stumped for a second until I remembered that you need to treat the destination point as a final portal to process. It's not obvious in Mikko's explanation and in most other explanations, but it's mentioned in Jeff Erickson's description of the funnel algorithm:

2.2.5 Conclusion

When the funnel has reached the last edge in X ? , we compute the shortest path from ?(0) to ?(1) in the sleeve by treating ?(1) as a triangle vertex and extending the funnel one last time. Thus, assuming the polygon is already triangulated, the overall time to compute the shortest path is O(x + x ? ) = O(x) = O(nk).

In my own code, I create dummy portals for the start and end positions where the left and right endpoints of the portals are the same as the positions themselves. This should fall into place nicely with the rest of the algorithm as long as your cross product comparisons are using >= or <= (not the strictly < or >).

I hope this helps!

PS - reading around on the net seems to suggest that shrinking the nav mesh for each agent size is the simplest way to go, but Demyen and this guy seem to try it the harder way. Does anyone have a comment on what the performance impact is like in practice?

I tried to implement Demyen's approach but I gave up after trying for a really long time to get all the details just right. Although I haven't tried it myself, I suspect that shrinking the nav mesh would indeed be a much simpler approach, and if you can afford it, it might be best to have a few different nav meshes tuned for particular sizes.

As for the other person (http://www.koffeebird.com/2014/05/towards-modified-simple-stupid-funnel.html), I do exactly this approach on my game and if you can operate under the same assumptions, namely that the portals you have are guaranteed for the agent of radius R, it works great (at least I think so)! Performance is absolutely a non-issue for me. On very long paths, my entire string pulling + tangent to circle computation takes on the order of ~50000 cycles which is around 0.02 ms on my machine. The A* search takes far, far longer. The A* search alone to generate that path could take me 0.25 to 0.5 ms.

You have far bigger problems to worry about when it comes to performance in pathfinding. The A* search (if you're using it) will be the lion's share of the time spent.

Ah ha! Yes, I worked through your example and I think what you were referring to is when you get to this case:

And it had me stumped for a second until I remembered that you need to treat the destination point as a final portal to process. It's not obvious in Mikko's explanation and in most other explanations, but it's mentioned in Jeff Erickson's description of the funnel algorithm:

2.2.5 Conclusion

When the funnel has reached the last edge in X ? , we compute the shortest path from ?(0) to ?(1) in the sleeve by treating ?(1) as a triangle vertex and extending the funnel one last time. Thus, assuming the polygon is already triangulated, the overall time to compute the shortest path is O(x + x ? ) = O(x) = O(nk).

In my own code, I create dummy portals for the start and end positions where the left and right endpoints of the portals are the same as the positions themselves. This should fall into place nicely with the rest of the algorithm as long as your cross product comparisons are using >= or <= (not the strictly < or >).

I hope this helps!

Not only did that help, but it fixed the problem. I hastily cut out an iteration from the main loop, because the destination was being added to the funnel twice. So it messed up the final check. Now that I think about it, it's perfectly logical why it's there. Thanks, indeed!

I tried to implement Demyen's approach but I gave up after trying for a really long time to get all the details just right. Although I haven't tried it myself, I suspect that shrinking the nav mesh would indeed be a much simpler approach, and if you can afford it, it might be best to have a few different nav meshes tuned for particular sizes.

I'm generating all of my mesh data procedurally and I'm by necessity dealing with either islands or holes. The reasons are a bit complicated, but in a nutshell this is what I'm up against:

<technicaldribble>

just to save a few nerve cells I gave up my own triangulation code and adopted the Triangle library, mainly because since it supports CDT (constrained Deulaunay triangulation) and is notably faster than my own ear clipping code. However, it dies when I feed it concave polygons with interior edges that wrap around islands. As a result I'll have to purge the interior edges, convert the islands into separate holes and rely on Triangle to feed me back the concave hull after it's done. The problem is that so far I haven't been able to gouge a proper set of hull segments from it after refinement. That is, simple triangulation, which produces fewer but poorly graded triangles works fine, since I already have my hull and the initial triangulation doesn't compromise it. But refinement can add vertices to the interior and the edges, which means I will no longer have a valid nav mesh to work off of. As if interior vertices weren't hard enough to deal with... Of course I could shrink the nav mesh for all agent sizes and then triangulate it, but that seems like an awful waste of resources, especially since I want the nav mesh generation code to be viable in near real-time (on the order of ~10-20 ms per cell).

</technicaldribble>

As for the other person (http://www.koffeebird.com/2014/05/towards-modified-simple-stupid-funnel.html), I do exactly this approach on my game and if you can operate under the same assumptions, namely that the portals you have are guaranteed for the agent of radius R, it works great (at least I think so)! Performance is absolutely a non-issue for me. On very long paths, my entire string pulling + tangent to circle computation takes on the order of ~50000 cycles which is around 0.02 ms on my machine. The A* search takes far, far longer. The A* search alone to generate that path could take me 0.25 to 0.5 ms.

You have far bigger problems to worry about when it comes to performance in pathfinding. The A* search (if you're using it) will be the lion's share of the time spent.

I haven't delved into that code, but it seems to impose the limitation that the subdivided nav mesh cannot be refined (eg forced to adhere to good grading/roughly equal-size/shape triangles). Simple vertex-based triangulation will always implicitly define the maximum agent size that can pass through the nav mesh (which is equal to each particular edge length), but vertices that are added to the body of the mesh itself effectively destroy that information that.

Then again, perhaps I'm overthinking all this refinement thing in the first place and long narrow triangles are just fine...

My initial plan was to go with convex decomposition, but the code I've written is a real pain to convert from recursion to stack-based linear format, so I eventually gave up and took the easier way out.

In the end I'll probably end up going the same route you are: raw triangulation + hull shrinking + the funnel algorithm from the koffeebird link.

I'm generating all of my mesh data procedurally and I'm by necessity dealing with either islands or holes. The reasons are a bit complicated, but in a nutshell this is what I'm up against:

<technicaldribble>

just to save a few nerve cells I gave up my own triangulation code and adopted the Triangle library, mainly because since it supports CDT (constrained Deulaunay triangulation) and is notably faster than my own ear clipping code. However, it dies when I feed it concave polygons with interior edges that wrap around islands. As a result I'll have to purge the interior edges, convert the islands into separate holes and rely on Triangle to feed me back the concave hull after it's done. The problem is that so far I haven't been able to gouge a proper set of hull segments from it after refinement. That is, simple triangulation, which produces fewer but poorly graded triangles works fine, since I already have my hull and the initial triangulation doesn't compromise it. But refinement can add vertices to the interior and the edges, which means I will no longer have a valid nav mesh to work off of. As if interior vertices weren't hard enough to deal with... Of course I could shrink the nav mesh for all agent sizes and then triangulate it, but that seems like an awful waste of resources, especially since I want the nav mesh generation code to be viable in near real-time (on the order of ~10-20 ms per cell).

</technicaldribble>

Can you show me an image to describe what's going on? Something doesn't vibe with me very well with what you've described, but I'm not sure I'm fully understanding your situation. For instance, I don't understand what you mean by "concave polygons with interior edges that wrap around islands". If my recollection of CDT is correct, it shouldn't make a difference if you have a concave polygon or not.

Can you show me an image to describe what's going on? Something doesn't vibe with me very well with what you've described, but I'm not sure I'm fully understanding your situation. For instance, I don't understand what you mean by "concave polygons with interior edges that wrap around islands". If my recollection of CDT is correct, it shouldn't make a difference if you have a concave polygon or not.

Here's the same dataset after simplification, but without "jaggie" and degenerate edge removal, which collapsed the two small islands in the previous example (notice that the polygon has no holes - it's just a simple polygon whose concavity extends inwards along a line and wraps around the two small islands):

[attachment=28097:islands.png]

Here's the dataset with the islands removed and Triangle's CDT refinement applied. Notice the interior vertices that result in nicely graded triangle output:

[attachment=28098:refined.png]

While I can easily triangulate the first polygon with ear clipping, the problem with CDT and interior edges is that these have to deal with overlapping vertices, which seriously confoozle the Delaunay divide and conquer phase, causing Triangle to crash. The solution would be to remove these edges and turn the vertices that lie around islands into separate sets that represent holes. It's actually easier than it seems in my case, since I already have vertex classifications from the flood-fill phase, but the bigger problem has to do with nav mesh shrinking, which then needs to do clipping to ensure the holes don't extend past another hole or an outer edge. The problem is compounded when refinement is applied, which can and will add vertices to the interior of the set as well as on the hull. As I mentioned above, I haven't been able to reliably get this information back from Triangle yet. Also, as mentioned, a far simpler, but much more costly solution would be to shrink the nav mesh in image a for all agent sizes and then apply triangulation, but this violates my current mandate that I be able to do it in near real time.