编程文汇

游戏中的AI:新手完全手册(中)

移动和导航

在我们之前的例子中,我们要么有一个简单的桨,我们告诉它向左或向右移动,或者是一个守卫,被告知巡逻或攻击。但是,我们究竟如何处理代理人的移动?如何设定速度,如何避开障碍物,以及在如何规划不能直线到达的路线?现在我们来看一下。

转向

在基础层面上,为每个角色赋一个速度值是很有意义的,速度值包括了移动的速度和方向。这个速度可以用米/秒,英里/小时,像素/每秒等来衡量。回想一下我们的Sense / Think / Act循环,我们可以想象Think部分可能会选择一个速度,然后Act部分将该速度应用于角色,让它在游戏世界中到处移动。游戏通常有一个物理系统来干这个事,它检查每个实体的速度值并相应地调整位置,这样就可以将这个工作委托给物理系统,AI只需要决定角色的速度。

如果我们知角色希望走到哪里,那么我们将会用速度把角色向该方向移动。非常简单,我们有这样的等式:

desired_travel = destination_position - agent_position

因此,想象一个角色处于2D世界的(-2,-2),目的地大致在东北方向(30,20),角色到达那里的所需行程是(32,22) 。假定这些位置以米为单位 —— 如果角色人每秒可以移动5米,那么我们会将我们的行程向量缩小到那个大小,可以得到一个大致的速度(4.12,2.83)。使用该设定,用这个速度进行移动,正如我们所期望的那样,代理将在8秒后到达目的地。

可以随时重新运行计算。例如,如果上面的代理程序是目标的一半,那么所需的行程将是长度的一半,但是一旦缩放到代理程序的最大速度5 m / s,速度就会相同。这也适用于移动目标(在合理范围内),允许代理在移动时进行小的修正。

通常我们想要比这更多的控制 - 例如,我们可能想要在开始时缓慢地提升速度以表示从静止状态移动到步行然后再到跑步的人。我们可能希望在另一端做同样的事情,让它们在接近目的地时减速停止。这通常由所谓的“ 转向行为 ”来处理,每个行为具有特定的名称,如Seek,Flee,Arrival等。这些的想法是,基于将代理的位置和当前速度与目标位置进行比较,可以将加速力应用于代理的速度,以产生朝向目标移动的不同方式。

每种行为的目的都略有不同。Seek and Arrive是将代理移动到目的地点的方式。障碍避免和分离帮助代理人采取小的纠正动作来绕过代理人与其目的地之间的小障碍物。对齐和凝聚力使代理人一起移动以模拟植绒动物。可以将任何数量的这些不同的转向行为加在一起,通常作为加权和,以产生将这些不同的关注考虑在内并产生单个输出向量的聚合值。例如,您可能会看到典型的角色代理使用“到达”操纵行为以及“分离”行为和“避障”行为来远离墙壁和其他代理。这种方法适用于不太复杂或拥挤的相当开放的环境。

然而,在更具挑战性的环境中,简单地将行为的输出加在一起并不能很好地工作 - 也许它们会导致移动过慢的对象,或者当到达行为想要通过障碍物但是障碍物时代理会卡住避免行为正在推动代理人回归。因此,考虑转向行为的变化有时是有意义的,这些变化比仅仅将所有值加在一起更复杂。一类方法是考虑反过来 - 而不是让每个行为给我们一个方向,然后将它们结合起来达成共识(这本身可能不够),我们可以考虑转向几种不同的方式方向 - 例如8个罗盘点,

尽管如此,在一个复杂的环境中,我们还需要一些更先进的东西,我们很快就会遇到这种情况。

寻路

上节内容对于在开阔的区域(例如足球场或竞技场)中的简单运动非常有用,从A到B的主要是直线行进及避开障碍物的小幅修正。当到达目的地的路线比较复杂时怎么办呢?这就是需要“寻路”的时候了,它会检测当前地形并为角色确定一个达目的地的路线。

最简单的方法 —— 为附近的每个方格覆盖网格,检测允许进入相邻网格。如果其中任何一个格子是目的地,那么从后向前查找上一个网格,直至到达出发点,就是可行路线。否则,从先前的可达方格开始,重复之前的过程,直到找到目的地或走完所有方格(这意味着可达路径)。这种方法的正式名称叫做:广度优先搜索算法 (通常缩写为BFS),因为在向前移动搜索之前,它在每一步都查看所有方向(因此是“广度”)。搜索空间就像一个向前移动的波前,直到它到达正在搜索的地方。

下面搜索简单的示例。每个步骤都会扩展搜索区域,直到它包含目标点 - 然后跟踪返回到开始的路径。

pathfinding1.gif

结果是得到一个网格列表,它们构成了搜索到的路线。这通常被称为“路径”(因此路径寻找),但您也可以将其视为一个计划,因为它代表了一个接一个的位置列表,实现了到达目的地的最终目标。

现在,假定我们知道每个方格的位置,可以使用上一节中的转向行为沿着路径移动 —— 首先从开始节点到节点2,然后从节点2到节点3,等等。最简单的方法是转向下一个方格的中心,但一个流行的替代方案是移动到当前方格和下一个方格之间的边上,边的中间。这会让角色在急转弯时沿着切线方向移动,可以实现更逼真的运动。

很容易看出这个算法可能有点浪费,因为它在“错误”和“正确”方向上探索同样多的方块。它也没有考虑移动的成本,有些方块上的成本比其他方块更高。这就是更复杂的算法A *(发音为'A star')的由来。它的工作方式与广度优先搜索的工作方式大致相同,只是不是盲目地探索相邻节点,然后是相邻点的相邻节点.....。邻居等等,它将所有这些节点放入一个列表并对它们进行排序,以便选择最有可能产生最短路径的节点。

pathfinding2.gif

在这个例子中,我们展示了它一次检查一个方格,每次选择一个最佳(或联合最佳)前景的相邻方格。生成的路径与广度优先搜索相同,但在此过程中检查的方格更少 ——这对游戏性能提升产生了很大影响。

没有网格的移动

前面的示例使用了覆盖在地图上的网格,并根据网格绘制了穿过地图的路线。但是大多数游戏并没有布置在网格上,因此覆盖网格可能无法实现真实的运动模式。它可能还需要衡量网格的大小 ——太大,并且它不能代表小走廊或转弯,太小可能有数千个网格搜索需要太长时间。那么,有哪些替代方案?

首先要意识到的是,在数学术语中,网格为我们提供了连接节点的“ ”。A *(和BFS)算法实际上在图上运行,根本不关心我们的网格。因此我们可以将节点放置在游戏世界的任意位置,保证任何两个连接的节点之间,以及在开始和结束位置之间以及至少一个节点之间,有可通过路线,那么我们的算法将和以前一样可用 -—— 通常更好,事实上,因为我们搜索的节点更少。这通常被称为“waypoints”系统,因为每个节点代表游戏世界中的重要位置,他们是形成任意数量假设路径的组成部分。

pathfinding3a.png

示例1:每个网格中的节点。搜索从角色所在的节点开始,并在目标方格中的节点处结束。

pathfinding3b.png

示例2:一组小得多的节点或 waypoint。 搜索从角色开始,根据需要通过尽可能多的waypoint,然后进入终点。请注意,移动到玩家西南的第一个waypoint是一种效率低下的路线,因此通常需要对以这种方式生成的路径进行一定程度的后处理(例如,发现路径可以直接进入东北的航点)。

这是一个非常灵活和强大的系统。但是通常需要在放置waypoint的位置和方法上小心,否则角色可能无法看到最近的waypoint并开始寻路。如果我们能够以某种方式基于地图的几何图形自动生成waypoint,那将是很棒的。

这就是'navmesh'的用武之地。它是“导航网格”的缩写,用由三角形组成的二维网格,大致覆盖游戏世界几何形状,也是是覆盖游戏中允许通行的地方。网格中的每个三角形成为图中的节点,并且最多3个相邻的三角形,这些三角形成为图形中的相邻节点。

这张照片是Unity引擎的一个例子 - 它分析了游戏世界的几何形状,并生成了一个与其近似的navmesh(浅蓝色)。导航网格中的每个多边形都是角色可以站立的区域,并且角色能够从一个多边形移动到与其相邻的任何多边形。(在这个例子中,考虑到角色的半径将超出角色的名义位置,多边形比它们所依赖的地板更窄。)

团结,Nwmeshkpng

我们可以再次使用A *搜索通过此网格的路线,这为我们提供了一条近乎完美的路线,可以将所有几何体考虑在内,但不需要过多的冗余节点(如网格)也不需要人来生成waypoint。

寻路是一个广泛的主题,有许多不同的方法,特别是如果你必须自己编写低级细节。进一步阅读的最佳来源之一是Amit Patel的网站

规划

我们通过寻路看到,有时仅仅选择一个方向并直接移动到那里是行不通的 - 我们必须选择一条路线转几次弯才能到达目的地。我们可以将这个想法概括为宽泛的概念,实现目标不仅仅是下一步,而是需要一系列步骤,并且可能需要向前看几个步骤才能知道第一步应该是什么。这就是我们所说的 计划 。寻路可以被认为是规划的一个特定应用,但是这个概念有更多的应用。就我们的Sense / Think / Act周期来说,这就是Think阶段试图规划未来多个Act阶段的地方。

让我们来看看游戏Magic:The Gathering。这是你的第一个回合,你有一手牌,手中包括一个提供1点黑色法力的沼泽,一个提供1点绿色法力的森林,一个需要1点蓝色法力来召唤的逃亡巫师,以及一个需要1点绿色法力来召唤的精灵秘教徒。(简单起见,我们将忽略其他3张牌。)规则(大致)是允许玩家每回合玩1张地牌,可以“点击”的地牌以从中提取法力值,只要有足够的法力,可以多次释放法术(包括生物召唤)。在这种情况下,人类玩家可能会知道玩森林,点击它获得1点绿色法力,然后召唤精灵秘教徒。但是AI如何知道做出这个决定呢?

一个简单的'计划者'

老实的做法可能是持续依次尝试每个动作,直到没有合适的动作为止。看着手牌,它可能会看到它可以玩沼泽,所以它就这样做了。在那之后,本回合还有其他任何行动吗?它不能召唤精灵秘教徒或逃亡巫师,因为它们分别需要绿色和蓝色法力,而沼泽中只能提供黑色法术力。我们不能玩森林因为我们已经玩过沼泽了。因此,AI玩家玩了一个有效的回合,但不是非常好的回合。幸运的是,我们可以做得更好。

寻路是要找到位置序列以到达目的地,类似的,计划者可以找到动作序列使游戏进入目标状态。就像路径上的每个位置都有一组邻居一样,这些邻居是路径下一步的潜在选择,计划中的每个动作都有邻居或“后继者”,它们是计划下一步的候选动作。我们可以搜索这些行动和后续动作,直到我们达到我们想要的状态。

在我们的例子中,让我们假设期望的结果是“如果可能的话召唤一个生物”。回合一开始,我们看到游戏规则只允许2个潜在的动作:

  1. 玩沼泽(结果:沼泽离开手,进入游戏)
  2. 玩森林(结果:森林离开手,进入游戏)

根据游戏规则,每次采取的行动都可以启用进一步的行动并关闭其他行动。想象一下,我们选择玩沼泽 -,这会消除这个行动(因为已经玩过沼泽),也会移除Play The Forest这个形动(因为每回合只允许玩一张Land卡),它会把“点击沼泽”作为下一步行动 , 实际上是唯一后继行动。如果我们更进一步选择“点击沼泽”,得到1点黑色法术力,但是无法继续做任何事情,这是毫无意义的。

  1. 玩沼泽(结果:沼泽离开手,进入游戏)
    1.1 点击沼泽(结果:点击沼泽,可用+1黑色法术力)
    没有动作 - 结束
  2. 玩森林(结果:森林离开手,进入游戏)

如果我们使用寻路类比,这个简短的动作列表并没有取得多大成果,导致我们进入了死胡同。因此,我们重复下一步行动的过程。我们选择“播放森林” - 这次,这将从考虑中删除“播放森林”和“播放沼泽”,并打开“点击森林”作为潜在(并且仅)下一步。这给了我们1个绿色法术力,在这种情况下开辟了第三步,即召唤精灵秘教徒。

  1. 玩沼泽(结果:沼泽离开手,进入游戏)
    1.1 点击沼泽(结果:点击沼泽,可用+1黑色法术力)
    没有动作 - 结束
  2. 玩森林(结果:森林离开手,进入游戏)
    2.1 点击森林(结果:点击森林,可获得+1绿色法术力)
    2.1.1 召唤精灵秘教徒(结果:游戏中的精灵秘教徒,-1可用绿色法术力)
    没有动作 - 结束

我们现在已经探索了所有可能的行动,以及从这些行动中采取的行动,我们找到了一个允许我们召唤生物的计划: 玩森林,点击森林,召唤精灵秘教徒。

显然这是一个非常简单的例子,通常你会想要选择 最好的 计划而不是任何符合某种标准的计划(比如'召唤一个生物')。通常,您可以根据最终结果或遵循计划的累积收益对潜在计划进行评分。例如,你可能会因为玩一张Land Card而获得1分,并且可以为召唤一个生物获得3分。“玩沼泽”将是一个短视计划,产生1分,但“玩森林→点击森林→召唤精灵秘教徒”产生4分,1分为土地,3分为该生物。按照这种评分方法,这将是得分最高的计划,因此将被选中。

我们已经展示了规划是如何在Magic:The Gathering的一个回合中运作的,但它也可以适用于连续回合中的动作(例如在国际象棋中,移动棋子以腾出空间来开发主教,或者在XCOM中闯入掩体,从而让该单位可以在下一回合安全地射击)或随着时间推移的整体战略(例如选择在星际争霸中的其他神族建筑物之前建造铁塔,或者在攻击敌人之前在天际中使用Fortify Health药水)。

改进规划

有时,每一步都有太多可能,要考虑每种排列的话是不合理的。回到魔术:聚会的例子——想象一下,如果我们手中有多个生物,已经有很多地牌,所以我们可以召唤任何一个生物,已经召唤出的生物可以使用多种技能,以及我们手上还有几张地牌 —— 出地牌,点击地牌,召唤生物和释放生物技能的排列数量可以达到成千上万。幸运的是,我们可以尝试几种方法来管理它。

第一种方式是“ 向后链接 ”。我们可以从想要的最终结果开始,看看我们是否可以找到路线回到原点,而不是从原点尝试所有操作看他们后续怎么走。一个类比是试图从一棵树的树干到达一个特定的叶子 —— 从那片叶子开始反向向后推更有意义,将路线轻松地追踪到树干,而不是从主干并试图猜测每一步要采取哪个分支。从终点开始反向推,可以更快更容易地形成计划。

例如,如果对手只有一滴血,那么尝试找到“对对手造成1点或更多点伤害”的计划可能是有用的。为了达到这个目的,我们的系统知道它需要施放一个伤害法术,这反过来意味着它需要手中有一个法术并且有足够的法力施放它,这反过来意味着它必须有足够的地牌地来获取法力,可能需要出一张额外的地牌。

另一种方式是'最佳优先搜索'。我们不是彻底地遍历所有行动的排列,而是衡量每个子计划的“好坏”程度(类似于我们在上述计划之间的选择方式),并且我们每次只评估最好的计划。这样我们通常能够形成最佳或足够好的计划,而无需考虑计划的每一种可能的排列。A *是最佳搜索的一种形式 - 通过探索最有前途的路线,它首先通常可以找到到达目的地的路径,而无需在其他方向上探索太多。

蒙特卡罗树搜索是一种有趣且越来越流行的最佳搜索变体。在选择后继动作时,它不会试图猜测哪些计划更好,而是在随机选择一个后继动作,直到没有可用动作而到达终点 ——也可能是因为此计划触发了输赢条件 ——而后使用该结果来对先前的选择赋予更高或更低的权重。通过连续多次重复这个过程,即使情况发生变化(例如对手采取预防措施来阻止我们),它也可以很好地估计下一步哪个是最好的。

最后,如果不提及面向目标的行动计划(简称GOAP),就不会完成对游戏计划的讨论。这是一种广泛使用且广泛讨论的技术,但除了一些具体的实现细节之外,它本质上是一个向后链接的规划器,从一个目标开始并尝试选择一个能够实现该目标的行动,或者是,一系列将达到目标的行动。例如,如果目标是例如“杀死玩家”,并且玩家处于掩护状态,则计划可能是“扔手榴弹”→“拿出武器”→“攻击”。

通常是有几个目标,每个目标都有自己的优先级,如果无法达到最高优先级目标 - 例如,由于玩家不可见,任何一组动作都不能达到“杀死玩家”的计划 - 它将回归到优先级较低的目标,例如“巡逻”或“守卫”。