Advertisement

Stupid Simple Funnel problem

Started by January 17, 2022 12:05 PM
2 comments, last by Narxes 2 years, 10 months ago

So the left node can't move to the left and the right node can't move to the right since that widens the funnel. So the algorithm gets stuck.
My solution is to detect when it is stuck and then move the apex to node that has advanced the furthest on the path.
In this case the right node has reached triangles that the left node hasn't so thats where I move the apex to.
Maybe the problem is due to the usage of rectangular borders I'm not sure.
Or could it be that the left node can check portals further down the path even if it failed to move to previous portals.
Any help on the problem is appreciated.


Description of the funnel algorithm can be found here:
http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html

To quote from the page you linked to: “If the new left endpoint is outside the funnel, the funnel is not update (E-F)”. In other words, you have five different points that you are dealing with: the apex, a left and a right funnel point, and left and right endpoints. Keep walking along the tunnel with the endpoints. If an endpoint ends up in the funnel, set the corresponding funnel point to that endpoint. If an endpoint is on the correct side of the funnel, do not do so, but keep walking. If the endpoint end up on the wrong side of the funnel, you have a path segment, so move the apex.

Unfortunately the code in the page you linked to does not appear to implement this, so I can see how you got confused. In this case, the description is correct, and the code is wrong.

It's easy to visualize this by imagining a wide straight corridor with sawtooth-shaped walls. The correct path from one end of the corridor to the other is in a straight line that never touches the walls, no matter how much the corridor narrows or widens.

Advertisement

Ok I figured out that failing to narrow the funnel still allows the algorithm from checking nodes further down the path. After testing everything works now. But yes it is a good idea to make the distinction between funnel point and endpoints.

This topic is closed to new replies.

Advertisement