游戏AI行为决策——HTN前言
Hierarchical Task Network(分层任务网络),简称HTN,与行为树、GOAP一样,也是一种行为决策方法。在《地平线:零之曙光》、《变形金刚:塞伯坦的陨落》中都有用它来制作游戏敌人的AI (我一个都没玩过捏。比起其它行为决策方法,HTN有个十分鲜明的特点:推演。
HTN允许我们把要做的事以高度复杂的「复合任务」来表示,而不是单单一个行为。什么意思呢?无论是有限状态机状态的转换,还是行为树节点的切换,大多时候只是从一个执行动作变为执行另一个动作。而HTN的一次规划,可以一口气规划出包含好几个动作的「复合任务」,你看到它做出的新动作,也不过是之前就计划好的一部分。
这么看来,好像还有点预知未来的味道呢,说得越来越玄乎了,直接来看看它的运行逻辑吧!
运行逻辑
HTN的整体结构框架如下:
别怕,看着复杂而已,相信你能够理解的:
1. 任务
首先,和其它行为决策方法一样,角色内部有存储一系列要做的事。在有限状态机中是「状态」,行为树中是「动作节点」,而HTN中是 「任务(Task)」。但要注意,HTN的「任务」十分特殊,它不只是单一的动作,可能包含多个动作,总的可以分为三种:「复合任务」、「方法」以及「原子任务」。
- 原子任务,是最简单的任务,只是单一的动作,像「奔跑」、「跳跃」等就算是原子任务。通常也不建议把一个原子任务设计得太复杂。
- 复合任务,是……“哦,我知道,一定是多个原子任务组合成的,对不对?”( ⓛ ω ⓛ *),很可惜,并不完全正确。复合任务是由多个「方法」组合而成的,而每次执行复合任务,只会选择组成它的众多「方法」之一来执行,就像行为树的选择节点一样。
- 方法,方法是HTN让角色行动丰富的关键,一个方法可以由多个「原子任务」或「复合任务」组合而成。在「方法」的帮助下,我们可以自然且清晰地构建丰富的行为。以「砍树」为例,可以构造成这个样子:
方法的执行,会逐一判断组成的「复合任务」和「原子任务」是否满足条件,只要有一个不满足,这个方法便会被放弃,它有点像行为树中的顺序节点。
这里要多说一嘴,「复合任务」和「方法」只会在HTN的规划阶段被执行。所谓「规划阶段」,就是根据「世界状态」来决定该做什么事,规划时会把要做的「复合任务」和「方法」统统分解成一个个「原子任务」。也就是说,最终角色实际执行的都是「原子任务」。
2. 世界状态
在游戏常用的决策行为算法中,只有GOAP和HTN有用到「世界状态」。其实这是更接近传统人工智能的设计方式(GOAP和HTN也确实是由传统人工智能转变来的),还是以「砍树」为例,想要让一个角色去砍树,他就得知道:哪里有树、哪里有电锯、电锯有多少油……这些 做事的前提 都可以归为「世界状态」的一员,反过来说,世界状态就是这类「前提条件」的集合,它们共同构成了HTN任务规划的基础。
在规划阶段,角色会复制一份「世界状态」的副本用于个人判断并选出可执行的任务,就好像是侦探拿着照片进行脑补推断一样。这个过程不会影响真正的「世界状态」。而在选出了可执行的任务后,就会将它分解成一系列「原子任务」挨个执行。有些(或者说大多数)「原子任务」执行完成后会对「世界状态」造成一定影响,比如开枪会减少弹药数,锯完树会减少树木数量等等。但要注意,这里的影响就不再是“脑补”的啦,而是真正改变「世界状态」的某些值。就像是部队制定完计划后,就开始正式行动了。
3. 总结
通过上述两大点,我想已经能大概弄清楚HTN的运行逻辑了吧(如果还是很懵,可以看看这个视频相关部分的介绍):根据世界状态来选择要执行的任务,再将选好的任务分解为一个个原子任务来执行,而原子任务执行完后又会影响世界状态。一旦分解出的原子任务都执行完了,又或者某个原子任务的执行条件突然不能满足了,就重新选择,重复这个步骤。这就是HTN大体的运行逻辑了。
代码实现
这次代码实现同样参考了Steve Rabin的《Game AI Pro》,相比之前我们实现的行为树,这次所要写的类不会太多(除去注释的话就更少了)。
1. 世界状态
世界状态实现的难点在于:
- 状态数据的类型是多种多样的,该用什么来统一保存?
- 状态数据会时时变化,如何保证存储的数据也会同步更新?
对于问题1,我们可以用 的字典来解决。毕竟C#中,object类是所有数据类型的老祖宗。那问题2呢,假设用这种字典存储了某个角色的血量,那这个角色就算血量变成0了,字典里存储的也只是刚存进去时的那个值而不是0。而且反过来,我们修改字典里的这个血量值,也不会影响实际角色的血量……除非,这些值能像属性一样……
这是可以做到的!但要用到两个字典,一个用来模仿属性的get,一个用来模仿属性的set。分别用值类型为System.Action
到这里我得再说一下,如果对于上面这几段话中的一些名词你有些许疑惑的话,就该再学习一下C#啦( ̄、 ̄),否则你可能不能理解世界状态类的实现:
//世界状态只有一个即可,我们将其设为静态类public static class HTNWorld{ //读 世界状态的字典 private static readonly Dictionary<string, Func> get_WorldState; //写 世界状态的字典 private static readonly Dictionary<string, Action> set_WorldState; static HTNWorld() { get_WorldState = new Dictionary<string, Func>(); set_WorldState = new Dictionary<string, Action>(); } //添加一个状态,需要传入状态名、读取函数和写入函数 public static void AddState(string key, Func getter, Action setter) { get_WorldState[key] = getter; set_WorldState[key] = setter; } //根据状态名移除某个世界状态 public static void RemoveState(string key) { get_WorldState.Remove(key); set_WorldState.Remove(key); } //修改某个状态的值 public static void UpdateState(string key, object value) { //就是通过写入字典修改的 set_WorldState[key].Invoke(value); } //读取某个状态的值,利用泛型,可以将获取的object转为指定的类型 public static T GetWorldState(string key) { return (T)get_WorldState[key].Invoke(); } //复制一份当前世界状态的值(这个主要是用在规划中) public static Dictionary CopyWorldState() { var copy = new Dictionary(); foreach(var state in get_WorldState) { copy.Add(state.Key, state.Value.Invoke()); } return copy; }}
2. 任务类接口
「复合任务」、「方法」和「原子任务」它们有共通之处,我们把这些共通之处以接口的形式提炼出来,可以简化我们在规划环节的代码逻辑。
//用于描述运行结果的枚举(如果有看上一篇行为树的话,也可以直接用行为树的EStatus)public enum EStatus{ Failure, Success, Running, }public interface IBaseTask{ //是否满足条件 bool MetCondition(); //添加子任务 void AddNextTask(IBaseTask nextTask);}
3. 原子任务
原子任务是一个抽象类,相当于行为树中的动作节点,用于开发者自定义的最小单元任务。一般就是像「开火」、「奔跑」之类的简单动作。值得注意的是,这里的条件判断和执行影响都要分两种情况,一种是规划时,一种是实际执行时,因为规划时我们使用的并不是真正的世界状态,而是一份模拟的世界状态副本。
public abstract class PrimitiveTask : IBaseTask{ //原子任务不可以再分解为子任务,所以AddNextTask方法不必实现 void IBaseTask.AddNextTask(IBaseTask nextTask) { throw new System.NotImplementedException(); } /// /// 执行前判断条件是否满足,传入null时直接修改HTNWorld /// /// 用于plan的世界状态副本 public bool MetCondition(Dictionary worldState = null) { if(worldState == null)//实际运行时 { return MetCondition_OnRun(); } else//模拟规划时 { return MetCondition_OnPlan(worldState); } } protected virtual bool MetCondition_OnPlan(Dictionary worldState) { return true; } protected virtual bool MetCondition_OnRun() { return true; } //任务的具体运行逻辑,交给具体类实现 public abstract EStatus Operator(); /// /// 执行成功后的影响,传入null时直接修改HTNWorld /// /// 用于plan的世界状态副本 public void Effect(Dictionary worldState = null) { if(worldState == null)//实际运行时 { Effect_OnRun(); } else //模拟运行时 { Effect_OnPlan(worldState); } } protected virtual void Effect_OnPlan(Dictionary worldState) { ; } protected virtual void Effect_OnRun() { ; }}
4. 方法
方法既可以添加「复合任务」又可以添加「原子任务」作组成的子任务,所以我们用IBaseTask列表来存储;而方法的满足与否,要看两个条件,具体看代码注释吧:
public class Method : IBaseTask{ //子任务列表,可以是复合任务,也可以是原点任务 public List SubTask { get; private set; } //方法的前提条件 private readonly Func condition; public Method(Func condition) { SubTask = new List(); this.condition = condition; } //方法条件满足的判断=方法本身前提条件满足+所有子任务条件满足 public bool MetCondition(Dictionary worldState) { if (condition())//方法自身的前提条件是否满足 { for (int i = 0; i < SubTask.Count; ++i) { //一旦有一个子任务的条件不满足,这个方法就不满足了 if (!SubTask[i].MetCondition(worldState)) { return false; } } return true;//如果子任务全都满足了,那就成了! } return false; } //添加子任务 public void AddNextTask(IBaseTask nextTask) { SubTask.Add(nextTask); }}
5. 复合任务
复合任务和「方法」类似,只不过只能添加「方法」作为子任务。
public class CompoundTask : IBaseTask{ //选中的方法 public Method ValidMethod { get; private set; } //子任务(方法)列表 private readonly List methods; public CompoundTask() { methods = new List(); } public void AddNextTask(IBaseTask nextTask) { //要判断添加进来的是不是方法类,是的话才添加 if (nextTask is Method m) { methods.Add(m); } } public bool MetCondition(Dictionary worldState) { for (int i = 0; i < methods.Count; ++i) { //只要有一个方法满足前提条件就可以 if(methods[i].MetCondition(worldState)) { //记录下这个满足的方法 ValidMethod = methods[i]; return true; } } return false; }}
到这里,基本的组件类就全部完成了,对比行为树那章,代码量很少对吧?接下来就是有关构造的类了:
6. 规划器
规划器的要点在于对「复合任务」的分解,这里提一下,一个HTN会保证有一个复合任务做为根任务,就和行为树的根节点一样。分解也是由此开始:
public class HTNPlanner{ //最终分解完成的所有原子任务存放的列表 public Stack FinalTasks { get; private set; } //分解过程中,用来缓存被分解出的任务的栈,因为类型各异,故用IBaseTask类型 private readonly Stack taskOfProcess; private readonly CompoundTask rootTask;//根任务 public HTNPlanner(CompoundTask rootTask) { this.rootTask = rootTask; taskOfProcess = new Stack(); FinalTasks = new Stack(); } //规划(核心) public void Plan() { //先复制一份世界状态 var worldState = HTNWorld.CopyWorldState(); //将存储列表清空,避免上次计划结果的影响 FinalTasks.Clear(); //将根任务压进栈中,准备分解 taskOfProcess.Push(rootTask); //只要栈还没空,就继续分解 while(taskOfProcess.Count > 0) { //拿出栈顶的元素 var task = taskOfProcess.Pop(); //如果这个元素是复合任务 if(task is CompoundTask cTask) { //判断是否可以执行 if(cTask.MetCondition(worldState)) { /*如果可以执行,就肯定有可用的方法, 就将该方法的子任务都压入栈中,以便继续分解*/ var subTask = cTask.ValidMethod.SubTask; foreach(var t in subTask) { taskOfProcess.Push(t); } /*通过上面的步骤我们知道,能被压进栈中的只有 复合任务和原子任务,方法本身并不会入栈*/ } } else //否则,这个元素就是原子任务 { //将该元素转为原子任务,因为原本是IBaseTask类型 var pTask = task as PrimitiveTask; //判断是否满足执行条件 if(pTask.MetCondition(worldState)) { //如果满足,就让它对复制的世界状态产生影响(模拟其真实发生) pTask.Effect(worldState); //再将该原子任务加入存放分解完成的任务列表 FinalTasks.Push(pTask); } } } }}
7. 执行器
执行器的关键在于如何确认一个原子任务是否执行完成,并且要在执行完成后产生影响并切换到下一个原子任务。
public class HTNPlanRunner{ //当前运行状态 private EStatus curState; //直接将规划器包含进来,方便重新规划 private readonly HTNPlanner planner; //当前执行的原子任务 private PrimitiveTask curTask; //标记「原子任务列表是否还有元素、能够继续」 private bool canContinue; public HTNPlanRunner(HTNPlanner planner) { this.planner = planner; curState = EStatus.Failure; } public void RunPlan() { //如果当前运行状态是失败(一开始默认失败) if(curState == EStatus.Failure) { //就规划一次 planner.Plan(); } //如果当前运行状态是成功,就表示当前任务完成了 if(curState == EStatus.Success) { //让当前原子任务造成影响 curTask.Effect(); } /*如果当前状态不是「正在执行」,就取出新一个原子任务作为当前任务 无论失败还是成功,都要这么做。因为如果是失败,肯定在代码运行到这 之前,已经进行了一次规划,理应获取新规划出的任务来运行;如果是因 为成功,那也要取出新任务来运行*/ if(curState != EStatus.Running) { //用TryPop的返回结果判断规划器的FinalTasks是否为空 canContinue = planner.FinalTasks.TryPop(out curTask); } /*如果canContinue为false,那curTask会为null也视作失败(其实应该是「全部 完成」,但全部完成和失败是一样的,都要重新规划)。所以只有当canContinue && curTask.MetCondition()都满足时,才读取当前原子任务的运行状态,否则就失败。*/ curState = canContinue && curTask.MetCondition() ? curTask.Operator() : EStatus.Failure; }}
差不多所有东西都完成了,为了方便使用,我们和上篇写行为树时一样,也做一个构造器:
8. 构造器
构造器会自带规划器和执行器,并将任务的创建打包成函数。也和上篇行为树一样,用栈的方式描述构建过程,提供一定可视化。
public partial class HTNPlanBuilder{ private HTNPlanner planner; private HTNPlanRunner runner; private readonly Stack taskStack; public HTNPlanBuilder() { taskStack = new Stack(); } private void AddTask(IBaseTask task) { if (planner != null)//当前计划器不为空 { //将新任务作为构造栈顶元素的子任务 taskStack.Peek().AddNextTask(task); } else //如果计划器为空,意味着新任务是根任务,进行初始化 { planner = new HTNPlanner(task as CompoundTask); runner = new HTNPlanRunner(planner); } //如果新任务是原子任务,就不需要进栈了,因为原子任务不会有子任务 if (task is not PrimitiveTask) { taskStack.Push(task); } } //剩下的代码都很简单,我相信能直接看得懂 public void RunPlan() { runner.RunPlan(); } public HTNPlanBuilder Back() { taskStack.Pop(); return this; } public HTNPlanner End() { taskStack.Clear(); return planner; } public HTNPlanBuilder CompoundTask() { var task = new CompoundTask(); AddTask(task); return this; } public HTNPlanBuilder Method(System.Func condition) { var task = new Method(condition); AddTask(task); return this; }}
我还是来简单画图,示意一下构建栈得运作过程吧:
- 加入一个复合节点0后:
- 往这个复0加一个方法作为一个子任务:
- 如果要向复0再加一个方法,就要调用Back函数,再添加:
总之,用Back调整栈顶的元素,我们可以自由地控制新任务作为谁的子任务。而且通过缩进可以较直观的看到HTN的整个结构,例如下面这样:
//节选自我某个小游戏里的一个小怪的行动protected override void Start(){ base.Start(); trigger = Para.HeathValue * 0.5f; hTN.CompoundTask() .Method(() => isHurt) .Enemy_Hurt(this) .Enemy_Die(this) .Back() .Method(() => curHp HTNWorld.GetWorldState("PlayerHp") > 0) .Enemy_Check(this) .Enemy_Track(this, PlayerTrans) .Enemy_Atk(this) .Back() .Method(() => true) .Enemy_Idle(this, 3f) .End();}
上述中的Enemy_Check、Enemy_Atk都是实际开发实现的具体原子行为。现在再来看,发现还是有问题的,HTN擅长规划,其实并不擅长时时决策,所以在实际开发时,建议与有限状态机结合。将受伤、死亡这类需要时时反馈的事交给状态机,HTN本身也可以放进一个状态,来进行复杂行为。而不是像我这样,将受伤、死亡也当成原子任务,因为这样做就要你为各个行为设计受伤中断,代码就会比较繁冗。
“状态机+其它”的复合决策模型并不罕见,GOAP也经常以这种形式出现。
最后分享一些设计原子任务的心得:
- 如果一个原子任务有一定的运行过程,可以用一个bool值在Operator函数内部判断是否完成了动作。
- 因为我们的世界状态是用字符串来读取的,如果我们想获取某个士兵的血量该怎么办?有很多士兵在,该如何区分?可以用Unity的GetInstanceID()获取唯一的ID+“血量”,组合成字符串来区分,其它类似情况同理。
能说的都说的差不多了,真正要了解HTN还是应当自己上手使用,鄙人也只是结合个人的学习和使用心得写出了这篇文章。有不足或不清楚的可以评论哈 (只是我不常看账号,可能不会回复
完毕!\ ( ̄︶ ̄*\ )