Finding the best-promising path with A*
The A* algorithm is probably the most widely-used technique for path finding given its implementation simplicity, efficiency, and because it has room for optimization. It's no coincidence that there are several algorithms based on it. At the same time, A* shares several roots with Dijkstra's algorithm, so you'll find similarities in their implementations.
Getting ready
Just like Dijkstra's algorithm, this recipe uses the binary heap extracted from the GPWiki. Also, it is important to understand what delegates are and how they work. Finally, we are entering into the world of informed search; that means that we need to understand what a heuristic is and what it is for.
In a nutshell, for the purpose of this recipe, a heuristic is a function for calculating the approximate cost between two vertices in order to compare them to other alternatives and take the minimum-cost choice.
We need to make small changes to the Graph class:
- Define a member variable as a...
