KM-A∗ pathfinding algorithm based on hierarchical clustering and strengthened DB Index criteria

In computer games, high-quality pathfinding algorithms are important to bring satisfactory experiences to the players, which may improve the playability of computer game. The method of KM-A* belongs to hierarchical pathfinding, which incorporates the information of obstacle distribution when partitioning game maps using K-means clustering. This algorithm reduced unnecessary storage and unnatural paths in some open areas. However, the found path by KM-A* is very unstable and the quality closely depends on the clustering results. In this paper, we proposed an improved KM-A* algorithm, which aims to enhance the stability and quality of pathfinding. First, an agglomerative hierarchical clustering algorithm is used to determine the initial cluster centers, and K-Means algorithm is then applied to cluster obstacle nodes with k values which can possibly generate best cluster categories on game maps. Secondly, the strengthened form of DB Index criteria is defined by adding impact factors to the standard DB Index criteria to measure the quality of clustering results. Finally the best clustering is selected based on this new DB Index, which will provide a guidance to further generate an abstract map for on-line pathfinding. Experiments are conducted to compare the performance of KM-A* and improved KM-A*, which show that the latter can find more stable paths and use less on-line processing time.