思维导图
?
文字版
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