Research Of Routing In The Game Grid Map Based On Speed-up A* Algorithm

With the rapid development of the game industry, people on the effectiveness and performance of game applications in path finding algorithms are put forward higher requirements. Automatically path finding is about find one accessible path between two points in a blocking map. Path finding is one of the important area of industry.In the study of the game grid map pathfinding, the most common algorithms for the A* algorithm. A* algorithm is a heuristic algorithm, the heuristic function is f(n)= g(n)+h(n). For the node N of the game grid map. g(n) is the starting node to the actual value of the path cost has been spent, and h(n) is the estimated value of the node to the destination node path costs. Through find the min f(n) node, A* algorithm can find the shortest path between two nodes.A* algorithm in the presence of the following difficult issues:first, the standard A* algorithm measure f(n) with Manhattan distance, the Manhattan distance can not be widely applicable to different types of games grid map. Second, A* algorithm set operation time complexity is a key factor affecting the performance of the game, in the contemporary games on the background of increasingly high performance requirements, how to improve the performance of A* algorithm is a major challenge. Third, between two nodes are usually the best there are multiple equivalent paths, A* algorithm will consider all the equivalent path thus affecting the efficiency of the A* algorithm. Aiming at the three problems described above, the following research are:(1) The A* algorithm is heuristic functions of different calculation rules in different grid types. Propose an efficient heuristic A* algorithm optimization.(2) Use a custom collection replaces the A* algorithm collection. By combining the priority queue and dictionary class, effectively the minimum cost node operation time complexity is reduced, the time will verify that the node already exists for reducing the complexity of the operation.(3) Have explored one speed-up A* algorithm to accelerate the program. By using directional information path node, according to explore the depth-first search constraint rules. Effectively reducing the A* algorithm Open table explore map number of nodes, the A* algorithm to enhance the operation efficiency.Finally though the actual game project practice, to achieve the A* algorithm proposed design optimization and acceleration. And by comparing the experimental data, analysis and comparison of the standard A* algorithm and optimization algorithms to accelerate their running time and the number of nodes explored Open table. Verify the validity of the research program.