Research On Multi-Scale Pathfinding And Complexity Measure Based On Contact Surface Of Maps

Pathfinding algorithms play a fundamental role in the field of artificial intelligence.Many related applications need the support of good pathfinding algorithms. In computergames, both the player and the computer-controlled characters often require moving from alocation of the map to another, i.e., looking a path on the map. Pathfinding is one of the maintasks especially in some real-time strategy games. Since A*algorithm was put forward, manyof the improved algorithms are proposed in the literature, such as HPA*algorithm based onuniform partition, KM-A*algorithm based on clustering, as well as M-A*algorithm based onmultiscale partition. All of these methods use the concept of abstract map. However, theobtained path by HPA*is not optimal; KM-A*and M-A*’s abstraction processes are verytime consuming. On the other hand, we find that the performance of pathfinding algorithmsis strongly affected by obstacle distribution in given maps. Therefore, measuring the mapcomplexity for specific pathfinding algorithms, e.g. A*, are important to provide a guidanceof creating a suitable map for pathfinding using this specific algorithm. There are two maincontributions in the thesis:1. To address the problem that M-A*does not consider the topographic distribution inthe partitioning process and results in more abstract nodes in the generated abstract graph, anaccelerated method based on multi-scale decomposition algorithm (MTD-A*) is proposedwhich takes into account the obstacle distribution and is used to find the shortest path betweentwo specified nodes quickly. When forming an abstract graph, the algorithm will not dividethe non-obstacle regions, which simplifies the process of abstraction. Besides, when MTD-A*refinements the abstract path to an actual path, Bresenham linear algorithm instead of A*isused to find the path in the non-obstacle partition, which accelerates the pathfinding process.Experimental results show that MTD-A*can reduce the search space and therefore it is fasterthan M-A*in forming abstract graph as well as on-line pathfinding.2. This paper first puts forward the concepts of total connect map and contact surface,and then proposes a map complexity measure based on the concept of contact surface. Whenanalyzing a map, we have found that the map is formed by some simple elements (contactsurface), and the complexity of the map is to some extent determined by different states of thecontact surfaces. Through the elimination of useless contact surfaces, the proposed mapcomplexity measure can reflect the pathfinding difficulty degree more accurately comparedwith previous complexity measures based on hamming distance and relative hammingdistance.