The Study And Implementation Of Pathfinding Algorithm Face Game Map

The high speed development of the game industry has promoted the new changes of the game artificial intelligence technology. The search path algorithm for the game map has been one of the hot spots and the basic problems of the game artificial intelligence, and the A* algorithm is the most widely used algorithm in game map path searching, which is the most effective heuristic search algorithm to solve the problem of path searching. Under different data structures, A* algorithm has obviously different search efficiency, and the design of heuristic function has different effects on the running speed. At present, the research on A* algorithm is mostly on theoretical stage, while the application of A* algorithm used in the actual game project is far less, which is a worthy study on the game map search algorithm.The paper first proposes a data structure of the search node with the flag bit based on the property of A* algorithm, using the smallest binary heap to implement the OPEN table, then by comparing the simulate program and the data graph to finish this study. By A* algorithm to evaluate the function property, and then propose the weighted function which can improve the searching efficiency of the search algorithm. Secondly, combined with the practical application of the search algorithm, the navigation mesh is used to simplify the complex and large game map, and to reduce the search space of the A* algorithm. Put forward time-sharing path search, using path splicing to process the dynamic obstacles, and introduce the evaluation function into the calculation of cost of the terrain, to improve the authenticity of game map path search. Finally, this paper uses the Cocos2d-X game engine to design and develop a demo program of game map path search.The experimental results shows that the A* algorithm runs 3?22 times faster than the search data structure with the flag bit structure than that without the flag bit. The using of the minimum binary heap achieves OPEN table can reduce the searching time of 40%?60%. The heuristic function can reduce 40% of the number of nodes that need to be expanded. In the actual application of game map search, the search algorithm can keep good search efficiency, avoid the dynamic obstacles and calculate the new path, and can find more realistic game map path.