A* Algorithm
WIP article
The A* algorithm is a type of best-first search [citation needed] resembling the Dijkstra algorithm. The sole difference is its use of heuristics to prioritise the search paths to expand. In physical pathfinding, this heuristic will usually be the length of the path [citation needed], which is minimised.
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 [3]. 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]. (Maybe continue this page with sub-sections for A* optimization)
- Open a node
- For each open node, open the neighbouring nodes, noting the total distance and stuff, whilst closing the node behind
- Remember the previous steps and stuff (I need to research this more it's been a long time)
C i t a t i o n n e e d e d
[1] A Formal Basis for the Heuristic Determination of Minimum Cost Paths
[2] A*-based Pathfinding in Modern Computer Games (http://paper.ijcsns.org/07_book/201101/20110119.pdf)
[3] A Formal Basis for the Heuristic Determination of Minimum Cost Paths (https://www.cs.auckland.ac.nz/courses/compsci709s2c/resources/Mike.d/astarNilsson.pdf)