Research Of Routing In The Game Map Based On Improved A* Algorithm

With the development of computer hardware and software technology, the game industry has also been developed. In recent years, the sound and visual effects in the game have been enhanced and improved greatly. However, the research and application of artificial intelligence technology in the game are relatively backward, so the virtual character's behavior in the game becomes monotonous and stupid. It can only repeat a few simple moves; this affected the quality of the game seriously. However, using artificial intelligence technology made the virtual character look more intelligent. So, in recent years artificial intelligence technology became a hot research topic in improving and enhancing the quality of the game. In the software of game, artificial intelligence is an important and complex module, and path-finding algorithm is the most important issues in artificial intelligence.A* algorithm is the most widely used artificial intelligence path-finding algorithms in the game developing currently. It is a heuristic search algorithm, the evaluation function is:F(n)=G(n)+H(n), G(n) is the actual distance from the start node to the current node, H (n) is the valuation distance from the current node to the target node. Using this function can calculate the valuation of all the nodes, which can search in the next step. Then choose the minimum to be the next node. So this path is the optimal path. It seems that the evaluation function is the most important in A* algorithm. It designed appropriately can greatly improve the efficiency of the search algorithm. In this paper, Firstly, improve the evaluation function, Secondly, optimize the searching speed in OPEN table, thirdly, combining the algorithm of a single object and A* algorithm. Finally, realize the standard A* algorithm and the improved algorithm using C++language, then according to the nodes and the time, which spent to search the path. They can verify the improved algorithm's feasibility and affectivity. In this paper, use 32* 32 rectangular grids to simulate the game map. The black boxes represent the obstacles in the game. Such as buildings, walls, rivers, other harmless through areas. Specific research methods and steps are as follows:Firstly, through analysis, we know that the most time consuming part in A* algorithm is: finding the smallest F value node in the OPEN table. In this paper, I use the binary heap method to sort the nodes in the OPEN table. Binary heap method is more efficient, greatly optimized the finding, adding and removing nodes'speed. By comparing the experimental, verification the search efficiency of improved algorithm than the standard A* algorithm increased 5%.Secondly, through improve the valuation function, reducing the number of nodes. However, the game map is huge. The number of nodes is still very large. Through analysis, we found that from the starting node to the target is a straight line when there do not have obstacles.So I combine the algorithm of a single object and A* algorithm, in order to further improve the speed. By comparing the experimental, verification the search efficiency of improved algorithm than the standard A* algorithm increased 11.5%.Finally, I combine the two methods. Then, use it to find path in game map. By comparing the experimental, verification the search efficiency of improved algorithm than the standard A* algorithm increased 14.7%.