Suggestions to speed up pathfinding

These are some simple suggestions that could speed up pathfinding in common cases.

1

PathFinder.ShortestPath takes a source and destination cell. However, it uses new DijkstraShortestPath() which calculates the shortest path between the source and ALL destination cells! In the usual use case where you only want the shortest path to the destination cell, you can use a variant of DijkstraShortestPath that breaks when it reaches the destination cell. See "Early Exit" here: http://www.redblobgames.com/pathfinding/a-star/introduction.html

I think it's as simple as breaking the loop in DijkstraShortestPath at line 51 (and taking the destination as a parameter).

2

Implement A as well as Djikstra. The algorithms are very similar, you just need to add a heuristic to the priority queue insertion at line 73 in DijkstraShortestPath. However, you will need to extend EdgeWeightedDigraph so that there is the concept of the grid coordinates of each node, so A can know what the 'right' direction to go in.

As time permits, I may have a shot at a PR for these myself.

Comments (5)