引言

本文将向您介绍游戏中的人工智能的各种概念（“游戏AI”），以便您了解可以使用哪些工具来解决AI问题，它们如何协同工作以及如何在选定的引擎中实现它们。

我假设您熟悉视频游戏，并且对几何，三角等数学概念有所了解。大多数代码示例都是用伪代码编写的，因此您不需要了解特定的语言。

什么是“游戏AI”？

游戏AI主要根据当前条件处理实体的动作选择。在传统的AI文献中，它被称为“ 智能代理 ”的管理。代理通常是游戏中的角色，但它可以是机器，机器人，甚至可以是更抽象的东西-一整套实体，一个国家或一个文明。在任何情况下，它都是一个对象，它监视周围的环境，基于该环境做出决策，并根据这些决策采取行动。有时这称为感知－思考－行动周期（Sense / Think / Act）：

感知：代理会识别（或被告知）有关可能影响其行为的环境的信息（例如，附近的危险，收集的物品，重点等）
思考：代理人决定如何应对（例如，决定是否可以安全地收集物品，是否应该打架或最好先躲起来）
行动：特工执行行动以执行其决定（例如，开始沿着通往敌人或目标的路线前进，依此类推）
...然后，由于角色的动作，情况发生了变化，因此应使用新数据重复该循环。

现实世界中的AI任务，尤其是与当今相关的AI任务，通常专注于“感知”。例如，无人驾驶车辆应接收前方的道路图像，并将其与其他数据（雷达和激光雷达）结合起来，并试图解释其所见。通常，这项任务是通过机器学习来解决的，它在处理大量现实世界中的嘈杂数据（例如，在汽车前的道路照片或几帧视频）时特别有效，并赋予它们一些含义，并提取语义信息，例如，“我前面有20码另一辆车。” 这些任务称为分类问题。

游戏之所以与众不同，是因为它们是模拟的一部分，因此不需要复杂的系统来提取此信息。无需执行图像识别算法即可检测到您面前的敌人；游戏知道有一个敌人，可以将这些信息直接传递到决策过程。因此，通常会大大简化此周期中的“感知”，并且在执行“思考”和“动作”时会出现所有复杂性。

游戏AI开发局限性

游戏AI通常会考虑以下限制：

与机器学习算法不同，它通常不预先训练；在开发游戏时，编写神经网络来监视成千上万的玩家以找到与他们对抗的最佳方法是不切实际的，因为该游戏尚未发布且还没有玩家！
通常认为游戏应该娱乐和挑战玩家，而不是“最优”-因此，即使您可以训练代理商以最佳方式抵抗玩家，但大多数情况下设计师都需要与他们不同的东西。
通常，代理商必须具有“现实”的行为，以便玩家感到自己正在与类人对手竞争。事实证明， AlphaGo程序比人的程序好得多，但是它选择的动作与传统的游戏理解相去甚远，经验丰富的对手将其称为对付外星人的游戏。如果游戏假装是人类的对手，那么通常这是不可取的，因此需要设置算法，以便做出合理的决定，而不是理想的决定。
AI必须实时运行。在这种情况下，这意味着该算法无法在很长时间内独占处理器资源。即使是10毫秒的决策时间也太多了，因为大多数游戏只有16-33毫秒才能完成图形下一帧的所有操作。
理想情况下，系统的至少一部分应取决于数据，并且不应该进行硬编码，以便非程序员可以更快地进行更改。

了解了所有这些内容之后，我们可以开始考虑创建AI的极其简单的方法，该方法以确保效率并允许游戏设计师选择类似于人类动作的复杂行为的方式来实现“感知－思考－动作”的整个周期。

轻松决策

让我们从一个非常简单的游戏开始，例如Pong。玩家的任务是移动“球拍”，使球从球拍反弹，而不是飞过去。规则类似于网球-如果错过球，您就会输。 AI具有相对简单的任务，即决定选择球拍的运动方向。

硬编码条件构造

如果我们想编写AI来控制球拍，那么有一个直观而简单的解决方案-不断移动球拍使其处于球下。当球到达球拍时，它已经处于理想位置并且可以击中球拍。

用伪代码表示的一种简单算法可以是：

 在每个帧/在游戏运行时更新：

如果球在球拍的左边：

	将球拍向左移动

否则，如果球在球拍的右边：

	将球拍向右移动

如果我们假设球拍的移动速度不低于球，那么这将是Pong中AI运动员的理想算法。如果没有太多的“感知”数据需要处理，并且座席可以执行的动作很少，那么我们不需要任何复杂的事情。

这种方法是如此简单，以至于几乎没有显示“感知－思考－行动”的整个周期。但是他是。

