Funnel algorithm

Question

I'm implementing the funnel algorithm for pathfinding. After searching many resources I found those : https://skatgame.net/mburo/ps/thesis_demyen_2006.pdf http://digestingduck.blogspot.com.by/2010/03/simple-stupid-funnel-algorithm.html http://ahamnett.blogspot.co.at/2012/10/funnel-algorithm.html

I undestand how the algorithm works, but I didn't find the full working code, only pieces of it. So I misunderstand:

1)How the points are divided into "left" or "right" programmaticaly;

2)Is the channel represented as list of triangles(polygons) or just as a list of verticies;

Answer 1

There are MANY MANY aspects here. Funnel algorithm is also the wrong name. What you're doing is using nav-meshes instead.

Each poly of the nav mesh has the nice property of being convex. This means if you take any two points in the poly, the line between those two points stays in the poly.

Where two polys meat is a "portal". Imagine put a vertex at the centre of every portal.

You "want" to do what is essentially A* on these vertices, but rather than moving along these non-optimum lines you want to keep a "funnel" as wide as possible going in the direction you want to go (just like in A*). Whenever you have to narrow the funnel you create a vertex in your graph at the point that caused the narrowing.

The algorithm goes as follows (sort of)

1) Create a vertex at the start location, note the current nav-mesh poly
2) If the goal is inside the current poly, create another vertex at the goal, the path is from the current location to that vertex
3) For each neighbour to the poly (a neighbour is any adjacent poly connected by a portal) use your A* heuristic with the centre of that neighbour to determin the "best" direction to test.
4) Start a "funnel" at the current location with an upper bound given by one side of the portal, and a lower bound given by the other side
5) Choose the best (heuristic) neighbour to the polygon the other side of the portal we chose for the funnel.
6) If the goal is inside the poly AND inside the funnel create a vertex at the goal's location. The path from the start to it is the shortest path.
7) If the goal is inside the poly but not in the funnel create a vertex along the most recent portal the funnel goes through on the "side" (left/right I guess?) of the goal. Then create a vertex at the goal. This is the shortest path.
8) If the goal isn't inside the poly choose the lowest heuristic neighbour again. If the funnel covers the portal, narrow the funnel on each side (creating a vertex when you do). If the funnel only covers one side, clamp that one side and create a new vertex. If the funnel doesn't overlap with the portal at all. Create a vertex on the portal-you-came-through's-to-get-to-this-poly line on the side which is nearest to the portal whilst still being in the funnel. Now start a new funnel from that vertex to the target portal.
9) Go to 6.

Will add pictures if you need them, I recommend you draw some!

Answer 2

I had the same problem while searching for funnel algorithm. Here it is a summarized procedure, considering one origin and target point:

1. Triangulate your polygon
2. Select origin and target points
3. find origin and target triangles
4. Do any graph search algorithm to find the path of triangles from origin to target
5. find the path of edges connecting the triangles between origin and target
6. reorder the edges to the same direction using cross product
7. perform the funnel algorithm on the order path of edges

i've implemented in haskell the code: you can look here , but it's quite messy. https://github.com/massudaw/funnel-triangulate/blob/master/src/Triangulation.hs