Studies On Hierachical Pathfinding Algorithms And Map Complexity Measures In Computer Games

Pathfinding is an important part of computer games, and game maps are the searchingspaces for pathfinding. It is very important to consider obstacle distribution information indesigning the game map and pathfinding algorithm. Most of the present pathfindingalgorithms did not consider the distribution information of obstacles in a map, which maycause unnecessary memory and time cost. Such as A*and Dijkstra, are very high and it isdifficult to satisfy the time requirement of pathfinding for large-scale maps; HPA*, M-A*donot consider the distribution information of obstacles in the process of abstraction, whichreduces the optimality of finally path; the condition of partition termination in Quadtreealgorithm is too rigid to require each subdomain containing only one type of nodes, and thisincreases the number of subdomains and then the number of abstract nodes. Specifically, thisresearch can be mainly divided into the following two parts:A new hierarchical pathfinding algorithm CDHPA*based on the obstacle distribution isproposed. The map is divided into several unequal sub-regions according to the proportion ofobstacles in the preprocessing stage, and then different pathfinding algorithms are used fordifferent distribution density of obstacles to calculate the shortest path for each pair ofabstract nodes in the map. Finally, an abstract map is formed containing abstract paths. Duringonline pathfinding, CDHPA*uses A*algorithm to find the abstract path, and refines theabstract path to local path using different algorithms for different sub-regions. BecauseCDHPA*considers the distribution information of obstacles in the process of abstraction andrefinement, the optimal path can be obtained with a small number of extension nodes, and thepathfinding time has been reduced. When the obstacles are not evenly distributed and a lot offree areas are in the map, the effectiveness of CDHPA*is particularly obvious.A new map complexity metric called ACX is defined based on the accumulation of XORcalculations. It calculates map complexity through accumulating the xor-value of eachneighbour cells line by line and describs the execution efficiency of correspondingpathfinding algorithm. This metric has shown to be highly relative with the efficiency of A*algorithm. It can provide references for the design of game maps. The results of ACX onlyrelated to the status of adjacent cell and have nothing to do with the size of the map and thenumber of obstacles.