Download pdf
Game Pathfinding System Design based on A-Star Pathfinding Algorithm
- 1 The School of Integrated Circuits, Huazhong University of Science and Technology, Wuhan, 430074, China
* Author to whom correspondence should be addressed.
Abstract
Pathfinding systems are used in many applications today, including navigation systems, autonomous driving systems, and games. The core part of the pathfinding system is the pathfinding algorithm, A Star pathfinding algorithm is a kind of efficient pathfinding algorithm, which is especially suitable for the design of game pathfinding. In this paper, based on the A Star algorithm, Godot game engine and C Sharp language are used to write a pathfinding program. After comparing different pathfinding methods and the estimated function, the A Star algorithm is improved according to the needs of the actual game pathfinding system, so that the pathfinding program can avoid crossing the obstacles through the diagonal by searching the surrounding obstacles and excluding unavailable nodes, and find a shorter path by using the Euclidean distance estimated function. The program applies the improved A Star algorithm in practice, and finally can complete the basic pathfinding needed in the game, which is practical for the design of the game's pathfinding system.
Keywords
Pathfinding system, A star algorithm, estimated function.
[1]. Chen Y, Shen S, Chen T, et al. 2014 Path optimization study for vehicles evacuation based on Dijkstra algorithm. Procedia Engineering, 71, 159-165.
[2]. Shu X W 2012 The improved dijkstra's shortest path algorithm and its application. Procedia Engineering, 29, 1186-1190.
[3]. Duchoň F, Babinec A, Kajan M, et al. 2014 Path planning with modified a star algorithm for a mobile robot. Procedia engineering, 96, 59-69.
[4]. Ma X 2024 Robot path planning and obstacle avoidance based on a combination of hybrid A-star algorithm and time-elastic-band algorithm. AIP Publishing, 3144(1).
[5]. Zhang Y, Dong B, Zhang L, et al. 2024 Global path planning for mobile robots based on improved A Star algorithm. Research Square.
[6]. Yin W, Yang X 2013 A totally Astar-based multi-path algorithm for the recognition of reasonable route sets in vehicle navigation systems. Procedia-Social and Behavioral Sciences, 96, 1069-1078.
[7]. Erke S, Bin D, Yiming N, et al. 2020 An improved A-Star based path planning algorithm for autonomous land vehicles, International Journal of Advanced Robotic Systems, 17(5).
[8]. Liu C, Mao Q, Chu X, et al. 2019 An improved A-star algorithm considering water current, traffic separation and berthing for vessel path planning. Applied Sciences, 9(6), 1057.
[9]. Permana S H, Bintoro K Y, Arifitama B, et al. 2018 Comparative analysis of pathfinding algorithms A star, dijkstra, and bfs on maze runner game. IJISTECH (International J. Inf. Syst. Technol), 1(2), 1.
[10]. Lawande S R, Jasmine G, Anbarasi J and Izhar L I 2022 A Systematic Review and Analysis of Intelligence-Based Pathfinding Algorithms in the Field of Video Games. Appl. Sci, 12, 5499.
Cite this article
Bai,H. (2024). Game Pathfinding System Design based on A-Star Pathfinding Algorithm. Applied and Computational Engineering,94,57-63.
Data availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
Disclaimer/Publisher's Note
The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
About volume
Volume title: Proceedings of CONF-MLA 2024 Workshop: Securing the Future: Empowering Cyber Defense with Machine Learning and Deep Learning
© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and
conditions of the Creative Commons Attribution (CC BY) license. Authors who
publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons
Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this
series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published
version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial
publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and
during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See
Open access policy for details).