Optimized Application and Practice of A* Algorithm in Game Map Path-Finding
Huilai Zou, Lili Zong, Hua Liu, Chaonan Wang, Zening Qu, Youtian Qu · 2010
The techniques of path finding and its optimization are widely applied in the fields of game development, intelligent navigation, GIS and so on. We have pointed out the deficiency of A* algorithm by analyzing the algorithm based on heuristic search and combining with the field of game development. By the skill of flood filling and the potential field to pre-treatment analysis the map, with searching optimization heuristic function to break the equilibrium, which eliminate exhaustive search effectively when face an ac-node in the map, improve the Intelligent of the algorithm to obstacle avoidance, and also avoid some invalid expansion. So in this way the efficiency in time and space has been greatly improved. Finally, the specific procedures have verified its feasibility and effectiveness by optimizing the data structure. Besides, the relevant areas also have a good universal currency.