Research of the Path Finding Algorithm A* in Video Games

Daohong Liu

doi:10.54097/hset.v39i.6642

Authors

Daohong Liu

DOI:

https://doi.org/10.54097/hset.v39i.6642

Keywords:

Path Finding; Games; Search; A* Algorithm; Video Games.

Abstract

Pathfinding is an essential component of many video games. This review provides a simple overview of the classical pathfinding algorithm A*, including a brief summary of the A* algorithm, as well as a few optimizations and applications of A* in video games. In the gaming industry, A* is a widely used pathfinding algorithm. Based on breadth first search and heuristic search, A* uses a heuristic function to quickly find the shortest path in a game map. A common optimization of A* is to use a binary heap to save the open queue, a variety of heuristic functions are also commonly used to increase the accuracy and speed of A*. This paper summarizes work done on the A* algorithm. The goal of this paper is to give researchers and developers a simple overview of the A* algorithm and its applications in video games.

Downloads

Download data is not yet available.

References

Y. Björnsson, M. Enzenberger, R. Holte, and J. Schaeffer. Fringe Search: Beating A* at Pathfinding on Game Maps. In China Internet Gaming, 2005:125–132.

P. Hart, N. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. In Computer Science 1972 4(2):100–107.

Yao Yu, LI Qing, Chen Xi. Optimization of the Application of A * Algorithm in Path Planning. Microelectronics & Computer, 2017, 34(7): 51-55.

X. Guo and P. Guo, A* Algorithm Analysis and Optimization: In Network Game Design, Computer and Information Science and Engineering, 2009:1-4.

A. V. Goldberg and C. Harrelson. Computing the Shortest Path: A* Search Meets Graph Theory. In ACM-SIAM Symposium on Discrete Algorithms, 2005 156–165.

Tristan Cazenave. Optimizations of data structures, heuristics and algorithms for path-finding on maps. In China Internet Gaming, 2006, 27–33.

Yngvi Björnsson and Kári Halldórsson. Improved heuristics for optimal path-finding on game maps. In conference on artificial intelligence and interactive digital entertainment, 2006: 9–14.

N. Sturtevant, A. Felner, M. Barer, J. Schaeffer, and N. Burch. Memory-based heuristics for explicit state spaces. In International Joint Conference on Artificial Intelligence, 2009, 609–614.

Wavefront and A-Star Algorithms for Mobile Robot Path Planning. Available from: https:// www. ResearchGate. net/figure/Flow-chart-of-A-star-algorithm_fig1_319404402

Cui, Xiao & Shi, Hao. A*-based Pathfinding in Modern Computer Games. International journal of computer science and network security, 2011,11(1):125-130.