Case-based multi-task pathfinding algorithm

Pathfinding is an important task in computer games, where the algorithm efficiency is the key issue. In this paper, we introduce case-based reasoning method in the process of A* algorithm in multi-task pathfinding. Firstly, we save some typical paths as cases. When a new task is coming, it no longer uses A* to find a path from scratch, but firstly computes the similarity of the new task and the stored cases to decide whether to go along the previous found paths or not. A solution to the new task will be obtained after adapting to the found similar case(s). Obviously, this memory-based pathfinding can reduce the search time at the cost of using more memory to store found paths as cases. Through experimental results, it is demonstrated that, as the number of stored paths is increasing, fewer nodes are needed to be searched during the pathfinding process.