A* Algorithm

A* (pronounced "A-star") is a graph traversal and path search algorithm, which is often used in many fields of computer science due to its completeness, optimality, and optimal efficiency. One major practical drawback is its O(b^d) space complexity, as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A* is still the best solution in many cases. Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968. It can be seen as an improvement of Dijkstra's algorithm. A* achieves better performance by using heuristics to guide its search. Compared to Dijkstra's algorithm, the A* algorithm only finds the shortest path from a specified source to a specified goal, and not the shortest-path tree from a specified source to all possible goals. This is a necessary trade-off for using a specific-goal-directed heuristic. For Dijkstra's algorithm, since the entire shortest-path tree is generated, every node is a goal, and there can be no specific-goal-directed heuristic.

Sources: wikipedia.org

A* Applications



A*'s time performance as a Pathfinding algorithm in game development has shown that although the genetic algorithm is faster than A*, it is used most commonly for pathfinding because its flow and logic are easy to understand. The algorithm also quickly and accurately estimates a path which allows for smooth calculations in game development.

Sources: Pathfinding Algorithms in Game Devolpment Paper






Types of games that use A* pathing:
RPGs
Used for pathing or player movement to navigate around terrain.
Racing Games
Used for gps navigation to find shortest path to destination.
Turn-Based Strategy
Used for character or unit movement to display possible movement options.