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?