在过去的5年中，我（作者）一直致力于改进RTS风格的游戏The Maestros中的分组单位移动。正如大约20年前Dave Pottinger 在他的“帝国时代”（Age of Empires）工作时所指出的那样 ，运动中的“寻路”这部分内容引起了所有人的注意，但使得数十个单位有智慧地走上一条道路的确重要且相当困难。我很想告诉你关于我在这个领域的旅程。

接下来的决不是最先进的解决方案。二十多年来，这个行业在这个问题上有非常出色的想法，你和我都没有希望紧跟时代的步伐。因此，让我们专注于在实际的游戏约束条件下为玩家制作基本路径的基本细节。我们假定了你拥有3D数学的实际知识，并不需要你有博士学位。说实话，我可能会让你心烦意乱;）

本文翻译自https://www.gamasutra.com/blogs/AndrewErridge/20180522/318413/Group_Pathfinding__Movement_in_RTS_Style_Games.php

目标

在RTS运动中，一些玩家需要象Company of Heroes（英雄连）那样的逼真，缓慢旋转的坦克和步兵小队。我们的游戏是在快速战斗中执行大型游戏，因此我们的优先事项是“响应超越现实”，以及“对协调阵型的直接控制”。比起帝国时代更像星际争霸。

我们开始的地方

UDK（虚幻引擎3的SDK）在基于导航网格的空间中支持A*路径查找，并且具有相当有效（如果很挑剔）的导航网格生成。不幸的是，寻路几乎完全是在不可修改的引擎代码中实现的，我们无法在UDK中修改它。总而言之，如果我选择了一个单位并右键点击一个可抵达的位置，我可以期待它最终到达那里。虽然UE4提供了更好的低级访问，但Unity和UE4今天的支持水平大致相同。我认为我们已经很好地覆盖功能了。伙计，我错了。

问题1 - 停止组

下一步是移动一个组。如果我选择我们的几个Doughboy单位并要求他们移动到完全相同的位置，那么他们中只有一个会实际上在那里。 最好的情况是，其他人将与那个制作它的人相邻。那么他们怎么知道他们什么时候完成了移动？ 才走了两步，我们就遇到了我们的第一个问题！

我们想到的解决方法是一种消息传递系统。到达那里的第一个人被设定为已经到达了目的地，任何碰到他的并且也想去同一个地方的人，也会认为自己到达了目的地。然后那些人可以将这个信息传递给任何碰到他们的人。 我们称之为“传递性碰撞”。这种感觉非常聪明，并且适用于聚类组，但仍然有一些愚蠢的退化情况（例如，如果单元排成一行）。

问题2 - 穿越人群

我们早期遇到的另一个问题是一个单元被另一个单元阻塞。尽管UDK的寻路支持在navmesh中创造新的障碍，但为数百个不断改变其位置的单位进行这项工作导致了无法游戏的表现。因为如此，单位总是试图穿过彼此而不是周围的空隙。

我们的解决办法是允许单位们在某些条件下相互施加推力。这也需要像我们的停止消息一样在整个组中传播。

一个更自然的解决方案可能是告诉单位将他们自己移开（星际争霸2），然后将自己移回去。在任何一种情况下，确定“推”另一个单位的确切状态/条件都非常复杂且容易出错。 “你可以推动盟军，但不是敌人，空闲单位而不是攻击单位。”在我们的例子中，它采用了大约10个独特的子句以及不同级别的嵌套来实现。哎呀！我很想在这里找到更通用的解决方案。

问题3 - 留在你的车道

在2014年我们在GDC首次公开演示The Maestros之后，我收到了一位来自我的导师的反馈，指出游戏感觉“混乱”。当时有很多事情对此产生了影响，但最大的问题是即使是简单的直线运动，也有单位在同一条路线上争夺位置。 没有人会期望现实生活中的人群这样做，当然也不是一群受过军事训练的机器人。我们所有的单位仍然完全独立行事。当他们从一名玩家的点击中收到一个单一的共同目的地并试图以他们自己最快的路线到达那里时，他们通常会选择与他们旁边的人一样的路线。结果就像405高速公路的所有8车道一样优雅，瞬间倒塌成一条车道。

解决这个问题的一般办法并不难。计算当前组的中心点，从该中心点获取每个单元位置的差异，并为每个单元发出一个定制的移动命令，并使用它们与目标的偏移量。

对于单元A，B和C以及点击的位置（红色十字线），对目的地进行偏移

这对于将单位集群从一个开放区域移动到另一个开放区域的基本情况非​​常有用，但正如您将在本文中开始学习的那样 - 大多数“一般”感觉解决方案都具有分解的条件。最明显的是如果你尝试移动到障碍旁边。正如你在下面看到的，中心点是好的，但是单元C会在巨石（灰色框）内。

另一个问题是，如果你的单位分散开来，你在中心附近点击，你会期望它们向内聚拢。然而，使用纯粹的偏移，他们通常会保持距离。如果你的单位太分散，目的地的偏移也不能达到预期。例如，你的所有部队都在一个集群中，但是你的指挥官（A部队）单独离开了2个屏幕。当你移动到集群中心附近的一个点时，你会希望你的所有单位，包括你的指挥官，最终都会落在你的光标下面（红色十字线）。事实上，如果你纯粹地应用偏移，它们都不会在你的光标下停止。

用一句话总结许多问题，“有些情况下，一些或所有单位应该聚集在一起，而不是维持它们与组织中心的偏移。”确定谁是否在一个组中的想法听起来有点令人生畏，当然，有一些复杂的聚类算法，可以在这里应用。我对这个问题的解决方案最终变得简单得多，并且在大量场景中出乎意料地有效。 这里是简介：

从我们的代码中借用词汇，我计算了该组的“SmartCenter”

• 计算组中所有单位的平均位置
• 移除任何不在该平均值的1个标准差内的单位
• 重新计算该组的子集的平均位置

如果我们试图达到的点在中心点的标准偏差范围内，我使用纯粹的独立运动。 这就保证了单位将紧紧地聚在一起，并且让玩家能够在The Maestros中以我们期待的形式直接控制单位们的组形态。

如果我没有找到一个有意义的“主要聚集（Primary Cluster）”，那么我的单位可能分布在整个地图上，在这种情况下，我只是希望他们尽可能地重组。纯粹的独立寻路的另一个胜利。 这是我在组的标准偏差大于特定的最大值时发现的。理想情况下，该最大值相当于该小组占用的面积，因此我使用所有单位半径的总和作为最大值。这是相当有效的。

如果我有一个“主要群集”，但有一个或多个单位与组中心的偏差超过1个标准差，我通过给他们一个偏移方向（即正常）的目的地，但离集团中心目的地的长度（即大小）为一个标准的偏差的长度。这具有“倒塌”的效果，并且感觉更自然。

问题4 - 粘在一起

在直线移动时，总体上对每个单位的目的地应用相对偏移对于我们游戏内的移动“简洁度”来说是巨大的胜利。尽管如此，绕过障碍仍然很糟糕。首先，单位将围绕障碍物走自己最短的路线，并不总是与团队团结在一起。 其次，我们的8车道至1车道的交通堵塞在我们到达目的地之前的每个中间点再次发生（见第二幅图）。

没有一起寻路

在中间点上交通堵塞

我没有一个好的答案就坐在这个问题上很长时间了。在第一天，我想选择1个单元的路径，并将偏移应用到每个中间点。当你认为你解决的首要问题是你的寻路紧紧盯着一个障碍时，这个算法很快就会崩溃。应用偏移量会让你的单位中有50％试图进入岩石路径，并且纯粹的独立寻路将导致永久性的僵局，甚至在你接近最终目的地的时候。

