Simple Stupid Funnel Algorithm

Newbie & Debugging Questions
#1

So I have a question about the Simple Stupid Funnel Algorithm (http://digestingduck.blogspot.co.uk/2010/03/simple-stupid-funnel-algorithm.html), is the only time you add a new point to the path when either the new left edge crosses the funnel’s right edge or when the new right edge crosses the funnel’s left edge? That seems to be what all the descriptions I can find say and what all the examples show but there would seem to be many cases where this does not work.

In the below:

  • Blue lines are the edges of the triangle mesh.
  • Green lines are the unoptimized path.
  • The red line is the left edge of the funnel.
  • The cyan line is the right edge of the funnel.
  • The yellow line is the current portal.
  • The magenta line is the current “optimized” path.

Now the first row works well. The second row is the exact same with the last triangle removed and produces an illegal path.

(Direct Link: http://i62.tinypic.com/2eq73t2.png)

Now as far as my understanding of the algorithm goes, my implementation is working other than that it produces an illegal result. So do I not understand the algorithm correctly, or have I missed something going wrong or is the algorithm itself just flawed?

Thanks in advance for any help.

#2

I’ve implemented the ‘un-simplified’ version of the funnel algorithm before, with good results. Unfortunately, it’s been a while and the details aren’t fresh in my mind at the moment, so I’d probably have to sit down and draw some diagrams to figure out whether the simplified version should be expected to handle all cases correctly.

However, just in case you haven’t seen it, there’s a comment on the blog post you linked to (fourth from the end) where someone questions whether the simplified version will guarantee correct results. I can’t say off hand whether his observation is correct, but it does at least suggest that the simplified version might be flawed. Also, my first impression is that the incorrect results you’re getting in the second example may be due to some other problem, as it doesn’t really match what the commenter described.

One thing I notice about the second example is that because there’s no ‘next portal’ at the end, the step where the right edge crosses over the left may not occur. If this is where the extra path vertex would be added, it makes sense it would be missed. So, that would appear to be a flaw either in the algorithm or in the implementation. (I imagine you’ve already tried stepping through in the debugger, but it seems the reason for the missing step could probably be determined that way.)

Sorry I can’t be of more help, but maybe something there will point you in the right direction.

#3

Thanks for the reply.

[quote=“Jesse,post:2,topic:55185”]
I hadn’t actually thanks. I can’t really understand what he’s saying there though, seems to me the funnel does cut through portals. But it is reassuring (if a little annoying) to know that there may be flaws. The comment for others reading btw is:

[quote=""]
And apparently no one did want to comment at all.

[quote=“Jesse,post:2,topic:55185”]
Certainly that would appear to be the reason, but like I say, what happens is as far as I can see, what is supposed to happen. The image I posted is a collection of screenshots from my actual implementation (implemented it step-wise for debugging in the end). So what you see is what you get.

I think what I will do in the end is just implement the original funnel (aka “string pulling” I think) algorithm - wouldn’t mind if this produced suboptimal paths but illegal paths I can’t be dealing with, still like to know what is going on here though. There seemed to be suggestion of using this version as a heuristic in the A* algorithm so maybe try that out so the work hasn’t been a complete waste. If you have any good links for the non-simplified algorithm you could recommend, it’d be much appreciated.

Thanks again.

#4

I just looked around a bit, but couldn’t find the reference I used, unfortunately. It was a really good paper though. The general topic was pathfinding in a Delaunay triangulation environment for agents with arbitrary radii. The specific version of the funnel algorithm used ensured that the agent stayed radius units away from all obstacles, and included curved sections in the path to go around corners.

This isn’t the paper in question:

Link

But it does have pseudocode for the funnel algorithm at the end, which might be helpful.

#5

I know the feeling. I try to keep a bookmark to any resource I use for anything longer than half an hour and still I completely lose good resources all the time. Thanks for the link.

If anyone does have a definitive answer to the simplified version however, I’d still like to hear it just for completeness.