Subgoal Graphs for Optimal Pathfinding in Eight-Neighbor Grids
Subgoal Graphs for Optimal Pathfinding in Eight-Neighbor Grids
复制标题
八邻域网格中最优寻路的子目标图
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Carlos Hernández
中科院分区：
文献类型：
--
作者：
T. Uras;Sven Koenig;Carlos Hernández
网格通常用于表示视频游戏中的地图。在本文中，我们提出了一种预处理8neighbor网格以生成子观念图的方法，并显示如何使用亚距离图来快速找到最短路径。我们将子观念放在障碍物的角落（类似于可见性图），并在寻找最短路径所需的子目标之间添加这些边缘，同时确保每个边缘仅连接易于彼此可触及的子目标。我们描述了一种通过首先找到通过子目标找到高级路径的方法，然后在高级路径上连续子目标之间的最短低水平路径。我们的方法是2012年基于网格的路径规划竞赛中的十个条目之一。在所有最佳路径计划者中，我们的方法是找到完整的路径最快，需要最少的内存。
Grids are often used to represent maps in video games. In this paper, we propose a method for preprocessing eightneighbor grids to generate subgoal graphs and show how subgoal graphs can be used to find shortest paths fast. We place subgoals at the corners of obstacles (similar to visibility graphs) and add those edges between subgoals that are necessary for finding shortest paths, while ensuring that each edge connects only subgoals that are easily reachable from one another. We describe a method for finding shortest paths by first finding high-level paths through subgoals and then shortest low-level paths between consecutive subgoals on the highlevel path. Our method was one of ten entries in the Grid-Based Path Planning Competition 2012. Among all optimal path planners, ours was the fastest to find complete paths and required the least amount of memory.