Waypoint Graph Based Fast Pathfinding in Dynamic Environment
Weiping Zhu, Daoyuan Jia, Hongyu Wan, Yang Tuo, Cheng Hu, Kechen Qin, Xiaohui Cui · International Journal of Distributed Sensor Networks · 2015
Pathfinding is a fundamental task in many applications including robotics, computer games, and vehicle navigation. Waypoint graph is often used for pathfinding due to its advantage in specifying the space and obstacles in a region. Currently the waypoint graph based pathfinding suffers from large computation overhead and hence long latency in dynamic environment, where the location of obstacles may change. In this paper, we propose a fast approach for waypoint graph based pathfinding in such scenario. We eliminate unnecessary waypoints and edges to make the graph sparse. And then we design a prediction-based local method to handle the dynamic change in the environment. Extensive simulation has been done and the results show that the proposed approach outperforms existing approaches.