感知是两个if语句。游戏知道球和球拍在哪里。因此，AI向游戏询问其位置，从而“感觉”到球是在左侧还是右侧。
思维也内置在两个if语句中。它们包含两个解决方案，在这种情况下，这两个解决方案是互斥的，因此可以选择以下三个动作之一：将球拍向左移动，向右移动球拍，或者如果球拍已经正确放置，则什么也不做。
“动作”是“将球拍向左移动”或“将球拍向右移动”。根据游戏的实施方式，可以采取立即移动球拍的位置或设置球拍的速度和方向的形式，以便可以在其他游戏代码中正确移动球拍。

这种方法通常称为“反应性”，因为存在一组简单的规则（在我们的示例中为代码中的“ if”语句），它们可以响应世界状况并立即决定如何进行。

决策树

这个Pong示例实际上类似于称为决策树的正式AI概念。在该系统中，决策以树的形式排列，并且算法必须绕过它才能到达包含对所选操作的最终决策的“工作表”。让我们使用流程图绘制Pong球拍算法的决策树的图形表示：

可以看出它像一棵树，只是倒过来了！

决策树的每个部分通常称为“节点”，因为在AI中，图论用于描述这种结构。每个节点可以是以下两种类型之一：

解决方案的节点：基于条件验证的两个备选方案的选择。每个备选方案均以其自己的节点表示。
结束节点：执行的操作，表示树做出的最终决定。

该算法从树的“根”分配的第一个节点开始，然后根据条件决定要转到哪个子节点，或者执行存储在该节点中的操作，然后停止工作。

乍一看，决策树的优势并不明显，因为它所做的工作与上一节中的if语句完全相同。但是，有一个非常通用的系统，其中每个解决方案都有1个条件和2个可能的结果，这使开发人员可以从代表树中解决方案的数据构建AI，并避免将其硬编码到代码中。可以想象一个简单的数据格式来描述这种树：

节点编号	决定（或“结束”）	动作片	动作片
1个	球拍左边的球？	?？检查节点2	不行吗检查节点3
2	结束	向左移动球拍
3	球拍右边的球？	?？转到节点4	不行吗转到节点5
4	结束	向右移动球拍
5	结束	什么都不做

从代码的角度来看，我们需要强制系统读取这些行中的每行，为每个节点创建，基于第二列附加决策逻辑并基于第三列和第四列附加子节点。我们仍然需要手动手动定义条件和动作，但是现在我们可以想象一个更加复杂的游戏，您可以在其中添加新的解决方案和动作，以及通过更改唯一包含树定义的文本文件来配置整个AI。我们可以将文件传输给游戏设计者，他们将能够自定义行为，而无需重新编译游戏和更改代码-前提是代码已经具有有用的条件和操作。

当决策树基于大量示例（例如，使用ID3算法）自动构建时，决策树将非常强大。它使它们成为根据传入数据对情况进行分类的有效且高性能的工具，但是此主题超出了设计人员创建用于选择代理动作的简单系统的范围。

脚本编写

上面，我们研究了使用预先创建的条件和动作的决策树系统。 AI开发人员可以用他需要的任何方式重建树，但是他应该依靠程序员已经为他创建了所有必要条件和动作的事实。但是，如果我们为设计师提供更强大的工具，使他能够创造自己的条件，甚至可能创造行为，该怎么办？

例如，不是强迫编码器写条件“球拍左边的球？” 和“球拍右边的球？”，他可以简单地创建一个系统，设计人员可以在其中独立编写检查这些值的条件。结果，决策树数据可能如下所示：

节点编号	决定（或“结束”）	解决方案	动作片
1个	ball.position.x <paddle.position.x	?？检查节点2	不行吗检查节点3
2	结束	向左移动球拍
3	ball.position.x> paddle.position.x	?？检查节点4	不行吗检查节点5
4	结束	将球拍向右移动
5	结束	什么都不做

与以前相同，但是现在解决方案具有自己的代码，类似于if语句的条件部分。该代码将从第二列读取决策节点，而不是搜索特定条件（例如，“球拍左侧的球？”），而是计算条件表达式并返回true或false。这可以通过插入脚本语言 Lua的一样或AngelScript，它允许开发人员把对象从游戏（如球和球拍），并创建一个可从脚本（例如ball.position）变量来完成。与C ++相比，用脚本语言编写通常更容易，并且不需要完整的编译阶段，因此它非常适合对游戏逻辑进行快速更改，并且使技术上精通的团队成员无需编码器的干预即可创建游戏功能。

在上面的示例中，脚本语言仅用于评估条件表达式，但是最终操作也可以在脚本中描述。例如，这些类型为“向右移动球拍”的动作可以变成脚本结构，如ball.position.x += 10 ，也就是说，该动作也可以在脚本中设置，而无需编写MovePaddleRight函数代码。

