Improved Heuristics for Optimal Pathfinding on Game Maps
- tag：路径规划启发式
文章目录
- Improved Heuristics for Optimal Pathfinding on Game Maps
-
- Abstract
- Introduction
- Improved Heuristics
-
- Dead-End Heuristic
- Gateway Heuristic
- Decomposition Algorithm
- Empirical Evaluation
- Conclusions
Abstract
随着计算机游戏世界变得越来越复杂，寻路性能瓶颈也变得越来越明显。通常用于指导基于 A? 的寻路的启发式函数过于简单，无法在如此复杂的大型游戏世界中为搜索提供必要的指导。这可能会导致 A? 搜索为了在两个遥远的地点之间找到一条路径而探索整个游戏地图。
本文提出了两种有效的启发式方法，用于估算大型复杂游戏地图中不同地点之间的距离。前一种启发式，即死胡同启发式，可以从搜索地图中剔除与当前查询无关的区域，而第二种启发式则使用所谓的网关来改进其估计值。在实际游戏地图上进行的经验评估表明，与标准的八分距离度量法相比，这两种启发式方法都能显著降低 A? 搜索的探索复杂度和时间复杂度。
Introduction
现代计算机游戏世界的规模和复杂程度逐年增加，这既体现在地图的大小上，也体现在世界中存在的单位数量上。例如，在即时战略（RTS）游戏中，可能有数百个单位同时在世界中航行。为所有这些单位实时计算路径对计算要求很高，可能会消耗掉为游戏逻辑预留的大部分可用 CPU 资源。在 RTS 游戏中，寻路查询还用于回答计算机控制的人工智能提出的各种战略问题（例如，距离特定资源有多远，或敌人可以从哪里发动攻击）。因此，在现代游戏中，使用高效（并经过仔细实施）的算法进行寻路计算至关重要。A? 算法（Hart、Nilsson 和 Raphael，1968 年）是游戏寻路事实上的行业标准。虽然不同游戏的状态空间表示可能不同（网格或网状都很常见），但 A? 搜索或其变体通常是首选算法。通常使用简单有效的启发式来指导搜索。例如，在基于网格的地图中，通常使用八分距离（曼哈顿距离的扩展，允许对角线移动）。然而，随着游戏地图变得越来越大、越来越复杂，这种简单的启发式方法无法提供足够有针对性的指导，导致在两个遥远的地图位置之间寻找最短路径时，搜索经常会探索几乎整个地图。
克服这一问题的一种技术是分层寻路。这种方法不是只使用单一的状态空间表示法，而是同时使用更高层次的抽象表示法。层级结构中的每一级都会使用越来越抽象的游戏地图视图，随后可以使用更小的状态空间来表示。在回答寻路查询时，会在其中一个高层中找到近似路径（然后可能会在基础层中使用小范围局部搜索进行细化）。由于 A? 搜索的状态空间更小，因此处理速度更快。这种方法的主要缺点是返回的路径不一定是最优的。这是因为在抽象过程中，通常会丢失地图的一些细节。不过，如果路径只是略微次优，这通常对游戏性影响不大。幸运的是，大多数情况下都是如此。然而，随着地图上单位和其他动态障碍物数量的增加，路径变得严重次优的风险也会增加。这是因为在抽象状态空间中进行的搜索通常不会（也无法）考虑这些动态障碍。
我们在本文中提出的方法在减少状态空间探索的同时，还能考虑动态障碍。我们不是利用状态空间抽象来创建分层视图，而是利用它来提供改进的启发式函数，以指导常规 A? 搜索。我们面临的挑战是==如何设计出既能高效计算，又能大大改进搜索引导的启发式方法。==我们引入了两种这样的新启发式，它们都是可容许的，因此保持了最优性。
本文的主要贡献有
- 改进了用于指导（游戏）地图寻路搜索的可接受启发式方法–我们在实际游戏地图上的实验表明，使用新启发式方法进行的 A? 搜索，无论从节点扩展还是从总搜索时间来看，都大大优于标准的八邻域距离启发式方法；
2) 一种将游戏地图自动分解成较小区域的算法方法；该方法不仅有助于为我们的新启发式方法创建抽象视图，还有助于创建一般的分层寻路技术。
下一节我们将介绍新的启发式函数，并提供详细示例和伪代码。下一节将介绍自动地图分解，随后将总结利用真实游戏地图对启发式方法进行广泛实证评估的结果。最后，我们总结并讨论了未来的研究方向。
Improved Heuristics
图 1 中的地图描绘了一个典型的角色扮演游戏室内场景。这个世界由多个房间组成，房间之间通过门和走廊相连。最先进的游戏地图一般会更大更复杂，但为了便于演示，我们将使用图中的地图。
在地图上寻找两个遥远地点之间的最短路径时，基于八英里距离的天真启发式会或多或少地探索地图上的所有地点。这部分是由于它无法事先知道是否存在一条穿过任何给定房间的路径，可以通往到达所需目的地的捷径。为了更好地说明这一点，我们在地图上用深灰色标出了 A? 使用八分启发式在相距较远的两个地点之间寻找最优路径时探索到的所有地砖。最佳路径以深灰色显示，起点在左边，目标在右边。该算法花费了大量精力探索那些我们一眼就能看出不可能相关的区域，因为这些区域要么是死胡同，要么是明显劣质的路径。
本文提出的两种启发式方法的理念是通过事先识别并排除两个给定地点之间不可能在最佳路径上的所有区域（在我们的例子中是房间）来缓解这一问题。前者，即死胡同启发式，避免了通往死胡同的区域，而后者，即网关启发式，则更进一步，认识到穿过某些房间只能通往次优路径。接下来的两个小节将分别介绍死胡同启发式和网关启发式。启发式计算分为两个阶段。第一阶段是对地图进行预处理并创建抽象视图。具体方法是自动将地图分解成较小的区域，然后计算路径信息。这种计算是离线完成的，每张地图只需计算一次。在第二阶段，来自预处理阶段的抽象视图被用来为寻路搜索得出改进的启发式估计值。启发式是实时计算的，因此效率非常重要。
Dead-End Heuristic
死胡同启发式可以立即判断出搜索是否进入了一个最终通向死胡同的房间，也就是说，从这个房间没有通向目标的路径（除了从我们进来时的入口出去）。显然，我们没有必要探索这样的房间。
预处理阶段 预处理阶段分为两个步骤。第一步，将游戏地图分解成几个较小的区域，在本例中代表房间和走廊。在此地图上运行分解算法的结果如图 2 左侧所示。
这一阶段的第二步是构建一个高级图，用于表示不同的区域和它们之间的相互联系。图中的节点代表一个区域，节点之间的边代表两个相应区域之间的入口。请注意，连接同一两个房间的入口可能不止一个，因此图中连接一对节点的边也可能不止一条。因此，该图是一个所谓的无向多图。该图与区域信息一起存储在游戏地图中。
运行阶段 当地图加载到游戏中时，预处理阶段的数据也会随地图一起加载。这确实会导致一些额外的内存使用，但只要仔细实施，就能将内存使用量降到最低。
当我们收到寻路查询，要求找出起点和目标位置之间的最短路径时，会进行两次搜索。首先是在多图中进行搜索，以确定地图中与查询相关的区域子集；其他区域，即所谓的死胡同区域，可以完全排除在寻路搜索之外。让多图中的节点 S 和 G 分别代表地图中的起点和目标位置区域。我们在多图中搜索从节点 S 到节点 G 的所有可能路径，以确定相关区域。需要注意的是，在搜索过程中，我们需要标记所有已经访问过的边，以防止出现循环和其他重复搜索工作。事实证明，简单的深度优先搜索在这项任务中最为有效，这是因为多图非常小，而且我们必须找到所有可能的路径。
一旦我们确定了相关区域的子集，就会执行类似 A? 的常规寻路搜索。唯一不同的是，我们使用了一个改进的启发式函数，对于位于非相关区域的网格单元，该函数会返回一个无穷大的值。这样做非常有效。每个网格单元都标有所属区域（使用了几个额外的比特），因此我们可以在恒定时间内琐碎地询问该区域是否相关。死胡同启发式的主要优点之一就是计算效率非常高。
这种方法与分层寻路有着本质区别，因为我们并没有事先确定任何高级路径。例如，在分层寻路中，如果高层路径被动态障碍物阻挡，通常要到路径跟踪阶段才会被注意到，搜索可能不得不重新执行。而在我们的案例中，其他可能的路径都是开放的，如果存在另一条路径，A*搜索也会找到。
这种方法能否有效减少对状态空间的探索，在很大程度上取决于地图的结构。一方面，对于主要由通过相对较少的可能路径连接的区域组成的地图，这种简单的启发式方法有可能带来显著的改进。然而，可供选择的路径越多，启发式的效果就越差。例如，如果我们在示例地图的顶部房间开辟一条新的路径，那么死胡同启发式就只能从搜索中排除几个小区域。
此外，在自动分解地图时也需要小心谨慎，因为如果生成的区域太小，抽象多图就会变得很大。这样一来，多图搜索的开销就会变得很大。当然，在实时情况下，可以通过预处理所有相关的面积计算来避免这种开销，不过要付出额外的内存使用代价。
我们接下来介绍的启发式方法不存在上述问题。
Gateway Heuristic
网关启发式会预先计算区域出入口之间的距离。它也分两个阶段进行。
预处理阶段 地图分解成区域的方法与死胡同启发式相同。我们将区域之间的边界定义为网关（或大门）。网关的大小可以是任意的，但我们分解算法的一个缺陷是它的方向总是水平或垂直的。接下来，我们使用多次 A* 搜索来预先计算门之间的（静态）距离。对于每个网关，我们都会计算其与所有其他网关的路径距离（如果不存在路径，则成本为无穷大）。或者，我们也可以只计算每个房间内网关之间的距离，然后在运行时使用小规模搜索来累计总成本。不过，我们的方法能带来更准确的启发式估计和更快的运行时间访问（当然，代价是额外的内存）。
我们的方法的一个重要元素是为每对网关存储四种不同的成本。每个关口都是双向的，因为我们想知道从关口出发和到达关口的每种可能性的不同距离。与只计算一个成本值相比，这能在运行时大大提高启发式估算的准确性。因此，我们需要对每对闸门进行四次单独的预计算寻路搜索（这是离线完成的，因此额外的时间并不重要）。在这些寻路搜索中，我们不允许通过出发和到达的闸门。
运行阶段 运行阶段是使用下面启发式函数的常规 A* 搜索：
启发式 hl(n, G) 计算网格单元 n 到门 G 中最近点的八分距离。这可以简单地计算为一个点到水平线/垂直线的距离。术语 H(Gi, Gj) 代表预先计算出的闸门 Gi 和 Gj 之间的最短距离（实际上，我们还必须通过闸门方向，但为了清晰起见，我们在这里省略了这一点）。我们需要查看当前区域的所有大门，并将每个大门与目标区域的所有大门进行比较，然后取最小成本。
网关启发式的准确性和计算效率与网关总数无关（尽管会影响内存使用）。启发式估算的计算效率主要受我们所经过区域，尤其是目标所在区域的门数量影响。这是因为在每个状态下，我们都会在所有门对中选择最小估计距离，前一个门在当前房间，后一个门在目标房间（见启发式函数方程）。另一方面，启发式的准确性受到两方面的影响：房间的形状和各个门的大小。由于我们使用八分启发式来估计当前状态（和目标）到最近的门的距离，因此很容易出现八分启发式带来的低估误差。不过，由于估算的距离通常较短，这些低估误差不会对整体距离估算产生重大影响。此外，我们的区域分解算法倾向于将地图分割成凸面区域，而八分启发式会在这些区域内给出准确的估计值。另一种低估与门的大小有关。在计算从一个州到一个门的距离时，我们总是使用门上最近的点来确保可接受性。这并不一定是我们在闸门距离预计算中使用的同一个闸门点。这两点之间的距离是造成低估的一个原因。闸门越大，这两点之间的距离就越远。
Decomposition Algorithm
将地图划分为区域的算法是一种洪水填充算法。该算法无需输入边界，而是在遇到满足特定条件的地块时自动建立边界。该算法无需输入任何其他信息，只需输入基于地砖的地图，以及每个地砖是否可通行的信息。输出是每块瓦片的信息，说明它属于哪个区域（或无法通过）。
分解方法的伪代码如算法 1 所示。在创建区域时，算法首先找到最左上方可通行且尚未分配到区域的瓦片。从该瓦片开始，算法开始向右填充，直到填充到非空闲瓦片为止。之前分配的瓦块和无法通过的瓦块都被视为非空闲瓦块（第 9-15 行）。然后，算法开始下一行，使用与右侧类似的停止标准尽可能向左选择一个起点（第 27-36 行）。然后再开始向右填充，重复上述过程。
该算法会检测一行之间的左右边界是扩大还是缩小（第 17-26 行和第 37-42 行）。如果边框在缩小后重新增长，该区域的填充就会停止（可能需要撤销最后一行的填充（第 20-24 行））。
图 4 举例说明了分解算法的工作原理。左上方的图片显示的是一张未分割的地图，右边的图片中已经开始了洪水填充。第四行已经停止，因为该区域向上打开。在这种情况下继续前进是不明智的，因为这条线将直接穿过另一个潜在区域。这就是算法第 12 行的停止条件（(x + 1, y - 1) 6= f ree）。在左下方的图片中，算法已经完成了对区域的填充。在紧接着区域下方的一行中，算法有机会将区域向右扩展。但是，由于区域已经从右侧开始缩小，而且禁止再生长，因此区域填充停止。这就确保了区域具有相当规则的形状。在最后一张图片中，又有两个区域进行了类似的填充。
Empirical Evaluation
我们在计算机游戏地图上运行了新的启发式方法，评估了这些方法的有效性，这些地图既有我们自己制作的，也有从流行的商业角色扮演游戏中提取的。所有实验均在 3.0 GHz CPU 个人电脑上运行。
表 1 显示了我们的寻路实验结果，其中对 octile 和两种新启发式方法进行了比较。在每张地图上，使用随机选择的起点和目标位置进行了 1000 次搜索。上半部分包括搜索我们的演示地图（图 1）所获得的实验数据，中半部分包括搜索热门游戏《光头之门 II》中九张不同地图所获得的数据（图 5）。在最后一部分，我们分别展示了同样来自《博德之门 2》的一个特别大的游戏地图的数据（图 6）。水平和垂直移动的成本为 100，而对角线移动的成本为 150。
在所有类型的地图中，新启发法在节点扩展数量和总运行时间方面都明显优于标准八进制启发法。总的来说，网关启发式是最好的。我们还可以看到，计算死胡同启发式的时间开销几乎可以忽略不计，因为节省的时间与节省的节点数大致相当。这是因为多图路径是预先计算好的。对于网关启发式而言，节点的减少尤为显著。然而，搜索时间并没有随着节点数量的增加而相对减少。这是由于新的启发式函数比计算八分距离复杂。尽管如此，所节省的时间还是相当可观的，而且在精心实施后还能进一步提高。
我们还有兴趣仔细研究启发式方法在较长的路径上的表现。前 10%部分给出了长于平均路径的结果（我们为每张地图随机生成了 10,000 条路径，其中包括最长的 10%）。现在，新启发式方法的性能提升更为显著。我们还想看看网关启发式估计值与真实路径长度的接近程度。
Conclusions
我们提出了两个新的可接受启发式函数，用于指导大型游戏地图寻路中的启发式搜索。这些启发式方法的初步结果很有希望。这两种启发式方法确实优于大多数现代游戏中使用的标准技术。不过，在得出任何具体结论之前，我们希望在更多地图上进行更全面的实验评估。很明显，随着游戏地图的不断增加，像这里讨论的启发式方法将变得非常必要。
我们在实施方面仍有改进的余地，也许更重要的是，在改进启发式估计方面也有改进的余地。关于如何继续这项研究，我们有几个想法。其一是进一步研究区域分解算法，使其更好地适应各种不同类型的地形。