A* path optimization
Jan 8 2021 ยท Pathfinding
The A* algorithm, using a straight-line distance heuristic function, is great in terms of performance, but yields a number of cases where the paths produced are not optimal.
For example, here is a path created in ScratchGraph using GraphPaper (the underlying library used for creating the connectors):
I suspect the non-optimal result is even more pronounced here given that the path is determined based on specific routing points that exist around the objects (you can spot these as the inflection points in the path), instead of a uniform grid. That said, I don’t want to use a uniform grid; while it’s likely a non-issue with A*, there is also the cost of computing which routing points are accessible vs blocked, and that cost grows quickly as the possible number of routing points grow.
An approach that works well, and doesn’t drastically increase the cost of path computation, is simplifying the generated path by checking if corresponding points in the path are visible to each other. If so, we can remove the intermediate points, and simply connect those 2 points together. Here’s a snipped from the GraphPaper codebase:
/**
*
* @param {Point[]} _pointsInRoute
* @param {Function} _arePointsVisibleToEachOther
*/
optimize: function(_pointsInRoute, _arePointsVisibleToEachOther) {
let start = 0;
let end = _pointsInRoute.length - 1;
while(true) {
if((end-start) <= 1) {
start++;
end = _pointsInRoute.length - 1;
if(start >= _pointsInRoute.length-2) {
break;
}
}
if(_arePointsVisibleToEachOther(_pointsInRoute[start], _pointsInRoute[end])) {
_pointsInRoute.splice(start + 1, (end-start) - 1);
end = _pointsInRoute.length - 1;
} else {
end--;
}
}
}
The function works as follows:
- Begin with the points
start
(first point in the path) andend
(last point in the path). - Relative to
start
, check if the other points in the path are visible to it (in the code above, we iterate backwards from the endpoint). If we find thatstart
is visible to another point, we eliminate the intermediate points from the path. - Once we get to
end
being the point afterstart
, updatestart
to the next point in the path and resetend
to whatever the last point in the path is. - Repeat the latter 2 steps until we’ve checked all corresponding points in the path (
start
is the point directly precedingend
).
Optimizing the path shown above with this method yields an optimal path:
In terms of performance, the cost is based on the number of points in the path and the cost of whatever computation the _arePointsVisibleToEachOther()
function does. For my use-cases, paths have relatively few points and _arePointsVisibleToEachOther()
consists of a number of fairly fast line-line intersection checks, so the method is fairly cheap and there’s no significant decrease in performance when generating paths.