如果您又向前迈进了一步，则可以（并且经常这样做）得出其逻辑结论，并以脚本语言而不是数据行列表的形式编写整个决策树。这将是与上述条件构造相似的代码，只是它们不是“硬编码”的-它们在外部脚本文件中，也就是说，可以在不重新编译整个程序的情况下对其进行更改。甚至有可能在游戏执行期间修改脚本文件，这使开发人员可以快速测试各种实现AI的方法。

对事件的反应

上面显示的示例旨在在Pong等简单游戏中执行单帧执行。他们的想法是，他们不断执行“感知－思考－行动”循环，并根据世界的最后状态继续行动。但是在更复杂的游戏中，对计算而非“计算”而言，对“事件”做出反应（即对游戏环境中的重要变化做出反应）通常更为合理。

这不适用于Pong，因此让我们选择另一个示例。想象一下一个射击游戏，其中敌人一动不动，直到找到一名玩家，之后他们才开始根据自己的职业进行行动-近战战士可以冲向玩家，而狙击手则保持一定距离并试图瞄准。从本质上讲，这是一个简单的反应系统-“如果我们看到一个玩家，那么我们就会做某事”-但从逻辑上讲，它可以分为一个事件（“看到一个玩家”）和反应（选择一个响应并执行它）。

这使我们回到了感知思维行动周期。我们可能有一个代码片段，这是一个“感知”代码，它在每一帧中检查敌人是否看到了玩家。如果没有，则什么也不会发生。但是，如果他看到了，就会创建一个“看到玩家”的事件。该代码将有一个单独的部分，内容为：“当事件“发生”时，看到玩家“发生”，那么我们执行“ xyz”，而“ xyz”是我们要处理的思维和行动的任何响应。对于角色格斗者，您可以将奔跑和攻击响应与“看到玩家”事件联系起来。对于狙击手，我们将“隐藏和瞄准”响应功能连接到此事件。与前面的示例一样，我们可以在数据文件中创建此类关联，以便可以快速更改它们而无需重建引擎。此外，有可能（并且经常使用）以脚本语言编写此类响应函数，以便它们可以在事件发生时创建复杂的解决方案。

改进决策

尽管简单的反应系统非常强大，但在许多情况下它们还不够用。有时，我们需要根据代理当前所做的事情来做出不同的决定，而将其作为条件提出来是不方便的。有时，存在太多条件，无法以决策树或脚本的形式有效地呈现它们。有时，在决定下一步行动之前，我们需要预先考虑并评估形势将如何变化。对于此类任务，需要更复杂的解决方案。

状态机

有限状态机（FSM）是一种表示其他对象（例如我们的AI代理之一）当前处于几种可能状态之一的一种方式，并且它可以从从一个州到另一个州。这种状态的数量有限，因此得名。现实世界中的一个例子是交通信号灯组，它从红色变为黄色，然后变为绿色，然后再返回。在不同的地方，有不同的照明顺序，但是原理是相同的-每个状态都表示某种东西（“站立”，“吃”，“站立，如果可能”等），在任何给定时间只有一个状态，并且它们之间的过渡基于简单的规则。

这非常适用于游戏中的NPC。警卫队可能具有以下明确分开的状态：

巡逻
突袭
飞行

我们可以提出以下状态间转换规则：

如果守卫看到敌人，他会进攻
如果后卫发动进攻，但再也看不到敌人，他将返回巡逻
如果警卫进攻但受了重伤，他逃脱了

该方案非常简单，我们可以使用严格定义的“ if”运算符和一个变量将其写下来，该变量将存储安全卫士的状态和各种检查-附近敌人的存在，安全卫士的健康水平等。但想象一下，我们需要添加更多状态：

等待中（巡逻之间）
搜索（当先前见过的敌人躲藏起来时）
逃脱寻求帮助（当发现敌人时，他太强大了，无法独自与他战斗）

而且在每个州可用的选择通常是有限的-例如，一名警卫可能不愿寻找失去视线的敌人，如果他的健康状况太差。

或早或晚，“如果<x和y但不包括z>则<p>”一长串变得太尴尬了，采用正式的方法来实现状态和它们之间的转换会有所帮助。为此，我们考虑了所有状态，并在每个状态下列出了到其他状态的所有转换以及它们所需的条件。我们还需要指示初始状态，以便在应用其他条件之前知道从哪里开始。

条件	过渡条件	新条件
等待中	预计持续10秒	巡逻
	敌人可见并且敌人太强大	帮助搜索
	敌人是可见的，很多健康	突袭
	敌人是可见的，几乎没有健康	飞行
巡逻	巡逻路线已完成	等待中
	敌人可见并且敌人太强大	帮助搜索
	敌人是可见的，很多健康	突袭
	敌人是可见的，几乎没有健康	飞行