我对这个挫折的概念答案也不是非常聪明（如下所示）。我会将路径从角落移开，大约一个半径宽度。另一方面，从数学角度确定这一点证明对我来说是难以置信的难以捉摸。我如何确定我的路线是靠近障碍物还是偏远？如果我接近，我左边还是右边有障碍物？在我的道路上的某个点上，我的左边或右边的坐标轴是什么？

在某些时候，我将不得不进行光线投射来定位障碍物体积。也许我可以在每个点周围放射状投射（如下图所示）？不幸的是，它很容易完全错过障碍。这个解决方案的准确性直接与我在路径上每点所做的光线投射数量成正比，而且这种效果非常低效。

我真正需要的是给定转角的左右轴，假说是转弯的角度告诉你你的障碍可能在哪里。我的大部分障碍将直接进入我的载体的“肘部”，偶尔会在它外面。 当我通过以下操作找到轴时，我遇到了突破：

• 为点之间的相对运动生成矢量 - 对于每个寻路点B，减去其前驱A，从A→B得到矢量

对于每对随后的向量，A和B，添加它们以获得从A的开始到B的结束的向量C

用上/下矢量交叉C得到矢量P，该矢量平分A和B之间的区域。

向量P是轮到我的右/左轴！我检查两侧的障碍物，并将我的寻路点从障碍物移开大于标准偏差一点。结果从直接在我的障碍旁边得到一个舒适地偏离它的路径（绿色）。

之前

之后

现在，我可以沿着我的路线在更新的点上应用我的偏移，这样我的团队就可以在路径上粘在一起，并且不会堵塞交通堵塞。它并没有涵盖所有情况，但在约90％的情况下，我们可以在没有交通阻塞的情况下获得。改善是巨大的。 这是一个转角的前后对比。

之前

之后

学习收获

我最大的收获是，像A *这样的“广义”寻路算法不太可能成为你游戏的整个运动指导，尤其是如果你想要一个协调的团队的运动。我学到的第二件事是复杂性在这里是真正的敌人。寻路并不困难，因为寻路算法很复杂。紧凑的A *实现很容易少于100行可读代码，并且对于大多数游戏来说都是完美的服务。寻找路径很困难，因为实时的和空间相互移动多个单元会产生令人难以置信的大量情景，而且人们对于很多情况下应该发生的情况具有非常特定的期望。

评论

Robert Basler：RTS小组运动是一个棘手的问题。我在Miranda的工作时发现的继续BOIDS的工作的GDC论文对于RTS单元群体的一般移动情况非常有帮助。http://www.red3d.com/cwr/steer/gdc99/ 这里有更多关于RTS单元移动的链接：http://onemanmmo.com/index.php?cmd=newsitem&comment=news.1.179.0

Marco Castorina：我已经研究了一段时间的寻路和路径，我仍然觉得这个主题很迷人，谢谢你分享你的发现！我没有看到你提到的另一种经常使用的方法Geraerts和Overmars的走廊映射。它在清除角落的情况下可能特别有用：https://www.researchgate.net/publication/224705309_The_Corridor_Map_Method_Real-Time_High-Quality_Path_Planning 和 https://pdfs.semanticscholar.org/a921/86a365a2e5c407f98efdbd95cf412f91a6e5.pdf

翻译后记

一个月前在Gama上看到的文章，感兴趣，但是没卯月啊，又不开发RTS游戏，也不开发moba游戏。直到最近（准确地说是月初），因为要坐火车，下了开罗的赛车物语，玩的时候就想着，我靠这个赛车的AI是怎么构建的呢，感觉赛车在赛道上飞驰，需要一种很特别的寻路算法啊。然后，灵光一现，好像，好像这个文章以及其引用的boids好像可以用到的样子，就翻译了一下文章，好好看看。

实际上，本文的精彩部分不在于作者解决问题的结果，反倒是作者遇到的各种复杂的问题场景才是真正值得借鉴的。