A Multi-task Pathfinding Method Based on CBR and Kd-tree

Yan Li, Sen Liang, Lanming Su, Jiacheng He

Key Lab. In Machine Learning and Computational Intelligence College of Mathematics and Computer Science, Hebei University

Baoding, China

Abstract: Pathfinding is a typical task in many computer games, and its performance will affect the quality of game AI. In order to enhance the efficiency of multi-task pathfinding, case-based reasoning has been introduced in traditional A* algorithm, called the CBMT method. The method needs to ｓｅｌｅｃｔ representative paths which can cover the whole map to build a compact case base, which is difficult in large maps. Besides, repeatedly searching for similar cases for each pathfinding task would be a time consuming process. To address these problems, we provide a kd-tree case storage structure and case retrieval mechanical in the CBMT method. The pre-stored cases (previously found paths) are generated randomly and incrementally. The original flat storage structure of the cases is changed into the kd-tree structure. Since the searching space can be reduced by branch pruning in case retrieval, the pathfinding efficiency has been improved obviously, and the number of searched nodes is also reduced.

Keywords: Multi-task Pathfinding; Case-based Reasoning; Kd-tree; Nearest-neighbors Search Algorithm; A*