突袭	敌人不可见	等待中
突袭	小健康	飞行
飞行	敌人不可见	等待中
搜寻	搜索了10秒	等待中
	敌人可见并且敌人太强大	帮助搜索
	敌人是可见的，很多健康	突袭
	敌人是可见的，几乎没有健康	飞行
帮助搜索	朋友看	突袭
初始状态：等待

这种方案称为状态转换表。这是代表航天器的一种复杂（且没有吸引力）的方式。从这些数据中，您还可以绘制图表并获得有关NPC行为外观的复杂图形表示。

它抓住了根据座席所处的情况为座席做决定的本质。如果箭头旁边的条件为true，则每个箭头指示状态之间的转换。

每次更新（或“周期”）时，我们都会检查代理的当前状态，查看转换列表，如果满足转换条件，则进入新状态。 Pending状态在每个帧或周期中检查10秒计时器是否已到期。如果过期，它将开始过渡到“巡逻”状态。同样，“攻击”状态将检查代理是否具有很多健康状况，如果是，则将其过渡到“飞行”状态。

这就是状态转移的处理方式-但是与状态本身关联的行为又如何呢？从为状态执行动作本身的角度来看，通常有两种将动作附加到航天器的方法：

当前状态的操作会定期执行，例如在每个帧或“周期”中执行。
在从一种状态过渡到另一种状态的过程中执行操作。

第一种类型的示例：每个帧或周期中的“巡逻”状态继续使特工沿着巡逻路线移动。每个帧或周期中的“攻击”状态都会尝试发起攻击或将其移动到可能的位置。依此类推。

第二种类型的示例：考虑过渡“如果敌人可见并且敌人太强大→寻求帮助”。代理必须选择寻求帮助的位置，并存储此信息，以便“帮助搜索”状态知道去向。同样，在“帮助搜索”状态下，当找到帮助时，代理会再次返回“攻击”状态，但此刻他想告知友好角色有关威胁的信息，因此在此过渡期间可能会执行“告诉朋友危险的动作”。

在这里，我们可以从“感知－思考－行动”的角度再次考虑该系统。感知嵌入在转换逻辑使用的数据中。思维内置于每个状态可用的转换中。并且该动作是通过在一个状态下或在状态之间的过渡期间定期执行的动作来执行的。

这个简单的系统运作良好，尽管有时不断轮询过渡条件可能是一个代价高昂的过程。例如，如果每个特工需要在每个帧中执行复杂的计算以确定敌人的可见性并确定从巡逻到攻击的过渡，那么这可能会花费大量的处理器时间。正如我们前面所看到的，可以将世界状态中的重要变化视为发生后进行处理的“事件”。因此，与其明确检查过渡条件“我的经纪人可以看到玩家吗？”，我们可以创建一个单独的可见性系统，该系统以较少的频率（例如每秒5次）执行这些检查，并创建“玩家”请参见“触发测试时”。它被传输到状态机，该状态机现在具有转换“接收到事件”的玩家看到“”的条件，并相应地对此做出响应。结果的行为将相似，除了几乎没有注意到（甚至增加的现实性）反应延迟之外，但由于将“感知”转移到程序的单独部分，因此生产率将提高。

分层状态机

所有这些都很好，但是对于大型状态机而言，工作变得非常不便。如果要通过用单独的“近战攻击”和“远距离攻击”状态代替“攻击”状态来扩展“攻击”状态，则我们将不得不更改从每个状态（现在和将来）的传入转换，这需要具有切换到“攻击”状态的能力。

您可能还注意到，在我们的示例中，有许多重复的过渡。 “待定”状态下的大多数过渡与“巡逻”状态下的过渡相同，最好避免重复这项工作，特别是如果我们想添加更多类似的状态。将“等待”和“巡逻”组合成一组“非战斗状态”将是合乎逻辑的，“非战斗状态”只有一组向战斗状态的常见过渡。如果将这个组表示为一个状态，则可以将“等待”和“巡逻”视为该状态的“子状态”，这将使我们能够更有效地描述整个系统。为新的非战斗子状态使用单独的转换表的示例：

主要条件：

条件	过渡条件	新条件
非战斗	敌人可见并且敌人太强大	帮助搜索
	敌人是可见的，很多健康	突袭
	敌人是可见的，几乎没有健康	飞行
突袭	敌人不可见	非战斗
突袭	小健康	飞行
飞行	敌人不可见	非战斗
搜寻	搜索了10秒	非战斗
	敌人可见并且敌人太强大	帮助搜索
	敌人是可见的，很多健康	突袭
	敌人是可见的，几乎没有健康	飞行
