Research On Game Map Path-finding Technology Based On Optimized A~* Algorithm Under Limited Memory

With the rapid development of the modern game industry,players have higher requirements for game quality.Intelligent path-finding is one of the important applications of artificial intelligence in games,and the A~*algorithm is one of the most popular algorithms in intelligent path-finding algorithms.The A~*algorithm combines the idea of heuristic search to filter out the current optimal node,which can greatly improve the search efficiency.However,the A~*algorithm needs to expand all successor nodes of the optimal node.In the case of a large and complex map,it will face the situation of lower search efficiency and larger memory footprint of nodes.At the same time,the A~*algorithm only uses the heuristic function of the distance dimension to evaluate the current node,so it is difficult to identify the optimal node accurately.In addition,when the available memory is limited,how to reasonably adjust the path-finding strategy to approach to the target node while saving memory overhead,is also one of the difficulties faced by the A~*algorithm.In view of the shortages of the above A~*algorithm,this paper proposes an improved memory-bound A~*algorithm called IMA~*algorithm.The IMA~*algorithm proposes an efficient search structure that combines a bucket structure and a heap structure.In the case of a large number of searched nodes,the search structure reasonably divides the nodes into different buckets where the nodes are sorted.This structure can quickly select the optimal node,which improves the node search efficiency.At the same time,the IMA~*algorithm creatively introduces the height and angle information in the map,which enriches the measurement dimension of the heuristic function.The improved heuristic function assigns appropriate weighting factors to the height and angle information,which improves the accuracy of identifying the optimal node.In addition,in order to reduce the memory occupation during the path-finding process,the IMA~*algorithm proposes a memory optimization strategy for the forgotten-list.In the case of limited available memory,this strategy only creates the forgotten-list for the parent node of the removed node and allocates memory,which saves memory overhead.This paper establishes an experimental simulation platform based on Unity3D.This paper demonstrates the applicability of the IMA~*algorithm in actual game scenarios,and analyzes the performance of the IMA~*algorithm in many ways.The experimental results show that,compared with the standard A~*algorithm,the IMA~*algorithm reduces the number of searched nodes by 22.4%on average.In addition,the IMA~*algorithm can save memory overhead and has certain advantages in terms of path-finding reliability.