Abstract——For a car racing game, the most common artificial intelligence is waypoint navigation by carefully placing waypoints in the game environment to move the game-controlled characters between each waypoint. The major drawback of this method is that these waypoints need to be manually setup. Meanwhile, these waypoints will depend upon the speedway track. In addition, the number of waypoints and the location of waypoints are also different due to human factors. In order to overcome these problems, we propose two modified A* algorithms to effectively solve the pathfinding problem in a static obstacles racing game. The first modified A* algorithm uses a line-of-sight algorithm to reduce the waypoints found by the original A* algorithm. For the speedway of F1 in Turkey, the waypoints reduced from 985 points to 28 points, over 97% waypoints could be removed. The second modified A* algorithm improves the performance of original A* algorithm by heuristically considering the truth that the game-controlled car should steer itself towards. That is to say, we only need to check three waypoints in front of the car, instead of checking four waypoints (up, down, left and right) in the original A* algorithm. Finally, a more general dynamic pathfinding algorithm which can solve the random obstacles avoidance problem in a racing game is also proposed.
Index Terms—Artificial intelligence, A* algorithm,pathfinding, racing game.
J.-Y. Wang is with the Department of Multimedia and Game Science, Lunghwa University of Science and Technology, Taoyuan, Taiwan (e-mail: wyy@mail.lhu.edu.tw).
Y.-B. Lin is with the Department of Electronic Engineering, Lunghwa University of Science and Technology, Taoyuan, Taiwan (e-mail: G972321024@ms.lhu.edu.tw).
Cite: Jung-Ying Wang and Yong-Bin Lin, "Implementation and Comparison the Dynamic Pathfinding Algorithm and Two Modified A* Pathfinding Algorithms in a Car Racing Game," International Journal of Computer Theory and Engineering vol. 4, no. 4, pp. 551-555, 2012.
Copyright © 2008-2024. International Association of Computer Science and Information Technology. All rights reserved.
