Research Repository

A*-based Pathfinding in Modern Computer Games

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

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

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
Uncontrolled Keywords: ResPubID23018, pathfinding, A*, A* optimization, computer game
Subjects: Faculty/School/Research Centre/Department > School of Engineering and Science
FOR Classification > 0802 Computation Theory and Mathematics
SEO Classification > 8902 Computer Software and Services
Depositing User: VUIR
Date Deposited: 19 Jul 2012 06:32
Last Modified: 24 Aug 2012 07:09
URI: http://vuir.vu.edu.au/id/eprint/8868
ePrint Statistics: View download statistics for this item

Repository staff only

View Item View Item

Search Google Scholar