Research Of Path-findingin Game Maps Based On Improved A~* Algorithm

With the progress of science and technology,electronic games have the leapfrog development.The rapid development of the game industry isrelating to research in the game technology of development. Path-finding algorithm based on A~* algorithm has been a hot research topic in the game development technology.Although A~*search algorithm is efficient, but there are also some disadvantages. First of all, in large-scale games, traversingthe OPEN table again and againin the process of thenode extension,it seriouslyaffects the search efficiency. Second, the nodes haing the same F value will be considered when they search for the optimal node,but the node far away from the target is not optimal, the result is investigating a lot of useless nodes.The research work of this paper is researchof path-findingbased on A~*algorithm map game, using the improved A~*algorithm to improve the efficiency ofpath-finding in the game map.Through the simulation experimentverifythe effectiveness of the improved A~*algorithm. The main works of this paper:Fristly, aiming at the repeated traversal problem of A~*pathfinding algorithm to the OPEN table, this article uses the mixed data structure to optimize of the OPEN list. Choose the smallest binary heap to store the OPEN table node, which can effectively improve the efficiency of getting the lowest F value node. At the same time use the index array to mark the nodes in OPEN table, which can reduce the time complexity to O(1).Secondly,it will generate huge quantity problem of visiting to a large number of useless nodes, this article use the cosine function to improve the heuristic function, the improved heuristic function can effectively reduce number of inspectionto the useless node.Thirdly, in this paper, in order to verify the feasibility and effectiveness of the improved A~*algorithm, there desigin the simulation experiments on improved A~*algorithm to make contrast analysis,respectively statistics out of the time it takes to millisecondsand the total nodes of finding. Through the value of the time-consuming and the total number of searchingnode, it will evaluate the effectiveness of the improved algorithm.