Subgoal graphs for optimal pathfinding in eight-neighbor grids

摘要: Grids are often used to represent maps in video games. In this paper, we propose a method for preprocessing eight-neighbor grids generate subgoal graphs and show how can be find shortest paths fast. We place subgoals at the corners of obstacles (similar visibility graphs) add those edges between that necessary finding paths, while ensuring each edge connects only easily reachable from one another. describe by first high-level through then low-level consecutive on path. Our was ten entries Grid-Based Path Planning Competition 2012. Among all optimal path planners, ours fastest complete required least amount memory.