人群寻路和使用流场瓦片进行转向

介绍

使用流场图块进行人群寻路和引导是一种解决在海量地图上移动数百到数千个单个代理的计算问题的技术。通过使用动态流场图块，可以实现更现代的转向管道，具有避障、植绒、动态编队、人群行为和对任意物理力的支持等功能，所有这些都无需为每个智能体重复重建单个路径的沉重 CPU 负担。此外，尽管路径复杂，代理仍会立即移动，从而为 AI 和玩家提供即时反馈。

动机

在制作《最高指挥官2》时，我们被赋予了改善运动和寻路行为的任务。与许多有寻路游戏一样，最高指挥官中的每个单位都会沿着固定的单向 A* 路径移动。最终，单位会与其他单位发生碰撞，尤其是当他们编队移动或进入战斗时。当路径交叉且单元发生冲突时，现有代码将停止单元并等待冲突解决，而不是围绕障碍物重建新路径。这是因为每次发生碰撞时重建路径都会变成一个复杂的问题，尤其是在大型战斗中，新路径可能会导致第二次和第三次碰撞，导致游戏停止。这种行为在一千个单位中重复出现，其控制玩家都在疯狂地点击对方的单位，本质上是乞求它们相互冲突和碰撞。
为了克服这个路径重建问题，所有运动都被设计成倾向于保持在同一路径上，导致物理、编队、AI、命中反应等受到限制。通过这种方式，寻路限制了整个用户体验。
由于最高指挥官的单轨寻路解决方案，玩家会在地图上移动时照顾他们的单位。他们会花时间观看和点击，观看和点击，所有这些都是为了帮助他们的单位应对游戏中不断变化的障碍和环境。

世界分区

在最高指挥官 2 引擎中，世界被分解为包含网格方块的各个区域，其中每个网格方块为 1 × 1 米，每个扇区包含 10 × 10 个网格方块。还有门户窗口，其中每个门户窗口跨越扇区边界。图 23.1 显示了一个示例。

在图 23.1 中，扇区通过可路径的门户窗口连接。门户窗口的起点和终点位于扇区边界两侧的墙壁处。每个窗口侧都有一个入口，每个入口中心是 N 向图中的一个节点，其边连接到可路径的相同扇区入口。

三种场类型

对于每个 10 × 10 m 网格扇区，该算法使用三个不同的 10 × 10 m 2D 数组或数据字段。这三种字段类型是成本场、积分场和流场。成本场存储每个网格方块的预定“路径成本”值，并在构建积分场时用作输入。积分场存储每个网格位置的积分“目标成本”值，并在构建流场时用作输入。最后，流场包含路径目标方向。以下各节将更详细地介绍每个场。

成本场

成本场是一个 8 位字段，包含 0–255 范围内的成本值，其中 255 是用于表示墙壁的特殊情况，1-254 表示遍历该格网位置的路径成本。不同的成本可用于表示斜坡或难以通过的区域，例如沼泽。每个网格位置的成本场至少具有一个成本;如果该位置有额外的费用，则会将其添加到一个位置。

如果 10 × 10 m 扇区清除了所有成本，则引用填充 1 的全局静态“清除”成本场。这样，您只需将内存成本在包含唯一数据的成本字段上。在 RTS 游戏中，有数量惊人的透明扇区。在最高指挥官2中，由于开阔和平坦的陆地，湖泊和海洋的广泛区域，我们大约50-70%的可路径空间被标记为清晰。

成本场数据由我们的编辑器预先构建，它将墙和几何坡度转换为成本值。我们的设计团队还可以可视化此路径成本信息，并对其进行更改。

积分场

积分场是一个 24 位场，其中前 16 位是总积分成本成本，后 8 位用于积分标志，例如“活动泛洪”和“视线”。您可以选择成本更多内存以获得更好的流场结果，方法是使用 32 位浮点数作为积分成本，使其成为 40 位场。

流场

流场是 8 位场，前四位用作方向查找表的索引，后四位用作标志，例如“可路径”和“具有视线”。流场包含代理的转向管线用于绕过山丘和墙壁以流向路径目标的所有主要方向和标志。

路径请求

获得有效的目标位置和一个或多个源位置后，您可以创建路径请求。路径请求将首先通过门户节点图运行 A*。A* walker 从源位置开始，穿过门户节点，并在目标处结束，从而生成“下一个”门户节点的链接列表。此过程继续与下一个路径请求源一起，但这次门户步行者运行“合并”A*，其中步行者更喜欢停止并指向先前旅行的门户节点以与先前的 A* 结果“合并”。通过“合并”A*，您更有可能共享流场结果，并且源更有可能靠近在一起，这是选择多个源以朝着单个目标移动时所需的行为。
如果您的 A* 目标路径成功，下一步是浏览下一个门户节点列表，并为每个门户节点提交流字段请求。此时，您已完成路径请求，并且由于您仅使用合并 A* 遍历了门户节点图，因此您使用的 CPU 非常少。

积分器

我们将积分器定义为负责接收单个流字段请求并在一个或多个即时报价上构建单个流字段图块的类。这是通过将请求的成本字段数据以及请求的“初始泛洪”作为输入来实现的。初始泛洪是目标位置的列表，每个位置都有一个预定的综合成本值。
积分器采用初始泛洪并使用 Eikonal 方程向外积分 [Ki Jeong 08]。可视化触摸静水的效果，产生在水面上移动的涟漪波浪。积分器的有源泛洪在路径表面上的移动方式类似，同时在积分场中设置越来越大的积分成本值。它重复这个过程，直到活跃的泛洪通过撞到墙壁或该部门的边界而停止移动。为了更好地理解积分过程，让我们回顾一下积分器的积分步骤。

1：重置积分场

积分器的第一步是重置其积分场值并应用初始目标泛洪。如果请求的流场具有最终的 1 × 1 目标，则其初始目标泛洪是具有零积分成本值的单个 1 × 1 位置。但是，如果流场请求来自 10 × 1 或 1 × 10 门户，则将有 10 个目标位置，其中包含 10 个不同的综合成本目标。
为了获得更高质量的流场结果，您可以在入口路径中积分至少一个前方的流场。然后，您可以将先前积分的成本结转为初始门户窗口成本，而不是使用零，从而有效地实现跨境流动。这种质量改进的代价是使流瓦依赖于顺序，因此更难被其他路径请求重用。

2：视线通行证

如果我们从实际路径目标进行积分，那么我们首先运行视线（LOS）通道。
我们这样做是为了在路径目标附近拥有最高质量的流动方向。当代理处于 LOS 内时，它可以完全忽略流场结果，而只是转向确切的目标位置。如果没有 LOS 通道，由于积分器只查看四个上、下、左和右邻居，因此您可以在目标周围拥有菱形流向。
通过在成本积分传递期间查看所有八个相邻要素，可以改善围绕目标的流程，但我们不建议这样做;标记 LOS 很低性能需求，并且在 LOS 内时，您可以通过完全忽略流场来获得最高质量的路径方向。
要积分 LOS，您需要像往常一样积分初始目标泛洪，但是，与其比较成本场邻居成本来确定积分成本，只需在移动泛洪时将泛洪成本增加 1，同时将位置标记为“有视线”。这样做，直到泛洪击中任何成本大于 1 的东西。
一旦我们击中了成本大于 1 的东西，我们需要确定该位置是否是 LOS 角落。我们通过查看该位置的邻居来做到这一点。如果一方的成本大于另一方，而另一方没有，我们就有一个LOS角。
对于所有LOS角，我们从网格正方形的外边缘位置开始，在远离目标的方向上构建一条2D线。使用 Bresenham 的线算法在网格上跟踪这条线，将每个网格位置标记为“泛洪阻塞”，并将该位置放在第二个活动泛洪列表中，以便稍后通过成本积分传递使用。通过将每个位置标记为“泛洪被阻挡”，LOS 积分泛洪将沿着标记目标可见边缘的线停止。
您可以通过在门户窗口位置沿用“视线已遮挡”和“泛洪被阻挡”标志来跨越扇区边界。然后，当您构建邻居的积分字段时，对于具有“泛洪被阻止”标志的每个门户窗口位置，将其视为目标的 LOS 角，并相应地构建线的其余部分。这将使LOS跨越部门边界无缝衔接。
继续向外移动 LOS 通道泛洪，直到它通过撞到墙壁或具有“泛洪被阻止”标志的位置停止移动。除了使用布雷森纳姆的直线算法所成本的时间外，LOS第一次通过非常低性能需求，因为它不考虑相邻的成本值。泛洪只是设置标志，偶尔检测角落并迭代一条线。
图 23.2 显示了 LOS 通过的结果。每个清晰的白色网格方块都被标记为“有视线”。每个 LOS 角都有一条线，其中与该线重叠的每个网格方块都标记为“泛洪阻塞”。

3：成本积分通行证

