HTN实现浅析

Hierarchical Task Network（HTN）分层任务网络是一种常见的游戏AI规划方案。类似于行为树，HTN提供了在不同条件分支下执行不同任务的能力，但是相比于行为树Runtime响应式的执行，HTN更拥有着一种全局规划的能力。

当前版本比较潦草，仅仅为了记录，后续会陆续修改

HTN类似于行为树有一个树形的执行流，所执行的单位也是类似于行为树的Task（这也说明了行为树和HTN的结构非常类似）。但是在执行树的任务之前，会先做一个全局规划，以深度优先搜索的策略遍历整颗树，将所有匹配的Task(这里的Task存在先后顺序，Task也不一定是叶子节点)按顺序存在TaskQueue中，在实际执行阶段，再依次从队列中执行Task。这里还有一个非常重要的特性，除了上文说的Task不是叶子节点，可以显式的在树结构中构建Task的执行顺序以外。Task本质上还是一个HierarchicalTask,简单说就是Task可以是一个SubHTN，SubHTN中又包含了一系列Task，所有我们这里可以约定最终执行Task为PrimitiveTask。显然这种分层设计提供了一种分而治之的设计能力。不过因为行为树也支持SubTree,所以个人认为HTN优点还是在于规划能力，以及在规划的策略下对Ai行为的设计，更趋向于宏观角度。

HTN简单来说分为两个阶段

Planning 构建计划
Running 执行阶段

后续的部分会着重分析上述两个阶段,所有的代码均以类C++的伪码形式，修改自UE行为树插件

1. HTN实现阶段分析

1.Planning

Planning阶段就是一次行为的规划，目的遍历HTNTree获取所有PrimitiveTask。因为HTNTree根据之前的简述是一颗分层树的结构，所以我们以深度优先搜索的方式从根节点来遍历整棵树。一种典型的优先搜索的实现方式是用栈来存放待处理的节点，每次出栈一个节点处理，并将产生的SubNodes/ChildrenNodes压入栈，依次执行到栈为空，文字伪码描述的执行过程如下：

增加根复合任务到分解列表中
对于每个在我们分解列表中的任务（for）
　　移除任务
　　如果任务是复合任务
　　　　找到满足当前条件状态并且能处理该复合任务的方法
　　　　如果该方法找到了，增加方法的任务到分解列表中
　　　　如果没找到，恢复到之前分解任务的状态中
　　如果任务是原始任务
　　　　在当前状态下执行任务
　　　　增加任务到最终计划列表

这个过程非常简单，但是依然有一些不同于普通深度遍历的点需要考虑。接下来将分析其中一些细节的实现，以UEHTN插件的实现作为例子 UAITask_MakeHTNPlan派生于UE::AITask，是一个生命周期和AI同级的对象，专门负责Planning阶段的对象

Members:

PlanHeap 如上文所说的计划栈
CurrentPlanStepID 当前计划极端
CurrentPlanToExpand 当前需要去展开处理的Plan

在AITask::Active时（即当AI激活时）执行Planning

UAITask_MakeHTNPlan::DoPlanning()
    while(true)
    {
        // 类似深度优先搜索
        CurrentPlanToExpand = DequeueCurrentBestPlan()
        if (CurrentPlanToExpand)
        {
            MakeExpansionsOfCurrentPlan(CurrentPlanToExpand)
        }
    }

UAITask_MakeHTNPlan::DequeueCurrentBestPlan
    return PlanHeap.HeapPop()

得到PlanToExpand后，执行MakeExpansions

UAITask_MakeHTNPlan::MakeExpansionsOfCurrentPlan()
    // 获取当前Plan下的WorldState和Nodes,这里会从Plan中的当前TaskNode获取子节点
    TSharedPtr<FBlackboardWorldState> WorldState;
	TArrayView<UHTNStandaloneNode*> NextNodes;
	CurrentPlanToExpand->GetWorldStateAndNextNodes(CurrentPlanStepID, WorldState, NextNodes);
    foreach(var node in NextNodes)
    {
        MakeExpansionsOfCurrentPlan(WorldState, Node)
        {
            // Initialize
            Node->Init()

            // Check condition
            // 主要检查WorldState，注意WorldState会在Planning阶段随着PlanSubmit而改变
            if (!EnterDecorators())
                continue;

            // Make plane
            Node->MakePlanExpansions()
        }
    }

每个HTNTaskNode自己执行规划，传入PlanningContext

+ HTNTask::MakePlanExpansions(PlanningContext)
+ HTNTask::CreatePlanSteps() 
    Task规划阶段主要是对WorldState备份状态的修改，以及添加到PlanningTaskList
    - NewWorldState = WorldState->MakeNext();  
    - NewWorldState->SetValue（Key, Value);  
    - UAITask_MakeHTNPlan.SubmitPlanStep(this, NewWorldState, cost);  

UAITask_MakeHTNPlan收到Node调用SubmitPlanStep后，会接受Plan，放入待执行队列, 同时也将接受WorldState的改变

