• Jun 14, 2017 News!Vol.8, No.5 has been indexed by EI (Inspec).   [Click]
  • Nov 09, 2017 News!Vol.9, No.5 has been published with online version. 16 peer reviewed articles from 11 specific areas are published in this issue.   [Click]
  • Jul 19, 2017 News!Vol.9, No.4 has been published with online version. 16 peer reviewed articles from 16 specific areas are published in this issue.   [Click]
General Information
Editor-in-chief
Prof. Wael Badawy
Department of Computing and Information Systems Umm Al Qura University, Canada
I'm happy to take on the position of editor in chief of IJCTE. We encourage authors to submit papers concerning any branch of computer theory and engineering.
IJCTE 2012 Vol.4(4): 551-555 ISSN: 1793-8201
DOI: 10.7763/IJCTE.2012.V4.530

Implementation and Comparison the Dynamic Pathfinding Algorithm and Two Modified A* Pathfinding Algorithms in a Car Racing Game

Jung-Ying Wang and Yong-Bin Lin

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).

[PDF]

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-2015. International Journal of Computer Theory and Engineering. All rights reserved.
E-mail: ijcte@vip.163.com