1
\$\begingroup\$

Stalled funnel algorithm

Disclaimer : yes, the whole map is not convex. But all of its subdivisions are ! (And that's what matters)

Hi ! I got A* working with nav mesh. Now I need to find the tightest path along the mesh path. While reading about the Funnel algorithm, I found an article where the author mentions that this algorithm can work with any convex polygon, as long as no portals are intersected.

However, while testing it, I ran into a problem : my algorithm is blocked. (See figure B) In figure A, the funnel can be narrowed, but in figure B, we can clearly see that neither side can progress :(

1 - Am I understanding the algorithm correctly ?

2 - Should I simply stick with triangles ? (I was keen on using polygons)

3 - Do you suggest another algorithm to make it work with any convex polygon ?

Thanks for your help !

Link to article : https://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html (The claim about convex polygons is faaar in the comment section. (Ctrl + F -> search for convex))

\$\endgroup\$
11
  • 2
    \$\begingroup\$ That shape in your diagram isn't a convex polygon \$\endgroup\$
    – Adam
    Commented Nov 8, 2023 at 15:06
  • \$\begingroup\$ All of these polygons are convex though. If the map as a whole must be convex the algorithm won't be really useful 😋 \$\endgroup\$ Commented Nov 8, 2023 at 15:12
  • 1
    \$\begingroup\$ I think you're missing a step from the article "and restart the algorithm from there (G)." It looks like this is supposed to be used recursively/hierarchically using a new starting point based on the last cycle? \$\endgroup\$
    – Romen
    Commented Nov 8, 2023 at 18:39
  • 1
    \$\begingroup\$ Thanks for your input Romen. I added a disclaimer in my post ! I just found the answer to my problem elsewhere. I'll write it down a bit later to share it. \$\endgroup\$ Commented Nov 8, 2023 at 21:19
  • 1
    \$\begingroup\$ It seems to me that the algorithm would have worked if you traverse the edge that actually narrows the funnel, instead of the one that widens it in B. Then the rays end up crossing and have to restart from that corner (either works). Repeating the algo from there finds a solution (done in my head). So I think your example is not implementing the algorithm correctly by allowing a widening step instead of narrowing. \$\endgroup\$
    – Romen
    Commented Nov 8, 2023 at 21:22

1 Answer 1

3
\$\begingroup\$

Edit : After further testing, I found out that a special case of this kind is also needed for triangles in some cases. I probably just incorrectly understood the algorithm ? Maybe it's because this special case isn't often covered in other articles.

A kind person nicknamed winkio helped me on Discord, so I'll share what I understood from his answer here.

Funnel algorithm with any convex polygon

Disclaimer : to understand this, start by understanding the Simple funnel algorithm : http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html

To handle any convex polygon (and not just triangles), we can add a special case to the algorithm, of which I'll give an example at steps F-G.

I tried my best to explain (and illustrate it), but the special case can be difficult to grasp. I think it's worth reading if you want to use any convex polygon like me ! Somehow I was having trouble finding documentation on this very constraint. (Perhaps because going exclusively with triangles is the way) If you ever need more details, let me know in a comment !

Step A : Starting the algorithm. Both sides reach the next (first) portal.

Step B : Starting randomly with the left side, we try to reach the next left end of the next portal : this is narrowing the funnel, so it's good. ✅

Step C : Moving on to the right side, we try to reach the next right end of the next portal : this is narrowing the funnel so it's good. ✅

Step D : Moving on to the left side, we try to reach the next portal... but it's broadening the funnel, so we don't do it. 🚫

Step E : Moving on to the right side, we try to reach the next portal... but it's broadening the funnel, so we don't do it. 🚫

Step F : Ooops ! We can't progress on either side. In this special case, winkio suggests we "force" the algorithm to progress on both sides, but we must keep in mind the previous vectors... which makes a concave funnel, temporarily. Of course, this makes the algorithm a bit more complex because we need to keep track of more data in this case.

Step G : We try to progress with the left side. (Still from the first apex) Oops ! We're narrowing the funnel, but we passed over the right side. We must then add a new apex on the right side, on the last portal that was reached without problem. Because of the step F, we must also check if the new left side is also passing over the new right side, starting from the new apex. It is not the case, and since we overcame the "weird special case situation", we are back to a normal funnel.

Step I : Trying to progress on the right side. We can't, because it's broadening the funnel. 🚫

Step J : Trying to progress on the left side. Oops ! We passed over the right side. ⛔

Step K : Time to place a new apex. We also progress on the right side otherwise the right side vector will be (0,0). At this point we could stop because one side reached the goal.

Step L : The left side also reaches the goal if we continue the algorithm.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .