A* Algorithm
Combine heuristics,
With the purity of maths,
To find the path hence
The A* algorithm is a type of best-first search [5] resembling the Dijkstra algorithm. The sole difference is its use of heuristics to prioritise the search paths to expand. In physical pathfinding, this heuristic may be the length of the path, or the time taken to traverse it.
A* is very common algorithm for pathfinding when creating AI. Although it is not only used for pathfinding. It has several useful features that have been proved by P. E. Hart, N. J. Nilsson and B. Raphael in their study in 1968 [1]. First, if the path exists, it will surely find a path from starting point to its goal. Second, the estimated cost from point A to the destination "is always less than or equal to the cheapest path cost." [2]. And lastly, A* "makes the most efficient use of heuristic." [2], which means it examines fewer nodes than any other search method.
Even though it's the most popular pathfinding method in games, developers might still have problems applying it depending on their game world. Nevertheless, there are a lot of ways to optimize it to the game world it's been used in. Some of the methods are discussed in [2].
Image from [6]. An illustration of the A* algorithm in play. The heuristics are visible in the boxes: 'distance travelled', 'estimated distance to destination', and 'distance + estimated distance to destination'
The A* process, as described in [2]. Image taken from [2].
Psuedocode of the A* process. Image taken from [4].
- [1] P. E. Hart, N. J. Nilsson and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," in IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, July 1968. Available: https://www.cs.auckland.ac.nz/courses/compsci709s2c/resources/Mike.d/astarNilsson.pdf [Accessed: 13-Feb-2019]
- [2] X. Cui and H. Shi, "A*-based pathfinding in modern computer games," vol. 11, 112010. Available: http://paper.ijcsns.org/07_book/201101/20110119.pdf [Accessed: 13-Feb-2019]
- [4] H. Sharma, A. Alekseychuk, P. Leskovsky, O. Hellwich, R. Anand, N. Zerbe, and P. Hufnagl, "Determining similarity in histological images using graph-theoretic description and matching methods for content-based image retrieval in medicaldiagnostics," Diagnostic pathology, vol. 7, p. 134, 10 2012.
- [5] R. DECHTER, J. PEARL, "The B* tree search algorithm: A best-first proof procedure.", Readings in Artificial Intelligence. p. 79-87, 1981. Available: https://www.ics.uci.edu/~dechter/publications/r0.pdf [Accessed: 14-Feb-2019]
- [6] P. Lester, "A* Pathfinding for Beginners", 2003. Available: https://www.gamedev.net/articles/programming/artificial-intelligence/a-pathfinding-for-beginners-r2003/ [Accessed: 15-Feb-2019]