帮助搜索	朋友看	突袭
初始状态：非战斗

非战斗状态：

条件	过渡条件	新条件
等待中	预计持续10秒	巡逻
巡逻	完成了巡逻路线	等待中
初始状态：等待

并以图表形式：

实际上，这是同一个系统，只是现在有一个非战斗状态代替了“巡逻”和“等待”，这本身就是一个具有巡逻和等待两个子状态的状态机。如果每个状态都可能包含子状态的状态机（并且这些子状态还可以包含其自己的状态机，依此类推），那么我们就有一个分层状态机（HFSM）。通过对非战斗行为进行分组，我们消除了许多不必要的过渡，并且可以对可能具有共同过渡的任何新状态进行相同的处理。例如，如果将来我们将“攻击”状态扩展为“近战攻击”状态和“弹丸攻击”状态，则它们可以是子状态，它们之间的过渡取决于与敌人的距离和弹药的存在，它们具有根据健康水平和其他的东西。因此，通过最少的重复转换，可以表示复杂的行为和子行为。

行为树

使用HFSM，我们能够以相当直观的方式创建相当复杂的行为集。但是，立即注意到，过渡规则形式的决策与当前状态密切相关。许多游戏都需要这样做。仔细使用状态层次结构可以减少重复转换的次数。但是有时我们需要适用于所有状态的规则，或者适用于几乎所有状态的规则。例如，如果特工的生命值下降到25％，他可能想逃跑，而不管他是在战斗中，正在等待，还是在说话，或者处于任何其他状态。我们不想记住，我们需要将此条件添加到将来可能添加到角色的每个状态中。因此，当设计人员稍后说他想将阈值从25％更改为10％时，我们将不必整理并更改每个相应的过渡。

在这种情况下，理想的情况是一个系统，其中关于要进入哪个状态的决定与状态本身分开存在，因此我们只能更改一个元素，并且仍然可以正确处理转换。这是行为树派上用场的地方。

行为树的实现方法有多种，但是本质上与上面提到的决策树大部分相同，并且非常相似：算法从“根节点”开始工作，并且树中有指示决策或动作的节点。但是，有一些关键区别：

现在，节点将返回以下三个值之一：“成功”（如果作业已完成），“不成功”（如果作业未完成）或“已执行”（如果作业仍在完成且未完全成功或失败）。
现在，我们没有决策节点可供我们从两个选择中进行选择，但是有装饰节点和单个子节点。如果它们“成功”，则它们将执行其唯一的子节点。装饰器节点通常包含确定执行是否以成功（这意味着您需要执行其子树）或失败（然后无需执行任何操作）而结束的条件。他们还可以返回“进行中”。
执行动作节点返回值“ running”以指示正在发生的事情。

可以组合一小组节点，从而创建大量复杂的行为，并且这种方案通常非常简短。例如，我们可以以行为树的形式重写上一示例中防护的分层CA：

使用此结构时，无需从“等待”或“巡逻”状态到“攻击”状态或任何其他状态的明确过渡-如果从上到下，从左到右遍历树，则根据当前情况做出正确的决定。如果敌人可见并且角色的健康状况不佳，则树将在“飞行”节点上完成奔跑，而与先前完成的节点（“巡逻”，“等待”，“攻击”等）无关。

您可能会注意到，我们还没有从“巡逻”返回“等待”状态的过渡-在这里，无条件的装饰器将派上用场。标准装饰器节点为“重复”-它没有条件，它仅拦截返回“成功”的子节点，然后再次运行该子节点，返回“已执行”。新树如下所示：

, , . , ( -, ?) ( , 10 ? , , ?) . , Unreal Engine 4 - , «», . — , , , .

基于实用程序的系统

有些游戏需要存在许多不同的动作，因此需要更简单，集中的过渡规则，但它们并不需要完全实现行为树的功能。与其创建一个明确的选择集或一棵潜在动作树，并通过树的结构定义隐含的后备位置，不如简单地检查所有动作并选择当前最适用的动作更好？

这是基于实用程序的系统所做的工作-这些系统中，代理可以执行许多操作，并且他选择根据相对实用程序执行一个每一个动作。这里的有用性是代理执行此操作的重要性或可取性的任意度量。通过编写效用函数以根据代理的当前状态及其环境计算操作的效用，代理可以检查效用值并选择当前最合适的状态。

这也非常类似于有限状态机，不同之处在于，过渡是通过评估每个潜在状态（包括当前状态）来确定的。值得注意的是，在一般情况下，我们选择向最有价值的动作过渡（或者如果我们已经在执行此动作，则选择过渡），但是对于更大的可变性，它可以是加权随机选择（优先考虑最有价值的动作，但允许其他人选择），从前五名（或任何其他数量）中选择随机动作，等等。

