I'm trying to implement the funnel algorithm to find the best path through a channel of polygons. I think I understand the algorithm but I've found a situation that it cannot handle correctly, which leads me to think that my understanding must be incorrect. The problem occurs when the destination is just around a corner. Here's a screenshot: http://www.starsentineltactics.com/temp/funnel1.jpg This should be pretty self-explanatory. The start and end points are marked. Edges are marked in red(shared) and blue(unshared.) The left and right sides of the channel are marked in yellow and green respectively. The white line is the resulting path. P1 is there for a later explanation, but it's the only apex change that the algorithm sees the need for, and hence the only node on my path between start and end. I've checked the debug logs and my code is doing exactly what I thought the funnel algorithm was supposed to do. In other words, my understanding of the funnel algorithm is that this situation should result in a faulty path. By my understanding, the when the destination node is being considered by the path system, the funnel apex should be at p1 and both the left and right feeler should be at the end point. Parallel is not crossing, so I don't recognize a cross here. I think I'm right not to do so as the end point is always going to make both feelers converge and it cannot be right to always register a cross on the final node. So logically, I can assume that my understanding of the algorithm is flawed. If I make that assumption, the only thing which would make any difference is the order that I calculate the feelers in. I simply alternate between left and right throughout the entire length of the path. If I considered them in reverse order, the path would be evaluated correctly. But right, left, right left is no better than left, right, left, right. So there must be a system to the order in which you evaluate points. So the only logical conclusion I can come to is that the order changes every time you move the apex. If I move the apex to a point on the left of the channel, it would make sense to consider the right feelers first from that point on. And if I move to the apex to a point on the right side of the channel, it would make sense to consider the left feeler first. Am I on the right track here at all? Is there anything I'm missing (eg: what about the beginning? Does it matter which side I start on? ) If I'm on the wrong track, then could someone please steer me in the right direction. I'm pretty certain that my implementation is correct, so my theory must be wrong. I did have a lot of trouble finding good reading material on the subject, so I wouldn't be surprised.

"File not found"

There was a capitalization error in the filename, which I've just fixed. Sorry about that.

I had a similar looking problem when I was doing the algo a while ago. The problem I had was that I was stopping the algo prematurly, and not checking the contraction of the other edge once I found a path. When you alternate left-right, and you find a path from the left side, you should make sure to also contract the right side as well. I'm not sure this is the problem you are having but worth a shot.

I don't think that's the problem here, but having looked at it again, I don't think my initial thoughts were correct either. I think I was a bit punch drunk from staring at graphs for too long because I no longer think that it *should* fail as it does, which means it really *is* an implementation error instead of a theoretical error.

I think maybe I don't move the feelers back far enough when I change the apex. I think I should be resetting the feelers right back to the apex at that point, as they would be at the start point, and I think I'm not doing that correctly somehow.

Hi Sybixsus,

There seems to be some problems going on. Firstly, the ‘feeler’ on one side shouldn’t be the furthest vertex processed on that side - it should always be the vertex on that side that is closest to the other side. In this case, even if you’ve reached your end position on the left side, the point you’re using in those cross comparisons should be first the one after the apex on the left side, because it’s the furthers ‘right’ point available. Thus, it is impossible to reach the end position on the right side without violating that line, causing the apex to advance (to the correct position).

Which brings me to the second point – make sure you are not ending the algorithm when you reach the end point on one side. You need to wait until all points have been processed (ie the end position has been reached on *both* sides), otherwise you might miss the final necessitated apex.

And finally:

Quote: Original post by sybixsus
I simply alternate between left and right throughout the entire length of the path.

This is a mistake that might go undetected because it will lead to correct results in most ordinary cases. There is actually a specific order that you need to process the points – the order of the triangles on which they appear. If you’re doing things in a fairly standard manner, then this will be the same order that you add the points when you are first building your funnel. If you do simply alternate between processing left and right vertices, the algorithm will fail horribly in cases like this:



As you can see, the processing of the left side of the tunnel will surge ahead because there are fewer points. By the time you reach the third vertex on the left side the system is breaks down because the algorithm thinks the vertex is on the ‘inside’ (it’s on the right of the line from the start to the left 'feeler', which would at that stage be the first left point) even though it really isn’t. However, if we process the points in the correct order, this cannot happen. The cluster of right points near the start position will be processed first, and in all cases the funnel algorithm will advance symmetrically. You can see that the algorithm depends on convexity – by not processing the points in the right order, you are allowing the possibility of concavity to slip in, thus rendering your 2D cross product comparisons unreliable.

Quote: Original post by sybixsus
I think I should be resetting the feelers right back to the apex at that point, as they would be at the start point, and I think I'm not doing that correctly somehow.

If you're following this explanation and implementation of the funnel algorithm, then you should definitely do that. But I should verify: Demyen, the most detailed explanation I know, does the whole thing a bit differently (and quite possibly more efficiently). You’d need to consult his material for information.

As you can see, the processing of the left side of the tunnel will surge ahead because there are fewer points. By the time you reach the third vertex on the left side the system is breaks down because the algorithm thinks the vertex is on the ‘inside’ (it’s on the right of the line from the start to the left 'feeler', which would at that stage be the first left point) even though it really isn’t. However, if we process the points in the correct order, this cannot happen. The cluster of right points near the start position will be processed first, and in all cases the funnel algorithm will advance symmetrically. You can see that the algorithm depends on convexity – by not processing the points in the right order, you are allowing the possibility of concavity to slip in, thus rendering your 2D cross product comparisons unreliable.

Hi guys,

Does anyone know the work around for that problem?
I mean he pseudo code or the code.
I have every interioredge/portal but I don't know in which order i must process them. And when I do, how do I know if they are from left or right?

Thanks in advance.