Performance Analysis of Pathfinding Algorithms Based On Map Distribution

Abstract

The distribution information of game maps is highly relevant to the execution efficiency of path searching and the degree of game difficulty. This paper analyzes the relationship between the pathfinding performance and the obstacles distribution in maps from two aspects, pathfinding algorithm design and game’s map design respectively. A hierarchical pathfinding algorithm called CDHPA* is proposed by incorporating the obstacle distribution in traditional HPA* algorithm.  It is used to hierarchical path search in those maps where the obstacles are densely distributed. On the other hand, a map complexity metric is defined based on the accumulation of xor calculations of given maps. This measure describes the complexity of a map and hence could reflect the performance of pathfinding algorithms, which could provide references for game maps design. The experimental results have validated the proposed analysis.