— 0 ( ) 100 ( ), , . , :


	, , 100, 0
	, 90, 0
	, 80
	10 , 0, 50
	, 0, 50

该方案最重要的方面之一是动作之间的转换是隐式表示的-从任何状态，您都可以完全合法地转到任何其他状态。此外，在返回的实用程序值中暗含了操作优先级。如果敌人是可见的，并且他很强壮，并且角色的健康状况很差，那么非零值将返回Flight和Help Search，但Help Search总是具有较高的等级。同样，非战斗行动永远不会超过50次，因此总是会被战斗打败。考虑到这一点，将创建动作及其效用计算。

在我们的示例中，动作返回一个恒定效用值或两个恒定效用值之一。更实际的系统使用连续值范围内的返回值。例如，如果特工的生命值较低，则Getaway动作可以返回较高的效用值，而如果敌人太强大，则Attack动作可以返回较低的效用值。这将使Getaway优先于Assault。 , , , . , , .

, . , , . ( @IADaveMark ).

, , , The Sims, , «» «», . , «», , «» , , , «» .

基于积分系统选择动作的想法非常简单，因此很明显，您可以在其他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等。（在Habré上有一系列关于他们的文章：https : //habr.com/post/358366/。）他们的想法是，您可以采用代理速度根据特工的位置和当前向目标移动速度的比较得出的加速力，从而产生了各种向目标移动的方式。

, . Seek Arrive . Obstacle Avoidance Separation . Alignment Cohesion , . steering behaviours , , , . , Arrival Separation Obstacle Avoidance, . , .

— , , Arrival , Obstacle Avoidance behaviour , . steering behaviours, , . — , , ( ). — , , 5-6 , .

但是，在具有死角和转弯选项的复杂环境中，我们将需要更高级的功能，并且我们将尽快进行处理。

寻路

转向行为非常适合在较开阔的区域内进行简单的运动，例如在足球场或竞技场上，您可以通过一点点调整从A到B的直线，避免障碍物。但是，如果到达终点的路线更复杂怎么办？然后，我们需要“寻路”-探索世界并沿着其绘制路径，以便代理到达终点。

— , , . , , , , . , ( , ). (Breadth-First Search, BFS), ( « »), . , , , .

这是一个实际搜索的简单示例。搜索区域在每个阶段都会扩展，直到其中包含端点为止，之后您可以跟踪到起点的路径。

, , . «», path ( « », pathfinding), , , , , .

, , steering behaviours — 2, 2 3, . , — . .

, , «» , «». , «» . A*. , , , , , , . ( , , ), — ( ) , ( ).

在此示例中，我们显示他一次检查一个单元，每次选择一个前景最佳（或最佳之一）的相邻单元。生成的路径类似于广度优先搜索路径，但是在此过程中检查的单元格较少，这对于复杂级别的游戏性能非常重要。

无网眼运动

, , . , . — , , , . ?

, — " " . A* ( BFS) , . , , , , , . « » (waypoints system), , .

1: . , , .

2: , . , . , - — , (, , , -).

, , , . , - .

navmesh. navigation mesh ( ). () , , . , .

Unity. navmesh ( ), . — , , . ( ý, , , , .)

, A*, , ( ) .