UAITask_MakeHTNPlan::SubmitPlanStep(Task, NewWorldState, cost)
    // 复制创建了一个新的Plan并添加了新的Task
    var AddedPlanStep = nullptr
    var NewPlan = PlanningContext.MakePlanCopyWithAddedStep(AddedStep, AddedStepID);
    NewPlan->Cost += AddedStep->Cost;

    // Submit plan!!
    CurrentPlanningContext.SubmitCandidatePlan(NewPlan, Description);
        PlanHeap.push(NewPlan)

    添加到PlanHeap后，会在下一次DoPlanning中去执行

2. Running

Running阶段基本上和行为树类似，只是按顺序执行RunningPlan中的PlanStep,注意之前步骤的MakePlanning只是为了收集需要执行的Task队列，为了规划所做的WorldState创建都是基于期望的备份修改，实际执行过程中，依然需要按步骤一次执行，所有的EnterConditiong依然需要去检测

2.1 基础的数据结构

enum class EHTNTaskStatus : uint8
{
	Active,
	Aborting,
	Inactive
};

enum class EHTNNodeResult : uint8
{
	// Finished as success
	Succeeded,
	// Finished as failure
	Failed,
	// Finished aborting = failure
	Aborted,
	// Not finished yet
	InProgress
};

接下来定义下Plan中Level的定义（个人认为更类似于深度）普通Task节点的顺序执行时Level不变，也就是说Level只会收到一些特殊的Composite节点而产生影响，例如Branch在产生分支，每个分支都会是新的不同的Level。或者通俗的说只是以Level划分不同的执行队列，只是为了基于不同Composite节点实现不同的执行流控制

struct HTNLevel
{
    TArray<FHTNPlanStep> Steps;
}

2.2 获取下一个原子任务

FHTNGetNextStepsContext 先看一下如何从当前Plan中获取下一个原子任务,并添加到PendingExecutionStepIDs

UHTNPlanInstance::GetNextPrimitiveStepsInCurrentPlan(&PendingExecutionStepIDs)
{
    auto& OutStepIDs = PendingExecutionStepIDs;
	FHTNGetNextStepsContext Context(*this, *CurrentPlan, bIsExecutingPlan, OutStepIDs);
	Context.AddNextPrimitiveStepsAfter(StepID);
	return Context.GetNumSubmittedSteps();    
}

FHTNGetNextStepsContext::SubmitPlanStep()
{
    OutStepIds.Add(PlanStepID);
	++curSubmitted;
}

FHTNGetNextStepsContext::AddNextPrimitiveStepsAfter(StepID)
{
    // 获取当前Level下，下一个有效的TaskStep
    // 
    // 即遍历当前Level下所有Steps，递归GetNextPrimitiveSteps
    // 一旦有新的StepSubmitted，则直接返回
    FHTNPlanLevel& Level = *Levels[CurrentStepID.LevelIndex];
    for (int32 StepIndex = InStepID.StepIndex + 1; StepIndex < Level.Steps.Num(); ++StepIndex)
	{
		const FHTNPlanStep& CandidateStep = Level.Steps[StepIndex];
		CandidateStep.Node->GetNextPrimitiveSteps(*this, {InStepID.LevelIndex, StepIndex});
        if (const int32 NumSubmittedNow = GetNumStepsSubmittedNow())
		{
			return NumSubmittedNow;
		}
	}
}

2.2 Tick执行过程

UHTNPlanInstance

UHTNPlanInstance::TickCurrentPlan(float DeltaTime)
    StartTasksPendingExecution()


UHTNPlanInstance::StartTasksPendingExecution
    var stepID = PendingExecutionStepIDs.pop()
    StartExecuteTask(StartExecuteTask)

UHTNPlanInstance::StartExecuteTask(PlanStepID)

    const FHTNPlanStep& PlanStep = CurrentPlan->GetStep(PlanStepID);
	UHTNTask& Task = *CastChecked<UHTNTask>(PlanStep.Node);

    // 添加到ExecutingQueue
	check(!CurrentlyExecutingStepIDs.Contains(PlanStepID));
	CurrentlyExecutingStepIDs.Add(PlanStepID);

    // Subnodes Begin

    // Subnodes end

    // Execute the current task
	uint8* const TaskMemory = GetNodeMemory(PlanStep.NodeMemoryOffset);
	const EHTNNodeResult Result = Task.ExecuteTask(TaskMemory);
	if (Result != EHTNNodeResult::InProgress && CurrentlyExecutingStepIDs.Contains(PlanStepID))
		OnTaskFinished(&Task, TaskMemory, PlanStepID, Result);

	return Result;

每个HTNTaskNode执行任务

HTNTask::ExecuteTask(RuntimeMemory) -> return EHTNodeResult
    // 首先为了节省内存，类似于行为树的做法，采用静态的树节点结构和每个实例的RuntimeNode
    // RuntimeNode只包含了少量的Runtime数据
    HTNTaskRuntime* const RuntimeNode = CastInstanceNodeMemory<HTNTaskRuntime>(RuntimeMemory);   
    var result = EHTNNodeResult::Succeeded;

    // Do something...

    // Return result
    return result;

例如一个HTNTask_Move任务的Execute如下：

HTNTask_Move::ExecuteTask(RuntimeNode)

3. 部分细节分析

1. Parallel实现分析

</br>

参考引用:

[1] https://www.jianshu.com/p/196962c7ae6a 一篇文章搞懂hierarchical task network(HTN)-通过实例探讨分层任务网络规划