思维导图

文字版

4 行为选择算法一览

AI模型：感知-思考-行动。

• 实现NPC思考的算法有很多种，每种算法都有适用的场景。本章介绍几种业界最流行的行为选择（思考）算法

• 注：思考，也是上面提到的行为选择算法，即决策算法

有限状态机 FSM，Finite-State Machine

• 定义

  • 状态 State

    • 表示一个特定的行为或内部状态，同一时刻只有一个状态是激活的

  • 状态迁移 State Transition

    • 满足特定条件时切换激活状态

• 可视化

  • 圆角方框表示状态

  • 箭头表示状态迁移

• 代码类

  • 状态基类 FSMState

  • 状态迁移类 FSMTransition

  • 状态机管理类 FiniteStateMachine

• 优缺点

  • 灵活

  • 状态数多时非常复杂

  • 无法做到有上下文时的行为重用

分层状态机 HFSM， Hierarchical Finite-State Machine

• 定义

  • 将一个状态机划分为按层次组织的多个状态机

• 优缺点

  • 一定程度上解决FSM缺点，例如有历史状态

  • 嵌套状态机，代码和递归负责度高

• 细节

  • Artificial Intelligence for Games一书5.3.9节，作者 Ian Millington

行为树 Behavior Tree

• 定义

  • 由一个根节点和许多行为组成树状结构，每个行为都是NPC要表现的一个独立动作。

• 算法描述

  • 把根节点当做当前节点

  • 如果当前节点不为空

    • 检测当前节点的预设条件

    • 如果预设条件返回true

      • 将节点加入待驱动列表中

      • 把节点的子节点（有可能为空）作为当前节点

    • 否则

      • 把节点的右兄弟节点作为当前节点

  • 驱动待驱动列表中的所有行为节点

• 优点

  • 简单直接，易于实现，且行为树本身无状态

  • 行为间的耦合度比FSM状态间耦合度小

  • 扩展性极强

    • 在行为树基础上实现其他的行为选择算法

    • 采用不同的行为选择算法

      • 固定/随机/依次选择子行为

      • 基于效用的类型选择器

      • 扩展预设条件等

• 缺点

  • 每次从根节点开始，单次驱动的时间通常大于FSM

  • 无状态，需要留意涉及NPC记忆的情况

基于效用的系统

• 定义

  • 对大量参考因素进行度量、权衡、组合、评估、排序、挑选，决定潜在动作的优先性（即优先级、评分、程度）

• 应用

  • 《模拟人生》 The Sims

• 适用

  • RPG

  • RTS 实时策略游戏

• 优点

  • AI逻辑不仅仅是布尔的是否逻辑，更多是连续竖直表明希望进行这个动作的程度，例如多远、多饿、血量或子弹等等

  • 适应性

    • 优先值一直在变化

  • 不可预测性，好处是提高可信度

• 缺点

  • 对应不可预测性，可控性较差。若游戏需要特定时刻让agent做出特定行为，你就必须用更脚本化的动作重写效用计算过程

  • 需要付出很高成本才能保证游戏中的agent表现得很聪明且具有强大的响应能力

    • 核心架构容易构造，新行为容易添加

    • 调节参数非常挑战

      • 行为并不孤立，往往联系紧密

      • 添加新行为影响其他行为

• 细节

  • 本书第9章

  • Behavioral Mathematics for Game AI, 作者Mark

目标导向的行动规划 GOAP，Goal-Oriented Action Planning

• 定义

  • 概念

    • 行为

    • 预设条件

    • 状态

  • 系统会用一些变量描述世界的初始状态，同时维护一些需要实现的目标集合。

  • GOAP通常会从事先确定的NPC想要实现的目标集合中选出一个目标列表（可以基于目标优先级或NPC当前状态来选择），然后通过规划系统决定行动序列，控制agent并间接影响世界状态，直到使规划目标中定义的事实都满足条件。

  • 具体：“逆向链式检索”，从想要实现的目标开始分析，先规划需要执行什么行动才能实现这个目标，然后得出刚才规划出的行动需要满足什么样的预设条件，以此类推直到起始状态。

    • 目标->行动+预设条件->...->初始状态

    • 我理解和“终局思维”有点像

    • 对应的，基于效用的系统实际上是一种“正向链式检索”：基于启发搜索、剪枝以及其他技巧。

• 算法

  • 把目标加入待解决事实列表中

  • 遍历待解决事实列表中的每个事实

    • 将其从列表中移除

    • 查找可以导致该事实发生的行动

    • 如果查到的行动其预设条件满足

      • 将该行动加入到计划中

      • 回溯检测待解决事实列表，查到现在可以支持的行动（上一步相当于更新了可以支持的行动），并加入到计划中

    • 否则

      • 把该行动的预设条件加入到待解决事实列表中

• 应用

  • FEAR，Just Cause 2和Deus Ex: Human Revolution

• 优点

  • 简化开发流程，让设计师集中精力创建简单的组件

• 缺点

  • 降低开发团队对AI行为的控制力与引导力

分层任务网络 HTN， Hierarchical Task Network

• 定义

  • 概念

    • 初始游戏状态

    • 代表要解决问题的根任务（root task）

    • 根任务表示的是一种具有较高层次抽象等级的任务（高层任务/复合任务），这类任务会在规划过程中被分解为越来越小的任务，直到最后一个由不可再分的任务（基元任务）组成的计划，该计划可以用来直接解决最开始定义的问题。

  • 正向规划器

    • 与GOAP区别，GOAP是逆向规划器

    • GOAP从期望的游戏世界状态开始，逐步回溯，直到当前游戏世界状态

    • HTN从当前游戏世界状态开始，尝试规划出一个期望的解决方案

• 算法

  • 把根复合任务加入到待分解列表中

  • 遍历待分解列表中的每个任务

    • 从待分解列表中移除该任务

    • 如果该任务是复合任务

      • 依次检查与该任务关联的所有实现方法，判断实现方法的预设条件是否在当前世界状态下被满足

      • 如果有实现方法满足条件，就把该方法的任务组加到待分解列表中

      • 如果没有，规划器会回溯到上一次任务的任务分解逻辑

    • 如果该任务是基元任务

      • 把任务的效果应用到当前世界状态上

      • 把任务加到最终计划列表中

• 应用

  • 杀戮地带2 KillZone2

  • 变形金刚：赛伯坦的陨落

• 优点

  • 设计师容易理解，方便与程序员合作

  • 模块化，基元任务可复用

• 缺点

  • HTN的检索是基于图的，深度和图中元素数量级会影响搜索时间

  • 降低了对AI的控制力

总结

• AI程序员有必要掌握各种（行为选择，决策）算法的最佳适用场景

  • 游戏类型

  • NPC的知识表示结构

  • 游戏的目标平台

  • 其他各种因素

• 花时间认真思考游戏需求，一定可以构建出一套既能平衡开发时间与完成度，又能带给玩家最佳体验的AI系统。

XMind - Trial Version