我们现在已准备好进行成本字段积分。与LOS通道一样，我们从活动泛洪列表开始。此活动泛洪来自上一个 LOS 通道的“泛洪被阻止”位置列表。通过这种方式，我们只积分从目标中看不到的位置。
我们将这个泛洪整合出来，直到它通过撞墙或扇形边界停止移动。在每个网格位置，我们通过添加最低性能需求的成本字段和积分成本字段的上、下、左或右邻居来计算积分成本。然后一次又一次地重复这个Eikonal方程过程，将泛洪向外移动到每个位置的非积分，非壁邻居。
在积分过程中，请注意由于成本差异较小而重叠的先前积分结果。要解决这种代价高昂的行为，请确保您的泛洪在达到先前的积分结果时停止，除非您的积分成本确实存在显着差异。如果你不这样做，你就有可能让泛洪来回反弹，在不必要的时候吃掉结果。换句话说，如果采用不同的路径稍微低性能需求一些，那么不要为了节省那很小的寻路成本差异而费心回溯整个领域。
以下示例说明了何时适合重叠以前积分的成本结果。假设一条路径分成两条路径，其中每条拆分路径通向相同的目标位置。然而，一个裂缝有一个长而昂贵的沙坑，而另一个则没有。整合泛洪将远离目标，一分为二，并在路径的起点相互汇聚。当它们相遇时，更低性能需求的泛洪将与更昂贵的泛洪的结果重叠并继续积分，回溯昂贵的路径，直到更低性能需求的积分成本与先前的积分成本没有显着差异。这种回溯行为将产生将流场方向从沙坑重定向回更低性能需求的路径的效果。这与 A* 中的回溯没有什么不同;指出这种行为是件好事，因为在积分字段时成本更高。

4：流场通道

现在，我们已准备好从新创建的积分字段构建流字段。这是通过迭代每个积分成本位置并写出LOS标志或比较所有八个NW，N，NE，E，SE，S，SW，W邻居来确定我们应该为该位置采取的“最低性能需求”方向来完成的。

图 23.3 显示了最终流场方向的样子。请注意，对于具有目标 LOS 的位置或清除图块内的位置，未执行任何工作。构建流字段后，我们将其提交到流字段缓存中。

流场缓存

流字段缓存包含我们构建的所有流字段，每个流字段都有自己唯一的 ID，具体取决于它们引导您完成的门户窗口。通过这种方式，尽管具有不同的目标，但可以在路径请求之间共享工作。

如果地图中存在双向走廊，则多个路径需要相同的走廊流场结果的可能性很大。还可以跟踪流字段的引用，因此当不再有对它的引用时，可以丢弃它或将其放在计时器上以便稍后丢弃。您还可以预构建所有流域排列并将其存储在磁盘上，以便只需构建具有自定义 LOS 目标信息的流域。

支持动态环境和查询

发明这项技术的全部意义在于更好地实时处理游戏环境的动态性质。为此，我们在构建所有内容时都考虑到了动态变化。
如果代理的位置移动到计划路径中的扇区之外，我们可以通过跨门户节点运行另一个“合并”A* 来轻松支持移动源。
我们通过重建目标的流场来支持移动目标。如果目标越过扇区边界，则会在后台重建路径的门户节点。新路径请求的大多数流域都已构建并位于缓存中，因此需要重建的流域很少。新路径准备就绪后，代理将从旧路径无缝切换到该路径。
我们通过将包含墙壁和山丘的部门的成本字段及其相关门户标记为脏来支持更改墙壁和山丘。然后，为位于脏扇区边界及其邻居边界的节点重建门户图。最后，将重新生成受这些更改影响的路径。
所有这些都是通过将事物标记为脏并根据优先级队列重建它们来完成的，其中队列中的每个项目都有一个固定毫秒数的时间片。这使我们能够控制重建的内容、时间和方式随时间推移而发生。

成本戳支持

成本戳表示一组自定义成本值，您可以“标记”到世界中。在《最高指挥官2》中，我们需要放置具有自定义墙壁和自定义可路径区域的建筑物。玩家基本上可以通过使用不同大小的结构（包括 1 × 1 个网格墙）来绘制全新的路径景观。
成本标记记录原始成本字段值，然后再将其替换为一组新的成本。在放置成本标记后，重叠的扇区将被标记为脏扇区，动态图形和路径重建过程将处理其他所有事情。

源成本数据

地图编辑器将通过查看几何图形来构建成本字段数据，并在适当的情况下放置墙壁和山丘。我们将运行模糊通道，在墙壁附近添加成本梯度，以改善沿着走廊和锯齿状边缘周围的流动结果。
所有成本数据也显示在编辑器中，以便设计人员可以根据需要手动添加和删除路径成本。这对设计团队来说是一个巨大的好处，因为他们最终可以控制单位在地图上移动的位置和方式。

