Hierarchical Dynamic Path Finding Algorithms In Game Maps

In commercial computer games, path finding performance directly affects the feelings ofplayers and their satisfaction, and path planning in games is often constrained by the limitedcomputer memory and CPU resources. In dynamic environments, roles must make animmediate response to the terrain changed any time. Path planning methods need a strongre-planning capability.The time complexity and memory-consuming of standard A*algorithm is high. HPA*algorithm searches devious paths in open regions, and still needs a larger storage. LPA*algorithm searches lots of nodes in the worst cases. In this research, based on these traditionalpath finding algorithms, we have studied the previously mentioned issues about path findingin game maps, and improved the performance of these algorithms. Specifically, this researchwork is mainly divided into two parts:1. We have proposed a new hierarchical path finding algorithm KM-A*. KM-A*generates uneven partitions of given game maps with reference to clustering results, whichreflects the distribution characteristics of obstacles in different maps. Based on these unevenpartitions, the corresponding abstract graph of the map is then obtained. KM-A*firstly usesA*to find a path in the abstract map, then runs A*or Bresenham algorithm for pathrefinement. KM-A*is suitable for path planning in static environments.2. We have developed a hierarchical dynamic path planning algorithm HPLPA*.HPLPA*runs LPA*first in the abstract diagram for the initial search. When the terrainchanges, A*is used to update the abstract diagram. Then LPA*runs in the updated abstractmap for path re-planning rapidly to find the abstract path, which is then refined to local pathby A*. HPLPA*is suitable for path planning in dynamic environments.Some experiments are conducted on more than60maps, which are randomly generatedmaps and game maps of the Baldur’s Gate II. The average online searched time, the averagepath length, and the average searched nodes were compared. The experimental resultsdemonstrated the effectiveness of the proposed method.