# Correct way of combining A* and funnel

I implemented a pathfinding algorithm like this:

• There is a mesh of triangles that defines the area the player can walk.

• An A* algorithm is used for finding a path from the start triangle to the end triangle.

• A funnel algorithm is used for optimizing the path returned by A*.

The result looks like this:

• The red lines mark the triangles of the mesh.

• The blue lines are the path returned by A*. The path connects the centres of the triangles that are found.

• The green lines are the path returned by the funnel algorithm.

In the screenshot above, it can be clearly seen that the green path is not optimal. The optimal path would be a straight line from start to end.

The blue path causes the problem. Since A* just uses the centres of the triangle as a heuristic to determine the length of the path from one triangle to the next, it thinks the best way would be to go through the three triangles below rather than the single triangle above. The blue path is then passed to the funnel algorithm, which only "sees" the triangles connected by the blue path; it cannot find the optimal path, because it is given the wrong set of triangles to work with.

So, I suppose the bug is caused by the heuristic of A* failing to determine the correct length. How to improve this? What is a better heuristic than just measuring the distances of the centres of the triangles?

Here's the main loop of the A* algorithm:

while ((pCurrent = removeOpenTriangWithLowestEstimatedScore()) != nullptr)
{
if (pCurrent == pGoal)
{
break;
}

m_mapClosed[pCurrent] = true;

for (const CTriangle *pNeigh : pCurrent->neighboursConst())
{
ASSERT (pNeigh != nullptr);

if (isInClosedSet (pNeigh))
{
continue; // the neighbour has already been evaluated
}

if (!pNeigh->enabled())
{
m_mapClosed[pNeigh] = true;
continue;  // the neighbour is disabled
}

auto itNeigh = findInOpenSet (pNeigh);

if (itNeigh == m_lstOpen.end())
{
// Add pNeigh to the open set.
tas.pT = pNeigh;
tas.dScore = DBL_MAX;
m_lstOpen.push_back (tas);
itNeigh = m_lstOpen.end();
itNeigh--;
}

// Estimate the distance from the neighbour to the goal.

double dNeighToGoal = pNeigh->distanceOfCentres (*pGoal);

if (dNeighToGoal < dNearestDist)
{
dNearestDist = dNeighToGoal;
pNearestTriangle = pNeigh;
}

// Compute the actual score from start to the neighbour.

double dScore = actualScore (pCurrent) + pCurrent->distanceOfCentres (*pNeigh);

if (dScore >= actualScore (pNeigh))
{
continue; // this is not a better path
}

// This path is the best until now. Record it!

m_mapCameFrom[pNeigh] = pCurrent;
m_mapActualScore[pNeigh] = dScore;

updateEstimatedScore (itNeigh, pNeigh, dScore + dNeighToGoal);
}
}


And here's the main loop of the funnel algorithm:

for (it++; it != lstTriangles.end(); pPrev = *(it++))
{
const CTriangle *pT = *it;
ASSERT (pT != nullptr);
ASSERT (pPrev != nullptr);

getOrderedVertices (*pT, *pPrev, ptA, ptB, ptC);

// ptA is the new vertex, ptB and ptC are shared by pPrev.

if (isTurnedAway (ptApex, ptA, ptB))
{
ptApex = ptB;
vecResult.push_back (ptApex);
}
else if (isTurnedAway (ptApex, ptC, ptA))
{
ptApex = ptC;
vecResult.push_back (ptApex);
}
}

• I don't think this is a bug so much as a property of your setup. If these triangles are the only nodes A* can use, then this is indeed a valid path. From the top of my head I don't know a proper solution though, other than "add more nodes to your mesh". – Christian Sep 12 '18 at 8:29
• How does adding more nodes to the mesh help? Or, how could I change the setup to get better results? – digory doo Sep 12 '18 at 9:52
• I just meant that more nodes would mean a tighter mesh, so any result from A* would be much closer to your actual goal - although of course pathfinding would be more expensive. DMGregory's answer is much better though, so just disregard anything I've said :) – Christian Sep 12 '18 at 11:19
• Can't you use the ramer douglas peucker algorithm to simplify the path? – clankill3r Sep 13 '18 at 14:10
• @clankill3r: No, the algorithm you mention just simplifies the number of points, but the funnel algo finds the best path within a set of triangles. – digory doo Sep 13 '18 at 15:01

You don't have to implement A* this way. You can use discretized polygon-to-polygon distances to accumulate your path length g, but use the Euclidean distance to your actual destination point (not the center of its containing polygon) for your heuristic estimate h. This remains an admissible heuristic, because it never over-estimates the length of the shortest path to the destination.
• Ok, I think I get it. The change is simple enough (dNeighToGoal = pNeigh->centre().distanceTo (ptTo);). However, the results seem very similar in most cases. – digory doo Sep 12 '18 at 12:47