我发现了一些关于游戏中人工智能的有趣材料。 通过简单的例子解释了人工智能的基本知识，里面有很多有用的工具和方法，可以方便地进行开发和设计。 如何、在何处以及何时使用它们也在那里。
大多数示例都是用伪代码编写的，因此不需要高级编程知识。 剪辑下方有 35 张带有图片和 gif 的文字，所以请做好准备。
UPD。 抱歉，我已经翻译了这篇关于哈布雷的文章 。 你可以阅读他的版本 ，但由于某种原因，这篇文章与我擦肩而过（我使用了搜索，但出现了问题）。 由于我正在一个致力于游戏开发的博客上写作，所以我决定将我的翻译版本留给订阅者（有些要点的格式不同，有些根据开发人员的建议故意省略）。
什么是AI？
游戏人工智能重点关注对象应根据其所处的条件执行哪些操作。 这通常被称为“智能代理”管理，其中代理是玩家角色、车辆、机器人，或者有时更抽象的东西：整个实体组甚至是文明。 在每种情况下，它都必须看到它的环境，根据它做出决定，并按照它采取行动。 这称为感知/思考/行动循环：
- 感知：代理发现或接收有关其环境中可能影响其行为的事物的信息（附近的威胁、要收集的物品、要探索的有趣地方）。
- 思考：特工决定如何反应（考虑是否足够安全来收集物品或者他是否应该先战斗/隐藏）。
- 行动：代理执行行动以实施先前的决定（开始向敌人或物体移动）。
- ...现在情况由于角色的行为而发生了变化，因此循环会用新数据重复。
人工智能倾向于关注循环的感知部分。 例如，自动驾驶汽车拍摄道路照片，将其与雷达和激光雷达数据相结合，并进行解释。 这通常是通过机器学习来完成的，机器学习处理传入的数据并赋予其含义，提取语义信息，例如“在你前面 20 码处有另一辆车”。 这些就是所谓的分类问题。
游戏不需要复杂的系统来提取信息，因为大多数数据已经是游戏不可或缺的一部分。 无需运行图像识别算法来确定前方是否有敌人——游戏已经知道并将信息直接输入决策过程。 因此，周期的“感知”部分通常比“思考和行动”部分简单得多。
游戏人工智能的局限性
人工智能有许多必须遵守的限制：
- AI不需要提前训练，就好像它是一种机器学习算法一样。 在开发过程中编写一个神经网络来监控数以万计的玩家并学习与他们对抗的最佳方式是没有意义的。 为什么？ 因为游戏还没有发售，还没有玩家。
- 游戏应该有趣且具有挑战性，因此特工不应该找到对抗人类的最佳方法。
- 特工需要看起来很真实，这样玩家才会感觉自己是在与真人对战。 AlphaGo 程序的表现优于人类，但所选择的步骤与传统的游戏理解相去甚远。 如果游戏模拟的是人类对手，这种感觉就不应该存在。 需要更改算法，以便做出合理的决策，而不是理想的决策。
- 人工智能必须实时工作。 这意味着该算法无法长时间独占CPU使用率来做出决策。 即使 10 毫秒也太长了，因为大多数游戏只需要 16 到 33 毫秒即可完成所有处理并进入下一个图形帧。
- 理想情况下，系统的至少一部分应该是数据驱动的，以便非编码人员可以更快地进行更改和调整。
让我们看看涵盖整个感知/思考/行动周期的人工智能方法。
做出基本决定
Начнем с простейшей игры — Pong. Цель: переместить платформу (paddle) так, чтобы мяч отскакивал от нее, а не пролетал мимо. Это как теннис, в котором вы проигрываете, если не отбиваете мяч. Здесь у ИИ относительно легкая задача — решить, в каком направлении перемещать платформу.
条件语句
对于 Pong 中的 AI，最明显的解决方案是始终尝试将平台放置在球下方。
Простой алгоритм для этого, написанный в псевдокоде:
游戏运行时的每一帧/更新：
如果球位于球拍左侧：
向左移动桨
否则，如果球位于球拍右侧：
向右移动桨
如果平台以球的速度移动，那么这就是 Pong 中 AI 的理想算法。 如果代理没有太多数据和可能的操作，则无需使任何事情复杂化。
这种方法非常简单，以至于整个感知/思考/行动周期几乎不易被注意到。 但它就在那里：
- Sense 部分位于两个 if 语句中。 游戏知道球在哪里以及平台在哪里，因此人工智能会向它寻找这些信息。
- Think 部分也包含在两个 if 语句中。 它们体现了两种解决方案，在这种情况下，这两种解决方案是相互排斥的。 结果，选择三个操作之一 - 将平台向左移动、向右移动，或者如果平台已经正确定位，则不执行任何操作。
- Часть Act находится в операторах Move Paddle Left и Move Paddle Right. В зависимости от дизайна игры, они могут перемещать платформу мгновенно или с определенной скоростью.
这种方法称为反应式 - 有一组简单的规则（在本例中是代码中的 if 语句），可以对世界的当前状态做出反应并采取行动。
决策树
Pong 的例子实际上相当于一个正式的人工智能概念，称为决策树。 算法通过它到达“叶子”——关于采取什么行动的决定。
让我们为我们平台的算法制作一个决策树框图：
树的每个部分都称为节点 - AI 使用图论来描述此类结构。 有两种类型的节点：
- 决策节点：根据测试某些条件在两个备选方案之间进行选择，其中每个备选方案都表示为一个单独的节点。
- 结束节点：代表最终决策的要执行的操作。
Алгоритм начинается с первого узла («корня» дерева). Он либо принимает решение о том, к какому дочернему узлу перейти, либо выполняет действие, хранящееся в узле, и завершается.
让决策树执行与上一节中的 if 语句相同的工作有什么好处？ 这里有一个通用系统，其中每个决策只有一个条件和两种可能的结果。 这使得开发人员可以根据代表树中决策的数据创建人工智能，而无需对其进行硬编码。 我们用表格的形式来展示一下：
在代码方面，您将获得一个用于读取字符串的系统。 为每个节点创建一个节点，根据第二列连接决策逻辑，根据第三列和第四列连接子节点。 您仍然需要对条件和动作进行编程，但现在游戏的结构将更加复杂。 您可以在此处添加其他决策和操作，然后通过简单地编辑树定义文本文件来自定义整个 AI。 接下来，您将文件传输给游戏设计者，他们可以更改行为，而无需重新编译游戏或更改代码。
当决策树是根据大量示例自动构建时（例如，使用 ID3 算法），它非常有用。 这使得它们成为根据所获得的数据对情况进行分类的有效且高性能的工具。 然而，我们超越了一个供代理选择操作的简单系统。
方案
Мы разобрали систему дерева решений, которая использовала заранее созданные условия и действия. Человек, проектирующий ИИ, может организовать дерево так, как хочет, но он все еще должен полагаться на кодера, который это все запрограммировал. Что если мы могли бы дать дизайнеру инструменты для создания собственных условий или действий?
这样程序员就不必为条件“球在球拍左侧”和“球在球拍右侧吗”编写代码，他可以创建一个系统，设计人员将在其中编写条件来检查这些值。 那么决策树数据将如下所示：
这本质上与第一个表中的相同，但解决方案本身有自己的代码，有点像 if 语句的条件部分。 在代码方面，这将在第二列中读取决策节点，但不是寻找要执行的特定条件（球是否位于球拍左侧），而是评估条件表达式并相应地返回 true 或 false。 这是使用 Lua 或 Angelscript 脚本语言完成的。 使用它们，开发人员可以在游戏中获取对象（球和球拍）并创建脚本中可用的变量（ball.position）。 而且，脚本语言比 C++ 更简单。 它不需要完整的编译阶段，因此非常适合快速调整游戏逻辑，并允许“非编码人员”自己创建必要的功能。
在上面的示例中，脚本语言仅用于评估条件表达式，但也可用于操作。 例如，数据 Move Paddle Right 可以成为脚本语句 (ball.position.x += 10)。 这样动作也可以在脚本中定义，而不需要对 Move Paddle Right 进行编程。
Можно пойти еще дальше и полностью написать дерево решений на языке сценариев. Это будет код в виде жестко запрограммированных (hardcoded) условных операторов, но они будут находится во внешних файлах скрипта, то есть могут быть изменены без перекомпиляции всей программы. Зачастую можно изменить файл сценария прямо во время игры, чтобы быстро протестировать разные реакции ИИ.
事件响应
上面的例子非常适合 Pong。 他们不断地运行感知/思考/行动循环，并根据世界的最新状态采取行动。 但在更复杂的游戏中，您需要对个别事件做出反应，而不是立即评估所有事情。 在这种情况下，Pong 已经是一个坏例子了。 让我们选择另一个。
想象一下在射击游戏中，敌人一动不动，直到他们发现玩家，然后他们根据自己的“专长”采取行动：有人会跑去“冲”，有人会从远处攻击。 它仍然是一个基本的反应系统 - “如果发现玩家，请做某事” - 但它可以在逻辑上分解为玩家看到事件和反应（选择响应并执行它）。
这让我们回到了感知/思考/行动循环。 我们可以编写一个 Sense 部分来检查每一帧 AI 是否看到玩家。 如果没有，则不会发生任何事情，但如果它看到了，则会创建 Player Seen 事件。 该代码将有一个单独的部分，其中显示“当发生 Player Seen 事件时，执行操作”，其中是解决思考和行动部分所需的响应。 因此，您将设置对 Player Seen 事件的反应：对于“冲锋”角色 - ChargeAndAttack，对于狙击手 - HideAndSnipe。 可以在数据文件中创建这些关系，以便快速编辑，而无需重新编译。 这里也可以使用脚本语言。
做出艰难的决定
虽然简单的反应系统非常强大，但在很多情况下它们还不够。 有时你需要根据代理当前正在做的事情做出不同的决定，但很难想象这是一个条件。 有时条件太多，无法在决策树或脚本中有效地表示它们。 有时您需要提前评估情况将如何变化，然后再决定下一步。 需要更复杂的方法来解决这些问题。
有限状态机
有限状态机或 FSM（有限状态机）是一种表示我们的代理当前处于几种可能状态之一的方式，并且它可以从一种状态转换到另一种状态。 这样的状态有一定数量——因此得名。 生活中最好的例子就是交通灯。 不同的地方有不同的灯光序列，但原理是相同的——每种状态代表某种东西（停止、行走等）。 交通信号灯在任何给定时间仅处于一种状态，并根据简单的规则从一种状态移动到另一种状态。
С NPC в играх похожая история. Для примера возьмем стража с такими состояниями:
- 巡逻。
- 进攻。
- 逃跑。
以及改变其状态的这些条件：
- 如果守卫看到敌人，他就会攻击。
- 如果守卫攻击但不再看到敌人，他就会返回巡逻。
- 如果一名警卫发起攻击但受了重伤，他就会逃跑。
您还可以编写带有守护者状态变量和各种检查的 if 语句：附近是否有敌人、NPC 的健康水平是多少等。让我们添加更多状态：
- 闲置——巡逻之间。
- 搜索 - 当注意到的敌人消失时。
- Просить о помощи (Finding Help) — когда враг замечен, но слишком силен, чтобы сражаться с ним в одиночку.
Выбор для каждого из них ограничен — например, страж не пойдет искать скрывшегося врага, если у него низкое здоровье.
毕竟，有一大堆“如果” ， 那“可能会变得太麻烦，因此我们需要形式化一种方法，使我们能够记住状态和状态之间的转换。 为此，我们考虑所有状态，并在每个状态下，在列表中写下所有到其他状态的转换，以及它们所需的条件。
这是一个状态转换表——一种表示 FSM 的综合方式。 让我们画一张图，全面了解 NPC 行为如何变化。
Диаграмма отражает суть принятия решений для этого агента на основе текущей ситуации. Причем каждая стрелка показывает переход между состояниями, если условие рядом с ней истинно.
每次更新时，我们都会检查代理的当前状态，查看转换列表，如果满足转换条件，则它接受新状态。 例如，每一帧都会检查 10 秒定时器是否已到期，如果已到期，则警卫从空闲状态进入巡逻状态。 同样，攻击状态会检查代理的健康状况 - 如果健康状况较低，则进入逃跑状态。
这是处理状态之间的转换，但是与状态本身相关的行为又如何呢？ 在实现特定状态的实际行为方面，通常有两种类型的“挂钩”，我们可以在其中将操作分配给 FSM：
- 我们针对当前状态定期执行的操作。
- 从一种状态过渡到另一种状态时我们采取的行动。
第一种类型的示例。 巡逻状态将在每帧中沿着巡逻路线移动代理。 攻击状态将尝试每帧发起攻击或转换到可能的状态。
对于第二种类型，考虑过渡“如果敌人可见并且敌人太强大，则进入寻求帮助状态。 代理必须选择去哪里寻求帮助并存储此信息，以便“寻找帮助”状态知道去哪里。 一旦找到帮助，代理就会返回到攻击状态。 此时，他将想要告诉盟友有关威胁的信息，因此可能会发生 NotifyFriendOfThreat 操作。
我们可以再次通过感知/思考/行动循环的视角来看待这个系统。 意义体现在转换逻辑所使用的数据中。 思考 - 每个状态都可以进行转换。 Act 是通过在一个状态内或在状态之间的转换时定期执行的动作来执行的。
有时，连续轮询转换条件的成本可能很高。 例如，如果每个代理每帧都执行复杂的计算来确定它是否可以看到敌人并了解它是否可以从巡逻状态转换到攻击状态，这将花费大量的CPU时间。
世界状况的重要变化可以被视为将在发生时进行处理的事件。 FSM 无需每帧检查转换条件“我的代理可以看到玩家吗？”，而是可以配置一个单独的系统来降低检查频率（例如每秒 5 次）。 结果是在检查通过时发出 Player Seen。
该信息被传递给 FSM，FSM 现在应该转至 Player Seen 事件接收条件并做出相应响应。 除了响应之前几乎察觉不到的延迟之外，最终的行为是相同的。 但由于将 Sense 部分分离为程序的单独部分，性能得到了提高。
分层有限状态机
然而，使用大型 FSM 并不总是很方便。 如果我们想要将攻击状态扩展为单独的近战攻击和远程攻击，我们将必须更改导致攻击状态（当前和未来）的所有其他状态的转换。
您可能注意到，在我们的示例中存在很多重复的转换。 大多数空闲状态下的转换与巡逻状态下的转换相同。 最好不要重复自己，特别是如果我们添加更多类似的状态。 将闲置和巡逻归为“非战斗”的一般标签是有意义的，其中只有一组常见的到战斗状态的转换。 如果我们将此标签视为一个状态，那么 Idling 和 Patrolling 就成为子状态。 为新的非战斗子状态使用单独的转换表的示例：
主要状态：
脱离战斗状态：
并以图表形式：
这是相同的系统，但具有新的非战斗状态，包括空闲和巡逻。 每个状态都包含一个带有子状态的 FSM（这些子状态又包含它们自己的 FSM - 等等，只要您需要），我们就得到了一个分层有限状态机或 HFSM（分层有限状态机）。 通过对非战斗状态进行分组，我们删除了一堆冗余的转换。 我们可以对任何具有共同转换的新状态执行相同的操作。 例如，如果将来我们将攻击状态扩展到近战攻击和导弹攻击状态，它们将是根据与敌人的距离和弹药可用性在彼此之间转换的子状态。 因此，可以用最少的重复转换来表示复杂的行为和子行为。
行为树
通过 HFSM，可以以简单的方式创建复杂的行为组合。 然而，有一点困难，即以过渡规则的形式做出的决策与当前状态密切相关。 在许多游戏中这正是所需要的。 仔细使用状态层次结构可以减少转换重复次数。 但有时您需要无论您处于哪个州都适用的规则，或者几乎适用于任何州的规则。 例如，如果一个特工的生命值下降到 25%，你会希望他逃跑，无论他是在战斗、闲置还是说话 - 你必须将这个条件添加到每个状态。 如果您的设计师稍后想要将低健康阈值从 25% 更改为 10%，则必须再次执行此操作。
В идеале для этой ситуации нужна система, в которой решения «в каком состоянии пребывать», находятся за пределами самих состояний, чтобы вносить изменения только в одном месте и не трогать условия перехода. Здесь появляются деревья поведений.
Существует несколько способов их реализации, но суть для всех примерно одинакова и похожа на дерево решений: алгоритм начинается с «корневого» узла, а в дереве находятся узлы, представляющие либо решения, либо действия. Правда есть несколько ключевых отличий:
- 节点现在返回三个值之一：成功（如果作业已完成）、失败（如果无法启动）或正在运行（如果仍在运行并且没有最终结果）。
- 没有更多的决策节点可以在两个选项之间进行选择。 相反，它们是装饰器节点，具有一个子节点。 如果他们成功，他们就会执行他们唯一的子节点。
- 执行操作的节点返回一个 Running 值来表示正在执行的操作。
这一小组节点可以组合起来创建大量复杂的行为。 让我们将前面示例中的 HFSM 防护想象为行为树：
С этой структурой не должно быть явного перехода от состояний Idling/Patrolling к состоянию Attacking или любым другим. Если враг виден, а здоровье персонажа низкое, выполнение остановится на узле Fleeing, независимо от того, какой узел он ранее выполнял — Patrolling, Idling, Attacking или любой другой.
Деревья поведений сложны — есть много способов их составить, да и найти правильное сочетание декораторов и составных узлов может быть проблематично. Есть также вопросы о том, как часто проверять дерево — мы хотим проходить его каждую часть или только тогда, когда одно из условий изменилось? Как хранить состояние, относящееся к узлам — как узнать, когда мы были в состоянии Idling в течение 10 секунд или как узнать, какие узлы выполнялись в прошлый раз, чтобы правильно обработать последовательность?
这就是为什么有很多实现的原因。 例如，一些系统用内联装饰器替换了装饰器节点。 当装饰器条件发生变化时，它们会重新评估树，帮助连接节点并提供定期更新。
基于实用程序的系统
有些游戏有许多不同的机制。 希望它们能够获得简单且通用的转换规则的所有好处，但不一定以完整的行为树的形式。 与拥有一组明确的选择或可能的操作树相比，检查所有操作并选择当前最合适的操作会更容易。
基于实用程序的系统将有助于解决这一问题。 在这个系统中，代理具有多种操作，并根据每个操作的相对效用选择要执行的操作。 其中效用是对代理执行此操作的重要性或期望程度的任意度量。
根据当前状态和环境计算出某个动作的效用，智能体可以随时检查并选择最合适的其他状态。 这与 FSM 类似，不同之处在于转换是由对每个潜在状态（包括当前状态）的估计来确定的。 请注意，我们会选择最有用的操作继续（如果我们已经完成，则留下）。 对于更多种类，这可以是从一个小列表中平衡但随机的选择。
系统分配任意范围的效用值，例如，从 0（完全不需要）到 100（完全需要）。 每个操作都有许多影响该值计算的参数。 回到我们的监护人示例：
动作之间的转换是不明确的——任何状态都可以跟随任何其他状态。 操作优先级可在返回的效用值中找到。 如果敌人可见，并且该敌人很强，并且角色的生命值较低，则 Fleeing 和 FindHelp 都将返回较高的非零值。 在这种情况下，FindingHelp 总是会更高。 同样，非战斗活动的返回值永远不会超过 50，因此它们总是低于战斗活动。 在创建操作并计算其效用时需要考虑到这一点。
在我们的示例中，操作返回固定常量值或两个固定值之一。 更现实的系统会从连续的值范围返回估计值。 例如，如果代理的生命值较低，则“逃离”动作会返回较高的效用值；如果敌人太强，“攻击”动作会返回较低的效用值。 因此，在特工认为自己没有足够的生命值来击败敌人的任何情况下，逃跑行动优先于攻击行动。 这允许根据任意数量的标准对操作进行优先级排序，从而使这种方法比行为树或 FSM 更加灵活和可变。
每个动作都有很多程序计算的条件。 它们可以用脚本语言编写，也可以编写为一系列数学公式。 《模拟人生》模拟了角色的日常生活，增加了额外的计算层——代理收到一系列影响效用评级的“动机”。 如果角色感到饥饿，随着时间的推移，他们会变得更加饥饿，并且 EatFood 动作的效用值将会增加，直到角色执行该操作，从而降低饥饿程度并将 EatFood 值返回到零。
基于评级系统选择行动的想法非常简单，因此基于效用的系统可以用作人工智能决策过程的一部分，而不是完全替代它们。 决策树可能会询问两个子节点的效用评级并选择较高的一个。 类似地，行为树可以有一个复合效用节点来评估操作的效用，以决定执行哪个子级。
运动和导航
В предыдущих примерах у нас была платформа, которую мы перемещали влево или вправо, и страж, который патрулировал или атаковал. Но как именно мы обрабатываем перемещение агента в течение определенного периода времени? Как мы устанавливаем скорость, как мы избегаем препятствий, и как мы планируем маршрут, если добраться до места назначения сложнее, чем просто двигаться по прямой? Давайте это рассмотрим.
管理
На начальном этапе будем считать, что каждый агент имеет значение скорости, которое включает в себя, как быстро он двигается и в каком направлении. Она может быть измерена в метрах в секунду, километрах в час, пикселей в секунду и т. д. Вспоминая цикл Sense/Think/Act, мы можем представить, что часть Think выбирает скорость, а часть Act применяет эту скорость к агенту. Обычно в играх есть физическая система, которая выполняет эту задачу за вас, изучая значение скорости каждого объекта и регулируя ее. Поэтому можно оставить ИИ с одной задачей — решить, какую скорость должен иметь агент. Если известно, где агент должен быть, то нужно переместить его в правильном направлении с установленной скоростью. Очень тривиальное уравнение:
desired_travel = 目的地位置 – 代理位置
想象一个 2D 世界。 智能体位于点 (-2,-2)，目的地位于东北某处的点 (30, 20)，智能体到达那里所需的路径是 (32, 22)。 假设这些位置以米为单位测量 - 如果我们将代理的速度设为每秒 5 米，那么我们将缩放位移矢量并获得大约 (4.12, 2.83) 的速度。 有了这些参数，代理将在近 8 秒内到达目的地。
您可以随时重新计算这些值。 如果智能体已到达目标的一半，则移动长度将是一半，但由于智能体的最大速度为 5 m/s（我们在上面决定），因此速度将相同。 这也适用于移动目标，允许代理在移动时进行微小的更改。
但我们想要更多的变化 - 例如，缓慢增加速度来模拟角色从站立到奔跑的移动。 最后停止前也可以做同样的事情。 这些功能被称为转向行为，每个行为都有特定的名称：寻找、逃离、到达等。其想法是，基于将代理的位置和当前速度与目的地进行比较，可以将加速力应用于代理的速度。为了使用不同的方法来实现目标。
每个行为的目的都略有不同。 寻找和到达是将代理移动到目的地的方法。 避障和分离调整代理的运动，以避开到达目标途中的障碍物。 一致性和凝聚力使代理能够齐心协力。 考虑到所有因素，可以将任意数量的不同转向行为相加，以产生单个路径向量。 使用“到达”、“分离”和“避障”行为来远离墙壁和其他代理的代理。 这种方法在开放位置效果很好，没有不必要的细节。
在更困难的条件下，添加不同的行为效果会更糟 - 例如，代理可能会由于到达和避障之间的冲突而卡在墙上。 因此，您需要考虑比简单添加所有值更复杂的选项。 方法是这样的：你可以考虑不同方向的移动并选择最佳选项，而不是将每个行为的结果相加。
然而，在一个充满死胡同和选择走哪条路的复杂环境中，我们将需要更先进的东西。
寻找方向
转向行为非常适合在开放区域（足球场或竞技场）中进行简单移动，其中从 A 到 B 是一条直线路径，仅绕障碍物很少绕道。 对于复杂的路线，我们需要寻路，这是一种探索世界并决定穿越世界的路线的方式。
最简单的方法是将网格应用于代理旁边的每个方格，并评估其中哪些方格可以移动。 如果其中一个是目的地，则沿着从每个方格到前一个方格的路线，直到到达起点。 这就是路线。 否则，请对附近的其他方块重复此过程，直到找到目的地或用完方块（意味着没有可能的路线）。 这就是所谓的广度优先搜索或 BFS（广度优先搜索算法）。 每走一步，他都会向各个方向看（因此是宽度，“宽度”）。 搜索空间就像一个波前，移动直到到达所需位置 - 搜索空间每一步都会扩展，直到包含终点，之后可以追溯到起点。
В результате вы получите список квадратов, по которым составляется нужный маршрут. Это и есть путь (отсюда, pathfinding) — список мест, которые агент посетит, следуя к пункту назначения.
鉴于我们知道世界上每个方块的位置，我们可以使用转向行为沿着路径移动 - 从节点 1 到节点 2，然后从节点 2 到节点 3，依此类推。 最简单的选择是前往下一个方块的中心，但更好的选择是停在当前方块和下一个方块之间的边缘中间。 因此，代理将能够在急转弯处走捷径。
BFS 算法也有缺点——它在“错误”方向上探索的方块数量与在“正确”方向上探索的方块数量一样多。 这就是称为 A*（A 星）的更复杂算法发挥作用的地方。 它的工作方式相同，但不是盲目地检查邻居方块（然后是邻居的邻居，然后是邻居的邻居的邻居，等等），而是将节点收集到一个列表中并对它们进行排序，以便检查的下一个节点始终是一条通向最短路线的路径。 节点根据启发式进行排序，该启发式考虑了两件事：到所需广场的假设路线的“成本”（包括任何旅行成本）以及对该广场距目的地有多远的估计（使搜索偏向于正确的方向）。
此示例表明，智能体一次探索一个方格，每次都会选择最有希望的相邻方格。 生成的路径与 BFS 相同，但在此过程中考虑的方块更少 - 这对游戏性能有很大影响。
Движение без сетки
但大多数游戏并不是在网格上布局的，而且通常不可能在不牺牲真实性的情况下做到这一点。 需要做出妥协。 正方形的大小应该是多少？ 太大，他们将无法正确表示小走廊或转弯，太小，将有太多的方块需要搜索，这最终将花费大量时间。
首先要理解的是，网格为我们提供了连接节点的图。 A* 和 BFS 算法实际上适用于图，根本不关心我们的网格。 我们可以将节点放置在游戏世界中的任何位置：只要任意两个连接的节点之间以及起点和终点与至少一个节点之间存在连接，算法就会像以前一样工作。 这通常称为航路点系统，因为每个节点代表世界上的一个重要位置，可以是任意数量的假设路径的一部分。
Пример 1: узел в каждом квадрате. Поиск начинается из узла, в котором находится агент, и заканчивается в узле нужного квадрата.
示例 2：较小的一组节点（航路点）。 搜索从代理的方格开始，经过所需数量的节点，然后继续到达目的地。
这是一个完全灵活且功能强大的系统。 但在决定在何处以及如何放置路径点时需要小心，否则代理可能根本看不到最近的点并且无法启动路径。 如果我们能够根据世界的几何形状自动放置路径点，那就更容易了。
这是导航网格或 navmesh（导航网格）出现的位置。 这通常是覆盖在世界几何形状上的三角形的 2D 网格 - 无论智能体允许在哪里行走。 网格中的每个三角形都成为图中的一个节点，并且最多有三个相邻三角形成为图中的相邻节点。
这张图片是来自 Unity 引擎的示例 - 它分析了世界中的几何形状并创建了一个导航网格（在浅蓝色的屏幕截图中）。 导航网格中的每个多边形都是代理可以站立或从一个多边形移动到另一个多边形的区域。 在此示例中，多边形小于它们所在的楼层 - 这样做是为了考虑代理的大小，该代理将超出其标称位置。
我们可以再次使用 A* 算法来搜索穿过该网格的路线。 这将为我们提供一条几乎完美的世界路线，它考虑了所有几何形状，并且不需要不必要的节点和创建航路点。
探路这个话题太宽泛，一篇文章的一节是不够的。 如果您想更详细地研究它，那么这会有所帮助 .
规划
我们通过寻路了解到，有时仅仅选择一个方向并移动是不够的 - 我们必须选择一条路线并转几个弯才能到达我们想要的目的地。 我们可以概括这个想法：实现目标不仅仅是下一步，而是一个完整的序列，有时你需要向前看几个步骤才能找出第一步应该是什么。 这就是所谓的计划。 寻路可以被认为是规划的几种扩展之一。 就我们的感知/思考/行动周期而言，这是思考部分为未来规划多个行动部分的地方。
让我们看一下棋盘游戏《万智牌》的例子。 我们首先手上有以下一组牌：
- 沼泽 - 提供 1 点黑色法力（地牌）。
- 森林 - 提供 1 点绿色法力（土地卡）。
- 逃亡巫师 - 需要 1 点蓝色法力才能召唤。
- 精灵秘法师 - 需要 1 点绿色法力才能召唤。
Оставшиеся три карты игнорируем, чтобы было проще. По правилам игроку разрешено играть 1 карту земли за ход, он может «тапнуть» эту карту, чтобы извлечь из нее ману, а затем использовать заклинания (включая вызов существа) по количеству маны. В этой ситуации игрок-человек знает, что нужно играть Forest, «тапнуть» 1 зеленую ману, а затем вызвать Elvish Mystic. Но как об этом догадаться игровому ИИ?
轻松规划
最简单的方法是依次尝试每个动作，直到没有合适的动作为止。 通过查看牌，AI 可以了解 Swamp 可以玩什么。 他演奏了它。 本回合还有其他行动吗？ 它不能召唤精灵秘法师或逃亡法师，因为它们分别需要绿色和蓝色法力来召唤它们，而沼泽只提供黑色法力。 而且他将不再能够玩森林，因为他已经玩过沼泽了。 因此，游戏AI虽然遵守了规则，但却做得很糟糕。 可以改进。
规划可以找到使游戏达到所需状态的一系列操作。 正如路径上的每个方格都有邻居（在寻路中）一样，计划中的每个动作也有邻居或后继者。 我们可以寻找这些动作和后续动作，直到达到所需的状态。
在我们的示例中，期望的结果是“如果可能的话，召唤一个生物”。 在回合开始时，我们只看到游戏规则允许的两种可能的行动：
1.玩Swamp（结果：游戏中的Swamp）
2.玩Forest（结果：游戏中的Forest）
采取的每项行动都可能导致进一步的行动并关闭其他行动，这同样取决于游戏规则。 想象一下我们玩了沼泽 - 这将删除沼泽作为下一步（我们已经玩过它），这也将删除森林（因为根据规则，你每回合可以打一张地牌）。 在此之后，AI 会添加获得 1 点黑色法力作为下一步，因为没有其他选择。 如果他继续选择点击沼泽，他将收到 1 单位黑色法力，并且无法用它做任何事情。
1.玩Swamp（结果：游戏中的Swamp）
1.1“点击”沼泽（结果：沼泽被“点击”，+1单位黑色法力）
没有可用的操作 - 结束
2.玩Forest（结果：游戏中的Forest）
行动清单很短，我们走进了死胡同。 我们在下一步中重复该过程。 我们玩森林，打开“获得 1 点绿色法力”动作，这又会打开第三个动作——召唤精灵秘法师。
1.玩Swamp（结果：游戏中的Swamp）
1.1“点击”沼泽（结果：沼泽被“点击”，+1单位黑色法力）
没有可用的操作 - 结束
2.玩Forest（结果：游戏中的Forest）
2.1“点击”森林（结果：森林被“点击”，+1单位绿色魔法值）
2.1.1 召唤精灵秘法师（结果：精灵秘法师在场，-1 绿色法力）
没有可用的操作 - 结束
最后，我们探索了所有可能的行动，并找到了召唤生物的计划。
这是一个非常简单的例子。 建议选择最佳的计划，而不是仅仅选择满足某些标准的任何计划。 通常可以根据实施的结果或总体效益来评估潜在的计划。 你可以为自己打出一张地牌得 1 分，召唤一个生物得 3 分。 打沼泽将是一个 1 点计划。 玩森林→点击森林→召唤精灵秘法师将立即获得4分。
这就是《万智牌》中计划的运作方式，但同样的逻辑也适用于其他情况。 例如，在国际象棋中移动棋子为象移动腾出空间。 或者像这样在 XCOM 中躲在墙后安全射击。 一般来说，你明白了。
改进规划
有时，潜在的行动太多，无法考虑每一个可能的选择。 回到万智牌的例子：假设在游戏中和你的手中有几张地牌和生物牌 - 可能的移动组合数量可能有几十种。 该问题有多种解决方案。
第一种方法是向后链接。 与其尝试所有组合，不如从最终结果开始，尝试找到一条直接的路线。 我们不是从树根到特定的叶子，而是沿着相反的方向移动——从叶子到根。 这种方法更简单、更快。
如果敌人有 1 生命值，您可以找到“造成 1 或更多伤害”计划。 为了实现这一目标，必须满足许多条件：
1. 法术可以造成伤害 - 法术必须在手上。
2. 要施展法术，你需要法力。
3. 要获得法力，您需要打出地牌。
4. 要打出地牌，您需要拥有它在手上。
另一种方法是最佳优先搜索。 我们不会尝试所有路径，而是选择最合适的一条。 大多数情况下，此方法会给出最佳计划，而无需不必要的搜索成本。 A* 是最佳优先搜索的一种形式 - 通过从一开始就检查最有希望的路线，它已经可以找到最佳路径，而无需检查其他选项。
蒙特卡洛树搜索是一个有趣且越来越流行的最佳优先搜索选项。 该算法在选择每个后续行动时不会猜测哪些计划比其他计划更好，而是在每一步中随机选择后继者，直到到达终点（当计划导致胜利或失败时）。 然后使用最终结果来增加或减少先前选项的权重。 通过连续多次重复这个过程，即使情况发生变化（如果敌人采取行动干扰玩家），算法也能很好地估计下一步的最佳行动是什么。
В рассказе о планировании в играх не обойдется без Goal-Oriented Action Planning или GOAP (целенаправленное планирование действий). Это широко используемый и обсуждаемый метод, но помимо нескольких отличительных деталей это, по сути, метод backwards chaining, о котором мы говорили ранее. Если задача была «уничтожить игрока», и игрок находится за укрытием, план может быть таким: уничтожь гранатой → достань ее → брось.
通常有几个目标，每个目标都有自己的优先级。 如果最高优先级的目标无法完成（由于玩家不可见，因此任何行动组合都不会创建“杀死玩家”计划），AI 将回退到较低优先级的目标。
Обучение и адаптация
我们已经说过，游戏人工智能通常不使用机器学习，因为它不适合实时管理代理。 但这并不意味着你不能从这个领域借东西。 我们希望在射手中找到一个可以让我们学习一些东西的对手。 例如，找出地图上的最佳位置。 或者格斗游戏中的对手会阻止玩家常用的连击动作，从而激励他使用其他连击动作。 因此，机器学习在这种情况下非常有用。
统计与概率
在我们讨论复杂的例子之前，让我们看看通过进行一些简单的测量并使用它们来做出决策我们可以走多远。 例如，即时战略——我们如何判断玩家在游戏开始的几分钟内是否可以发起攻击，以及准备什么防御？ 我们可以研究玩家过去的经历来了解未来可能的反应。 首先，我们没有这样的原始数据，但我们可以收集它——每次人工智能与人类对战时，它都可以记录第一次攻击的时间。 经过几次会话后，我们将得到玩家未来攻击所需的平均时间。
平均值还有一个问题：如果一个玩家冲了 20 次，慢速玩了 20 次，那么所需的值将位于中间的某个位置，这不会给我们带来任何有用的东西。 一种解决方案是限制输入数据 - 可以考虑最后 20 条数据。
当通过假设玩家过去的偏好在未来相同来估计某些行为的可能性时，可以使用类似的方法。 如果一个玩家用火球攻击我们五次，用闪电攻击两次，用近战攻击一次，那么很明显他更喜欢火球。 让我们推断一下使用不同武器的概率：火球=62,5%，闪电=25%，近战=12,5%。 我们的游戏人工智能需要做好保护自己免受火灾的准备。
另一个有趣的方法是使用朴素贝叶斯分类器来研究大量输入数据并对情况进行分类，以便人工智能以所需的方式做出反应。 贝叶斯分类器因其在电子邮件垃圾邮件过滤器中的使用而闻名。 他们在那里检查这些单词，将它们与这些单词之前出现的位置（是否在垃圾邮件中）进行比较，并对收到的电子邮件得出结论。 即使投入更少，我们也可以做同样的事情。 基于AI看到的所有有用信息（例如创建了哪些敌方单位，或者他们使用了哪些法术，或者他们研究了哪些技术），以及最终结果（战争还是和平，冲锋还是防御等） - 我们将选择所需的人工智能行为。
所有这些训练方法都足够了，但建议基于测试数据使用它们。 人工智能将学习适应游戏测试人员使用的不同策略。 发布后适应玩家的人工智能可能会变得太可预测或太难击败。
基于价值的适应
给定我们游戏世界的内容和规则，我们可以改变影响决策的一组值，而不是简单地使用输入数据。 我们这样做：
- Пусть ИИ собирает данные о состоянии мира и ключевых событиях во время игры (как указано выше).
- 让我们根据这个数据改变几个重要的值。
- 我们根据处理或评估这些值来实施我们的决策。
К примеру, у агента есть несколько комнат для выбора на карте шутера от первого лица. Каждая комната имеет свое value, которое определяет насколько она желательна для посещения. ИИ случайно выбирает в какую комнату идти, основываясь на значении value. Затем агент запоминает, в какой комнате его убили, и уменьшает ее value (вероятность, что он туда вернется). Аналогично для обратной ситуации — если агент уничтожает много противников, то value комнаты увеличивается.
Марковская модель
Что если мы используем собранные данные для прогнозирования? Если запомнить каждую комнату, в которой видим игрока в течение определенного периода времени, мы будем предугадывать в какую комнату игрок может перейти. Отследив и записав перемещения игрока по комнатам (values), мы можем прогнозировать их.
我们以三个房间为例：红色、绿色和蓝色。 还有我们在观看比赛时记录的观察结果：
每个房间的观察次数几乎相等——我们仍然不知道在哪里设置伏击的好地方。 收集统计数据也因玩家的重生而变得复杂，这些玩家均匀地出现在整个地图上。 但是他们出现在地图上后进入的下一个房间的数据已经有用了。
Видно, что зеленая комната устраивает игроков — большинство людей из красной переходят в нее, 50% которых остается там и дальше. Синяя комната наоборот не пользуется популярность, в нее почти не ходят, а если ходят, то не задерживаются.
但数据告诉我们一些更重要的事情——当一个玩家在蓝色的房间里时，我们看到他所在的下一个房间将是红色的，而不是绿色的。 尽管绿色房间比红色房间更受欢迎，但如果玩家在蓝色房间中，情况就会发生变化。 下一个状态（即玩家将前往的房间）取决于之前的状态（即玩家当前所在的房间）。 因为我们探索依赖关系，所以我们将比简单地独立计算观测值做出更准确的预测。
根据过去状态的数据预测未来状态称为马尔可夫模型，此类示例（带有房间）称为马尔可夫链。 由于这些模式代表连续状态之间变化的概率，因此它们在视觉上显示为 FSM，并带有每个转换周围的概率。 之前，我们使用 FSM 来表示智能体所处的行为状态，但这个概念可以扩展到任何状态，无论它是否与智能体相关。 在本例中，状态代表代理占用的房间：
这是一种表示状态变化的相对可能性的简单方法，使人工智能具有预测下一个状态的能力。 您可以预见未来的几个步骤。
如果一名球员在绿色房间里，那么下次观察他时，他有 50% 的几率会留在绿色房间里。 但即便如此，他仍然留在那里的可能性有多大呢？ 不仅有可能该球员在两次观察后仍留在休息室，而且也有可能离开并返回。 这是考虑了新数据的新表：
它表明，经过两次观察后，在绿色房间中看到玩家的几率将等于 51% - 21%，他将来自红色房间，其中 5% 玩家将访问他们之间的蓝色房间，并且25% 的球员不会离开休息室。
该表只是一个可视化工具 - 该过程只需要在每一步乘以概率。 这意味着您可以展望遥远的未来，但有一个警告：我们假设进入房间的机会完全取决于当前房间。 这称为马尔可夫性质 - 未来状态仅取决于现在。 但这并不是百分百准确。 玩家可以根据其他因素改变决定：健康水平或弹药数量。 由于我们不记录这些值，因此我们的预测将不太准确。
N-克
格斗游戏和预测玩家的连击动作的例子怎么样？ 相同！ 但我们将检查构成组合攻击的整个序列，而不是一个状态或事件。
实现此目的的一种方法是将每个输入（例如 Kick、Punch 或 Block）存储在缓冲区中，并将整个缓冲区写入为事件。 因此，玩家反复按 Kick、Kick、Punch 来使用 SuperDeathFist 攻击，AI 系统将所有输入存储在缓冲区中，并记住每一步中使用的最后三个输入。
(Жирным выделены строки, когда игрок запускает атаку SuperDeathFist.)
当玩家选择 Kick（踢），然后选择另一个 Kick（踢）时，AI 将看到所有选项，然后注意到下一个输入始终是 Punch（出拳）。 这将允许代理预测 SuperDeathFist 的组合动作并在可能的情况下阻止它。
这些事件序列称为 N 元语法，其中 N 是存储的元素数量。 在前面的示例中，它是 3-gram（三元组），这意味着：前两个条目用于预测第三个条目。 因此，在 5-gram 中，前四个条目预测第五个条目，依此类推。
设计者需要仔细选择 N-gram 的大小。 N 越小，需要的内存越少，但存储的历史记录也越少。 例如，2-gram（bigram）将记录 Kick、Kick 或 Kick、Punch，但无法存储 Kick、Kick、Punch，因此 AI 不会对 SuperDeathFist 组合做出反应。
另一方面，更大的数字需要更多的内存，并且人工智能将更难以训练，因为会有更多可能的选择。 如果您有三种可能的输入：踢、出拳或阻挡，并且我们使用 10 克，那么将有大约 60 个不同的选项。
二元模型是一个简单的马尔可夫链 - 每个过去状态/当前状态对都是一个二元模型，您可以根据第一个状态预测第二个状态。 3-gram 和更大的 N-gram 也可以被视为马尔可夫链，其中所有元素（N-gram 中的最后一个除外）一起形成第一个状态，最后一个元素形成第二个状态。 格斗游戏示例显示了从 Kick and Kick 状态转换到 Kick and Punch 状态的机会。 通过将多个输入历史条目视为一个单元，我们实质上是将输入序列转换为整个状态的一部分。 这给了我们马尔可夫属性，它允许我们使用马尔可夫链来预测下一个输入并猜测下一步将是什么组合移动。
结论
我们讨论了人工智能开发中最常见的工具和方法。 我们还研究了需要使用它们的情况以及它们特别有用的情况。
这应该足以理解游戏 AI 的基础知识。 但是，当然，这些并不是所有方法。 不太受欢迎但同样有效的包括：
- 优化算法包括爬山算法、梯度下降算法和遗传算法
- состязательные алгоритмы поиска/планирования (minimax и alpha-beta pruning)
- 分类方法（感知器、神经网络和支持向量机）
- системы для обработки восприятия и памяти агентов
- 人工智能的架构方法（混合系统、子集架构和其他覆盖人工智能系统的方法）
- 动画工具（规划和运动协调）
- 性能因素（详细程度、任何时间和时间切片算法）
相关资源：
1. На GameDev.net есть 和 .
2. 包含许多与游戏人工智能开发相关的广泛主题的演示文稿和文章。
3. 包括 GDC 人工智能峰会的主题，其中许多主题都是免费的。
4. 有用的资料也可以在网站上找到 .
5. 人工智能研究员和游戏开发者 Tommy Thompson 在 YouTube 上制作视频 对商业游戏中的人工智能进行了解释和研究。
有关该主题的书籍：
1. Game AI Pro书籍系列是解释如何实现特定功能或如何解决特定问题的短文集合。
2、AI游戏编程智慧系列是Game AI Pro系列的前身。 它包含较旧的方法，但几乎所有方法即使在今天也是相关的。
3. 是每个想要了解人工智能一般领域的人的基础文本之一。 这不是一本关于游戏开发的书——它教授人工智能的基础知识。
来源： habr.com