A*-based Pathfinding in Modern Computer Games

Full text for this resource is not available from the Research Repository.

Cui, Xiao and Shi, Hao (2011) A*-based Pathfinding in Modern Computer Games. International Journal of Computer Science and Network Security, 11 (1). pp. 125-130. ISSN 1738-7906

Abstract

Pathfinding in computer games has been investigated for many years. It is probably the most popular but frustrating game artificial intelligence (AI) problem in game industry. Various search algorithms, such as Dijkstra’s algorithm, bread first search algorithm and depth first search algorithm, were created to solve the shortest path problem until the emergence of A* algorithm as a provably optimal solution for pathfinding. Since it was created, it has successfully attracted attention of thousands of researchers to put effort into it. A long list of A*-based algorithms and techniques were generated. This paper reviews a number of popular A*-based algorithms and techniques from different perspectives. It aims to explore the relationship between various A*-based algorithms. In the first section, an overview of pathfinding is presented. Then, the details of A* algorithm are addressed as a basis of delivering a number of optimization techniques from different angles. Finally, a number of real examples of how the pathfinding techniques are used in real games are given and a conclusion is drawn.

Item type Article
URI https://vuir.vu.edu.au/id/eprint/8868
Official URL http://search.ijcsns.org/02_search/02_search_03.ph...
Subjects Historical > Faculty/School/Research Centre/Department > School of Engineering and Science
Current > FOR Classification > 0802 Computation Theory and Mathematics
Historical > SEO Classification > 8902 Computer Software and Services
Keywords ResPubID23018, pathfinding, A*, A* optimization, computer game
Download/View statistics View download statistics for this item

Search Google Scholar

Repository staff login