Regions Discovery Algorithm for Pathfinding in Grid Based Maps

摘要

Pathfinding problems often have to be solved under many constraints including limited processing time, memory, and computational power. The challenges become bigger as the size and complexity of the search space increase. Therefore, pathfinding on large and complex maps can result in performance bottlenecks. Researchers proposed to reduce the search space using preprocessing techniques such as hierarchical pathfinding to overcome the bottlenecks. In this paper we present a novel graph partition technique to boost the speed of pathfinding and preserve optimality for grid based environments. To overcome the weaknesses of clustering methods that are used in traditional hierarchical pathfinding algorithms, we propose to develop a graph decomposition algorithm that abstracts regions based on local features. The objective of our approach is to maintain the pathfinding optimality by only eliminating the regions that are obsolete. Thus, any possible solution path will not be eliminated during the search. Our experiment results show that a search space can be reduced as much as 47%, leading to much faster execution and less memory consumption.