A*++

Just discovered a nifty new-to-me improvement on A*, via a nifty interactive demonstration of various pathfinding algorithms.

I’m supposed to be working on other things today, so I haven’t fully digested the paper explaining the algorithm and may be misunderstanding it entirely. But at least part of the trick turns out to be one of those it’s-easy-when-you-know-how things: its inventor explains you want to “prune the set of immediate neighbours around a node by trying to prove that an optimal path… exists from the parent of the current node to each neighbour and that path does not involve visiting the current node.”

In other words, at each step of the pathfinding, instead of subjecting every neighbor of the current node to A*, you try to draw a path from the previous step in the path to each neighbor. If that path crosses through the current node, then you can discard that neighbor as a possible next step.

Easy once you know how. And the speed increase compared to other pathfinding algorithms is shocking (seriously, play with that interactive demo for a bit, the difference is amazing.)