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 t...
详细信息
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 select 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.
暂无评论