Original Post
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.
