游戏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. 状态数据的类型是多种多样的，该用什么来统一保存？
2. 状态数据会时时变化，如何保证存储的数据也会同步更新？

对于问题1，我们可以用 <string, object> 的字典来解决。毕竟C#中，object类是所有数据类型的老祖宗。那问题2呢，假设用这种字典存储了某个角色的血量，那这个角色就算血量变成0了，字典里存储的也只是刚存进去时的那个值而不是0。而且反过来，我们修改字典里的这个血量值，也不会影响实际角色的血量……除非，这些值能像属性一样……

这是可以做到的！但要用到两个字典，一个用来模仿属性的get，一个用来模仿属性的set。分别用值类型为System.Action< object > 和 System.Func< object >的字典就可以了。

到这里我得再说一下，如果对于上面这几段话中的一些名词你有些许疑惑的话，就该再学习一下C#啦(￣、￣)，否则你可能不能理解世界状态类的实现：

//世界状态只有一个即可，我们将其设为静态类
public static class HTNWorld
{
    //读 世界状态的字典
    private static readonly Dictionary<string, Func<object>> get_WorldState;
    //写 世界状态的字典
    private static readonly Dictionary<string, Action<object>> set_WorldState;
    
    static HTNWorld()
    {
        get_WorldState = new Dictionary<string, Func<object>>();
        set_WorldState = new Dictionary<string, Action<object>>();
    }
    //添加一个状态，需要传入状态名、读取函数和写入函数
    public static void AddState(string key, Func<object> getter, Action<object> 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<T>(string key) 
    {
        return (T)get_WorldState[key].Invoke();
    }
    //复制一份当前世界状态的值（这个主要是用在规划中）
    public static Dictionary<string, object> CopyWorldState()
    {
        var copy = new Dictionary<string, object>();
        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();
    }

    /// <summary>
    /// 执行前判断条件是否满足，传入null时直接修改HTNWorld
    /// </summary>
    /// <param name="worldState">用于plan的世界状态副本</param>
    public bool MetCondition(Dictionary<string, object> worldState = null)
    {
        if(worldState == null)//实际运行时
        {
            return MetCondition_OnRun();
        }
        else//模拟规划时
        {
            return MetCondition_OnPlan(worldState);
        }
    }
    protected virtual bool MetCondition_OnPlan(Dictionary<string, object> worldState)
    {
        return true;
    }
    protected virtual bool MetCondition_OnRun()
    {
        return true;
    }
    
    //任务的具体运行逻辑，交给具体类实现
    public abstract EStatus Operator();

    /// <summary>
    /// 执行成功后的影响，传入null时直接修改HTNWorld
    /// </summary>
    /// <param name="worldState">用于plan的世界状态副本</param>
    public void Effect(Dictionary<string, object> worldState = null)
    {
        if(worldState == null)//实际运行时
        {
            Effect_OnRun();
        }
        else //模拟运行时
        {
            Effect_OnPlan(worldState);
        }
    }
    protected virtual void Effect_OnPlan(Dictionary<string, object> worldState)
    {
        ;
    }
    protected virtual void Effect_OnRun()
    {
        ;
    }
}

4. 方法

方法既可以添加「复合任务」又可以添加「原子任务」作组成的子任务，所以我们用IBaseTask列表来存储；而方法的满足与否，要看两个条件，具体看代码注释吧：

public class Method : IBaseTask
{
    //子任务列表，可以是复合任务，也可以是原点任务
    public List<IBaseTask> SubTask { get; private set; }
    //方法的前提条件
    private readonly Func<bool> condition;

    public Method(Func<bool> condition)
    {
        SubTask = new List<IBaseTask>();
        this.condition = condition;
    }
    //方法条件满足的判断=方法本身前提条件满足+所有子任务条件满足
    public bool MetCondition(Dictionary<string, object> 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<Method> methods;
    
    public CompoundTask()
    {
        methods = new List<Method>();
    }
    
    public void AddNextTask(IBaseTask nextTask)
    {
        //要判断添加进来的是不是方法类，是的话才添加
        if (nextTask is Method m)
        {
            methods.Add(m);
        }
    }
    
    public bool MetCondition(Dictionary<string, object> 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<PrimitiveTask> FinalTasks { get; private set; }
    //分解过程中，用来缓存被分解出的任务的栈，因为类型各异，故用IBaseTask类型
    private readonly Stack<IBaseTask> taskOfProcess;
    private readonly CompoundTask rootTask;//根任务
    
    public HTNPlanner(CompoundTask rootTask)
    {
        this.rootTask = rootTask;
        taskOfProcess = new Stack<IBaseTask>();
        FinalTasks = new Stack<PrimitiveTask>();
    }
    //规划（核心）
    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<IBaseTask> taskStack;
    
    public HTNPlanBuilder()
    {
        taskStack = new Stack<IBaseTask>();
    }
    
    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<bool> 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 <= trigger)
                .Enemy_Combo(this, 3)
                .Enemy_Rest(this, "victory")
                .Back()
            .Method(() => HTNWorld.GetWorldState<float>("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也经常以这种形式出现。

最后分享一些设计原子任务的心得：

1. 如果一个原子任务有一定的运行过程，可以用一个bool值在Operator函数内部判断是否完成了动作。
2. 因为我们的世界状态是用字符串来读取的，如果我们想获取某个士兵的血量该怎么办？有很多士兵在，该如何区分？可以用Unity的GetInstanceID()获取唯一的ID+“血量”，组合成字符串来区分，其它类似情况同理。

能说的都说的差不多了，真正要了解HTN还是应当自己上手使用，鄙人也只是结合个人的学习和使用心得写出了这篇文章。有不足或不清楚的可以评论哈 （只是我不常看账号，可能不会回复

完毕！\ (￣︶￣*\ )

本栏目推荐文章
• 认知行为疗法-中对认知的理解
• Dating Java8系列之通过行为参数化传递代码
• 设计模式—行为型模式之状态模式
• 游戏AI行为决策——MLP（多层感知机/人工神经网络）
• 【技术推荐】我愿称之为开源界最好用的行为验证码
• 设计模式—行为型模式之策略模式
• java split 无效 ，由于split()函数的默认行为是去除匹配分隔符周围的空格，导致程序运行不符合预期
• Dating Java8系列之通过行为参数化传递代码
• 数据分享|用户消费行为分析预测模型、重庆市的政策数据分析
• 程序员软技能：学会从心理和历史的角度来理解理财行为

行为 HTN行为htn htn 行为 行为分析 行为wpf 行为eplan 行为 密码 vuerouter行为 消费行为 人类 行为ai