The Research And Application Of Path Finding Algorithms In Game Artificial Intelligence

Path search is an important part of game artificial intelligence.In large commercial games,path search is often limited by storage space and CPU processing power.Path search performance directly determines the user's satisfaction with the game.By analyzing the traditional path finding algorithm in detail,several improvement and optimization methods are proposed in this paper.Through experiment,the effect of the improved algorithm is compared and analyzed.First of all,the paper discusses the background of the research and the present situation of domestic and foreign research.Path search is one of the factors that affect the whole effect of the game.Path search gives the ability of NPC to sense the environment around.To some extent,this sensible ability marks the level of NPC intelligence and directly affects the behavior of the game role.Currently,there are several path search algorithms in artificial intelligence,but most of them do not consider map topography information.So they cannot meet the actual needs of game development.Then,the paper compares the various traditional path search algorithms and describes the search space representation.The time complexity of traditional Dijkstra algorithm and A* algorithm are high.They cannot meet the requirements of large scale map of the road search.HPA * and other layered path search algorithms uniform zoning map.It did not consider the distribution information of map terrain,and had poor adaptation.To solve the above problem,the paper improves in three aspects.(1)The paper proposes an optimization methods of A* algorithm Open table.The multiset associative container is used as the data structure of the A* Open table.The paper discusses the properties of the sequential containers and associative containers and the operation of RB-Tree.The experimental comparison indicates that A* algorithm for Open table optimization is superior to the standard A* algorithm,A* algorithm for optimization of index array and blind search algorithm.(2)A new MF-A* path finding algorithm is put forward,which is based on terrain influence factors.According to the distribution of the terrain in the game,three kinds of terrain influence factors are defined with the weight of a single map region.According to the topographic influence factor,the paper designs a heuristic function for MF-A* algorithm.Subsequently,the nodes on the path are selected by the Floyd smoothing processing method,and the path is smoothed by Catmull-Rom algorithm.More than 99% of the search results by MF-A* algorithm is better than the A* algorithm,and MF-A* algorithm improves the appearance of the zigzag path.MF-A* algorithm can achieve the desired results.(3)A hierarchical path search algorithm named K-HPA* is proposed,which is based on map clustering algorithm.First,the map should be pretreated,such as screening of the barrier region,finding the initial clustering center of K-Means algorithm by the maximum distance method,and clustering the map by K-Means algorithm.The next step is to define the key nodes and construct the virtual map.In the obstacle region the MF-A* search algorithm is used,and in the non-barrier region the Bresenham processing method is adopted.The experimental comparison indicates that the search efficiency of K-HPA* algorithm is higher than that of MF-A* algorithm,and the expanded nodes of K-HPA* algorithm are less than that of the MF-A* algorithm.In the end,the paper summarizes the research work,and makes a prospect about improvement of MF-A* and K-HPA* algorithm.