Automatic search space generation with Hierarchical Adaptive Flood Filled for simulation and computer game in confined environment

In simulation and computer game domains, pathfinding is an important capability for mobile and artificial agents. The problems of pathfinding have been widely studied for decades. The two significant aspect of pathfinding are related to search algorithm and search space. This paper mainly focuses on the search space generation aspect. Search space could be generated manually or automatically and the size of the search space has significant effects on the computational time and memory usage. Therefore, improving the search space generation techniques is essential to improve the system performance. In this paper, a Hierarchical Adaptive Flood Filled (HAFF) technique for automatic search space generation from binary image of a map is presented. From the experimental results, it is shown that the search space can be significantly reduced with the proposed method.