不同移动方式

最高指挥官 2 引擎中的每个特工都有自己的移动类型。每种移动类型都有自己的成本字段数据，因此生成自己的门户图。这样，仅陆地坦克的路径将与可以在湖泊和沼泽上行驶的气垫船不同。
编辑器将为每种移动类型构建不同的成本数据。为了支撑大型单元，在地图上运行了一个特殊的墙壁缓冲过程，将墙壁向外移动。这起到了关闭对大型单元来说太小的细缝的效果，以及推出墙壁和山侧，因此大型单元在靠近时无法在视觉上重叠它们。
如果用户选择具有不同移动类型的单位，例如喷气机中队、一些陆地坦克、一些气垫船和一个超大型实验机器人，游戏将对所有兼容单位使用“最严格的运动类型”路径，然后再为不兼容单位构建更多路径。

流场转向

当代理使用流场进行引导时，需要注意一些 if-else 条件。对于初学者来说，如果代理没有有效的流字段，它应该转向下一个门户位置。一旦代理有了流场，它应该寻找一个 LOS 标志来引导其目标;否则，它应使用指定的流场方向。
当代理接收新的流场方向时，我们建议存储路径方向向量，并在穿过网格正方形时混合新的流向。这具有在代理遍历流场时平滑流场方向的效果。

墙壁和物理

借助流场，您的寻路代理可以向任何方向移动，而无需重建其路径的高额费用。一旦您的代理向任何方向移动，他们必然会碰壁或其他代理。在最高指挥官2引擎中，特工可以互相推动，也可以使用物理原理沿着墙壁滑动。
在我们的游戏中使用物理特性允许新的游戏场景，例如推退单位的爆炸或可以推退一百辆坦克的超大型机器人。我们有一个可以在地图上任意推动或拉动单位的结构，以及一个可以将单位吸入旋风中的大型单位，将它们旋转，直到它们撞在一起。如果没有与使用流场图块相关的更低性能需求的移动成本，这些新的游戏场景是不可能的。

岛屿流场

可以实现包含岛屿 ID 的可选岛屿字段类型，其中每个岛屿 ID 表示单个可路径岛屿。想象一下夏威夷的不同岛屿：如果你在一个岛上，你只能开车到同一个岛上的位置。
对于每个航段，您存储其岛屿 ID。如果扇区中有多个岛 ID，则该扇区将有一个岛字段将 ID 分解为各个格网位置。使用此信息，您可以快速确定路径请求是否有效。
在最高指挥官 2 引擎中，您可以将鼠标移动到地图上的任何位置，并看到鼠标图标从箭头变为停车标志，指示您无法到达该位置。此功能是通过检索源位置和目标位置的岛屿 ID 以查看它们是否匹配来实现的。

最小化 CPU 占用空间

您可以通过限制每个时钟周期承诺的图块或网格方块的数量来强制降低 CPU 使用率。您还可以轻松地跨线程分散积分工作，因为积分字段内存与其他所有内存是分开的。

未来工作

以下是进一步改进此技术的想法列表。

通过跨重叠扇区连接门户图节点来支持 3D 空间。
预处理和压缩所有流场排列并从磁盘流式传输它们。
通过使用扇区层次结构和 N 路图添加对任意大小地图的支持。
使用 GPU 而不是 CPU 构建流场 [Ki Jeong 07]。
支持多个目标。多个目标流场非常适合追逐英雄的僵尸。

结论

我们在《最高指挥官2》上的工作表明，超越基于单一路径的解决方案，开始寻找基于现场的解决方案，以支持RTS游戏中有数百到数千名代理的动态人群路径和转向，这是有利的。在本文中，我们演示了如何表示和分析可路径地形，以生成可以驱动数百个单位实现目标的流场。此外，我们表明，与单个单元路径查找请求相比，这种方法在计算上是低性能需求的，即使在面对动态地形和查询时也是如此。希望你能从我们在《最高指挥官2》引擎方面的经验中受益，并在下一款游戏中继续扩展和完善基于野外的寻路。
工具书类

[Ki Jeong 07]W.Ki Jeng和R.Whitaker。“用于并行的快速Eikonal方程求解器

SIAM计算科学与工程会议，2007年。

[Ki Jeong 08]W.Ki Jeng和R.Whitaker。“Eikonal方程的快速迭代方法”，SIAM科学计算杂志30（5），2008