— , , . — ( : https://habr.com/post/331192/ ).

规划中

, — , . , . , , , . . , . «--», — , .

Magic: The Gathering. , , «», 1 , «», 1 , «-», 1 , « », 1 . ( .) , , «» , , ( ), . «», , 1 , « ». , ?

«»

, . , , «», . ? « », «-», , «» . «», «». - , . , .

, , , . , , , , «», . , .

, « , ». , :

 1.  "" (: ""       )
2.  "" (: ""       )

, . , «» — ( «» ), «» ( ) «» 1 — , , . « „“», 1 , , .

 1.  "" (: ""       )
            1.1  "" (:   "",  +1  )
                           - 
2.  "" (: ""       )

«», . . « „“». « „“» « „“», ( ) « „“». 1 , — « „ “».

 1.  "" (: ""       )
            1.1  "" (:   "",  +1  )
                           - 
2.  "" (: ""       )
            2.1  "" (:   "",  +1  )
                        2.1.1  " " (: " "  ,  -1  )
                                       -

, , , : « „“», « „“», « „ “».

, , 一个计划，而不仅仅是满足某些条件的计划（例如，“召唤生物”）。通常，您可以根据最终结果或使用该计划的累积收益来评估潜在计划。例如，您可以为自己的地形图分配1分，而为召唤生物分配3分。 “玩“沼泽””是一个简短的计划，得1分，“玩”森林”→触摸“森林”→称呼“精灵神秘”的计划得4分，地面1分，生物3分。这将是最有利可图的计划，因此，如果我们指定了这些点，则应选择它。

上面，我们展示了计划是如何在一个“魔术：汇聚”动作中工作的，但是它也可以应用于一系列动作中的动作（例如，在国际象棋中“移动棋子为主教的发展留出空间”或“掩盖一个单位”他可以进行下一回合射击，“在XCOM中是安全的”或整个游戏的总体策略（例如，在“星际争霸”中为所有其他神族建筑建造塔架，或者在“天际”中攻击敌人之前喝“强化健康”药水）。

改善计划

, . Magic: The Gathering — , , , , , — , , . , .

" backwards chaining " (« »). , . — , ( ), , . , .

, 1 , « 1 ». , , , . , , , , .

— . , «» ( , ) . , . A* — , .

— - . , , , , , — , — . , (, ).

, (Goal-Oriented Action Planning, GOAP). , , , , , , , , . , « » , : « » → « » → «».

, . , , « », , , , «» « ».

, « », . , - , . , , , . , . , Tekken Street Fighter , , . , .

, , , . , , , , , , . , , . , , , , . , .

简单平均的问题在于它通常会随着时间在中心收敛。因此，如果玩家在前20次使用急冲策略，而后20次切换到慢得多的策略，则平均值将处于中间位置，这将无法提供任何有用的信息。改善数据的一种方法是使用简单的平均窗口，该窗口仅考虑最后20个数据点。

, , . , , , , 5 8 . , , : =62,5%, =25% =12,5%. - , !

(Naive Bayes Classifier) , - . - , , , . , . - , . (, , ) (/, / ..), .

, , . , , . , , .

. , , , . , :

( );
«» ;
.

, . , . . , , . , , , , , . , , . , , . -, , - , .

, ? , , - , , . , , , , , , .

, — , , :

,
	10	2	20%
		7	70％
		1个	10%
	10	3	30%
		5	50％
		2	20%
	8	6	75％
		2	25％
		0	0％

每个房间中的检测次数相当均匀，因此我们无法了解哪个房间可以成为伏击的好地方。玩家会均匀地在地图上生成，并且出现在这三个房间中的任何一个中的概率相同，因此数据可能会失真。但是访问下一个房间的数据可能会有用，并且可以帮助我们预测玩家在地图上的移动。

我们可以立即注意到，绿色房间对玩家非常有吸引力-红色房间中的大多数玩家都变成了绿色，并且在下一次检查中，在绿色房间中看到的玩家中有50％留在那里。我们还可以注意到，蓝色的房间是一个没有吸引力的地方。人们很少从红色或绿色的房间移到蓝色的房间，似乎没有人喜欢在其中徘徊很长时间。

但是数据告诉我们一些更具体的信息-他们说，当玩家在蓝色房间中时，紧随其后的是他最有可能选择红色而不是绿色。尽管绿色房间比红色房间更受欢迎，但如果玩家在蓝色房间里，趋势就会稍微相反。似乎下一个状态（即他决定进一步移动的房间）取决于前一个状态（即他现在所在的房间），因此该数据使我们可以更好地预测玩家的行为而不是独立观察计数。

我们可以使用先前状态的知识来预测未来状态的想法称为马尔可夫模型 , , (, « »), . , , . , , , . . :

这是指示转变为不同状态的相对概率的简单方法，这使AI能够预测下一个状态。但是，我们可以通过创建一个分两个或多个步骤展望未来的系统来走得更远。

如果玩家被发现在绿色房间中，我们将使用数据告诉我们，下一次观察时，他仍有50％的机会仍在绿色房间中。但是他第三次留在里面的可能性是多少？这不仅是他将留在绿色房间进行两次观察的概率（50％* 50％= 25％），而且还包括他离开绿色空间并返回的概率。这是一张新表，其中以前的值适用于三个观测值：一个当前观测值和两个未来假设值。

观察1	假设观察2		3
		30%		20%	6%
				70％	21%
				10%	3％
		50％		30%	15％
				50％	25%
				20%	10%
		20%		75％	15％
				25％	5%
				0％	0％
				:	100％

, 2 51% — 21% , , 5% , , 25% , .

— , . , , : , , . , , 。尽管它允许我们使用诸如马尔可夫链之类的功能强大的工具，但它通常只是一个近似值。玩家可能会根据其他因素（例如他们的健康水平和弹药数量）决定访问房间，并且由于我们没有将此信息记录为条件的一部分，因此我们的预测将不太准确。

N克

. , ( , ), , , -.

— (, , ) . , , , " ”，然后AI系统将所有玩家的输入保存到缓冲区中，并记住每个步骤中使用的最后3个条目。

进入	现有输入序列	新输入存储器
踢	踢	没有啦
罢工	踢，踢	没有啦
踢	踢，踢，踢	踢，踢，踢
踢	踢，踢，踢，踢	踢，踢，踢
罢工	踢，踢，踢，踢，踢	踢，踢，踢
块	踢，踢，踢，踢，踢，块	踢，踢，块
踢	踢，踢，踢，踢，踢，挡，踢	踢，挡，踢
踢	踢，踢，踢，踢，踢，挡，踢，踢	挡，踢，踢
罢工	, , , , , , , ,	, ,

( « ».)

, , , , . - , , , , . , , .

N- , N — . 3-, , 2 . 5- 4 , .

N- ( ). , , , , , . , 2- ( «») , , , , , , .

, , , , , , . , ( , ) 10-, 60 .

— « / » . N- , N-, , , . , 。将输入历史记录的多个元素视为一个元素，我们实际上将输入序列转换为状态的一个片段，这为我们提供了一个马尔可夫属性，允许我们使用马尔可夫链来预测下一个输入，即猜测将跟随哪个组合运动。

知识表示

, , . ? , , , . ( ) ( ) ? ? , .

/

, , — . , , . , , , , . , . .

; — , , , . , , , . « », . — , «Crate_01», «Crate_02», «Crate_27», . , . , «Crate», «Broken_Crate» , .

«COVER» , . () , , , . , , , .

, , . , , Unity Unreal Engine 4 , .

— , , « , » « , » . .

, , , . «TRAINING», . , — , — . , «» , . ARCHERY-TRAINING MAGIC-TRAINING, . . , « , »! , , « ». , , ..

, , - . , ( ), , .


	Shoot-Arrow	+10 Archery
	Sword-Duel	+10 Swords
	Shoot-Arrow	+15 Archery
	Sword-Duel	+8 Swords
	Sword-Duel	+5 Swords
	Cast-Spell	+10 Magic

- 4 6 , 4 , , . , , . . .


旅馆	求购	-10
旅馆	Sleep	-50
图书馆	Read-Book	+10 Spellcasting
图书馆	Read-Book	+5 Archery

« », ARCHERY-TRAINING, «read-book» . , .

— , — , , , . . , , , .

通常情况下，可以将一部分世界状态测量为连续值。范例：

“健康百分比”通常在0（无效）到100（绝对健康）的范围内
“距离最近的敌人”的范围从0到任意正值

, , - . , , .

, «», — , 200 , 100 . , , — 200 190 , 10 .

, , . , , . (Response Curves).

X, , « » Y ( 0.0 1.0). , , .

«» — , 10% — , . 0 1 :

, ( 50 ), , .

, «» 40 50 : 0.96 1.0.

15 ( 0.5) 5 ( 0.2) . , .

0 1, . 20% 50 0.6. 75% 5 0.47. 10% 5 0.145.

:

— , .
— , , 50 — , , .
, ( ) . , — , Unity AnimationCurve , .

Blackboards

, , , . , , , . , , , . , , . - , - , ( , ).

. , , / . . , , .

, . , , . «-», , , .

«blackboards» (« »), — (, , ) — «», . , - , . , . «static blackboard» ( , , ), «-» «dynamic blackboard». — .

, . . -RPG :

«» blackboard :
- « »: « 412»
- « »: 35.0
- « »: « 43»
- « »: 55.4
- « »: 12:45pm
blackboard , :
- « »: 12:34pm

— , , , , . , , - , , . « » « » — , blackboard.

Unreal Engine 4 dynamic blackboard , . blackboard ( ), , .

(Influence Maps)

, . « », , ? «» — ? RTS , — , ?

, . , — . , , , . , .

« ». «», . , . , 2D-, , , , , . . , .

« ». , , 3 — 2 , 1 . ?

+1 . :

, . +1 . .

:

, , +2 . +2 ! :

[: CC-BY: https://game-icons.net/heavenly-dog/originals/defensive-wall.html ]

, . , +2 , 11 +1 , 2 0 — , , .

, , .

. , ?

-, . , , , . , — «» .

-, . , , — .

, , , . , , , .

, . , , , , .

结论

, , , , . ( , ), :

, , .
/, --
, , ,
, , ( )
, (motion planning) motion matching
, (level of detail), (anytime algorithms) (timeslicing)

, , , .

GameDev.net , .
AiGameDev.com
GDC Vault GDC AI Summit, : https://www.gdcvault.com/
, AI Game Programmers Guild : http://gameai.com/
YouTube-, : https://www.youtube.com/user/tthompso

, :

The Game AI Pro — , . http://www.gameaipro.com/ .
AI Game Programming Wisdom Game AI Pro. , . , !
Artificial Intelligence: A Modern Approach — , . , , , .

, , . - — , .

游戏AI实施技术概述

引言