【USparkle專欄】如果你深懷絕技，愛“搞點研究”，樂于分享也博采眾長，我們期待你的加入，讓智慧的火花碰撞交織，讓知識的傳遞生生不息！

這是侑虎科技第1855篇文章，感謝作者狐王駕虎供稿。歡迎轉(zhuǎn)發(fā)分享，未經(jīng)作者授權(quán)請勿轉(zhuǎn)載。如果您有任何獨到的見解或者發(fā)現(xiàn)也歡迎聯(lián)系我們，一起探討。（QQ群：793972859）

作者主頁：

https://home.cnblogs.com/u/OwlCat

一、前言

Hierarchical Task Network（分層任務(wù)網(wǎng)絡(luò)），簡稱HTN，與行為樹、GOAP一樣，也是一種行為決策方法。在《地平線：零之曙光》、《變形金剛：塞伯坦的隕落》中都有用它來制作游戲敵人的AI。比起其它行為決策方法，HTN有個十分鮮明的特點：推演。

HTN允許我們把要做的事以高度復雜的「復合任務(wù)」來表示，而不是單單一個行為。什么意思呢？無論是有限狀態(tài)機狀態(tài)的轉(zhuǎn)換，還是行為樹節(jié)點的切換，大多時候只是從一個執(zhí)行動作變?yōu)閳?zhí)行另一個動作。而HTN的一次規(guī)劃，可以一口氣規(guī)劃出包含好幾個動作的「復合任務(wù)」，你看到它做出的新動作，也不過是之前就計劃好的一部分。

這么看來，好像還有點預(yù)知未來的味道呢，說得越來越玄乎了，直接來看看它的運行邏輯吧！

PS：據(jù)后續(xù)反饋，分享一個有應(yīng)用HTN的項目的代碼[1]（也可以用該gitee倉庫[2]）HTN使用的主要部分在該項目的Script/Characters/Enemy部分，有需要的可以參考看看這個HTN的實際使用。

二、運行邏輯

HTN的整體結(jié)構(gòu)框架如下：

別怕，看著復雜而已，相信你能夠理解的：

1. 任務(wù)

首先，和其它行為決策方法一樣，角色內(nèi)部有存儲一系列要做的事。在有限狀態(tài)機中是「狀態(tài)」，行為樹中是「動作節(jié)點」，而HTN中是「任務(wù)（Task）」。但要注意，HTN的「任務(wù)」十分特殊，它不只是單一的動作，可能包含多個動作，總的可以分為三種：「復合任務(wù)」、「方法」以及「原子任務(wù)」。

• 原子任務(wù)：是最簡單的任務(wù)，只是單一的動作，像「奔跑」、「跳躍」等就算是原子任務(wù)。通常也不建議把一個原子任務(wù)設(shè)計得太復雜。

• 復合任務(wù)：只理解為是多個原子任務(wù)組合成的，并不完全正確。復合任務(wù)是由多個「方法」組合而成的，而每次執(zhí)行復合任務(wù)，只會選擇組成它的眾多「方法」之一來執(zhí)行，就像行為樹的選擇節(jié)點一樣。

• 方法：方法是HTN讓角色行動豐富的關(guān)鍵，一個方法可以由多個「原子任務(wù)」或「復合任務(wù)」組合而成。在「方法」的幫助下，我們可以自然且清晰地構(gòu)建豐富的行為。以「砍樹」為例，可以構(gòu)造成這個樣子：

方法的執(zhí)行，會逐一判斷組成的「復合任務(wù)」和「原子任務(wù)」是否滿足條件，只要有一個不滿足，這個方法便會被放棄，它有點像行為樹中的順序節(jié)點。

這里要多說一嘴，「復合任務(wù)」和「方法」只會在HTN的規(guī)劃階段被執(zhí)行。所謂「規(guī)劃階段」，就是根據(jù)「世界狀態(tài)」來決定該做什么事，規(guī)劃時會把要做的「復合任務(wù)」和「方法」統(tǒng)統(tǒng)分解成一個個「原子任務(wù)」。也就是說，最終角色實際執(zhí)行的都是「原子任務(wù)」。

2. 世界狀態(tài)

在游戲常用的決策行為算法中，只有GOAP和HTN有用到「世界狀態(tài)」。其實這是更接近傳統(tǒng)人工智能的設(shè)計方式（GOAP和HTN也確實是由傳統(tǒng)人工智能轉(zhuǎn)變來的），還是以「砍樹」為例，想要讓一個角色去砍樹，他就得知道：哪里有樹、哪里有電鋸、電鋸有多少油……這些做事的前提都可以歸為「世界狀態(tài)」的一員，反過來說，世界狀態(tài)就是這類「前提條件」的集合，它們共同構(gòu)成了HTN任務(wù)規(guī)劃的基礎(chǔ)。

在規(guī)劃階段，角色會復制一份「世界狀態(tài)」的副本用于個人判斷并選出可執(zhí)行的任務(wù)，就好像是偵探拿著照片進行腦補推斷一樣。這個過程不會影響真正的「世界狀態(tài)」。而在選出了可執(zhí)行的任務(wù)后，就會將它分解成一系列「原子任務(wù)」挨個執(zhí)行。有些（或者說大多數(shù)）「原子任務(wù)」執(zhí)行完成后會對「世界狀態(tài)」造成一定影響，比如開槍會減少彈藥數(shù)，鋸完樹會減少樹木數(shù)量等等。但要注意，這里的影響就不再是“腦補”的啦，而是真正改變「世界狀態(tài)」的某些值。就像是部隊制定完計劃后，就開始正式行動了。

3. 總結(jié)

通過上述兩大點，我想已經(jīng)能大概弄清楚HTN的運行邏輯了吧（如果還是很懵，可以看看這個視頻[3]相關(guān)部分的介紹）：根據(jù)世界狀態(tài)來選擇要執(zhí)行的任務(wù)，再將選好的任務(wù)分解為一個個原子任務(wù)來執(zhí)行，而原子任務(wù)執(zhí)行完后又會影響世界狀態(tài)。一旦分解出的原子任務(wù)都執(zhí)行完了，又或者某個原子任務(wù)的執(zhí)行條件突然不能滿足了，就重新選擇，重復這個步驟。這就是HTN大體的運行邏輯了。

三、代碼實現(xiàn)

這次代碼實現(xiàn)同樣參考了Steve Rabin的《Game AI Pro》[4]，相比之前我們實現(xiàn)的行為樹，這次所要寫的類不會太多（除去注釋的話就更少了）。

1. 世界狀態(tài)

世界狀態(tài)實現(xiàn)的難點在于：

1. 狀態(tài)數(shù)據(jù)的類型是多種多樣的，該用什么來統(tǒng)一保存？

2. 狀態(tài)數(shù)據(jù)會時時變化，如何保證存儲的數(shù)據(jù)也會同步更新？

對于問題1，我們可以用 的字典來解決。畢竟C ，Object類是所有數(shù)據(jù)類型的老祖宗。那問題2呢，假設(shè)用這種字典存儲了某個角色的血量，那這個角色就算血量變成0了，字典里存儲的也只是剛存進去時的那個值而不是0。而且反過來，我們修改字典里的這個血量值，也不會影響實際角色的血量……除非，這些值能像屬性一樣……

這是可以做到的！但要用到兩個字典，一個用來模仿屬性的get，一個用來模仿屬性的set。分別用值類型為System.Action和System.Func的字典就可以了。

到這里我得再說一下，如果對于上面這幾段話中的一些名詞你有些許疑惑的話，就該再學習一下C，否則你可能不能理解世界狀態(tài)類的實現(xiàn)：

//世界狀態(tài)只有一個即可，我們將其設(shè)為靜態(tài)類 publicstaticclassHTNWorld {     //讀 世界狀態(tài)的字典     privatestaticreadonly Dictionary

 > get_WorldState;     //寫 世界狀態(tài)的字典     privatestaticreadonly Dictionary

 > set_WorldState;     static HTNWorld()     {         get_WorldState = new Dictionary

 >();         set_WorldState = new Dictionary

 >();     }     //添加一個狀態(tài)，需要傳入狀態(tài)名、讀取函數(shù)和寫入函數(shù)     public static void AddState(string key, Func
getter, Action setter)     {         get_WorldState[key] = getter;         set_WorldState[key] = setter;     }     //根據(jù)狀態(tài)名移除某個世界狀態(tài)     public static void RemoveState(string key)     {         get_WorldState.Remove(key);         set_WorldState.Remove(key);     }     //修改某個狀態(tài)的值     public static void UpdateState(string key, object value)     {         //就是通過寫入字典修改的         set_WorldState[key].Invoke(value);     }     //讀取某個狀態(tài)的值，利用泛型，可以將獲取的object轉(zhuǎn)為指定的類型     public static T GetWorldState

 (string key)     {         return (T)get_WorldState[key].Invoke();     }     //復制一份當前世界狀態(tài)的值（這個主要是用在規(guī)劃中）     public static Dictionary

  CopyWorldState()     {         var copy = new Dictionary

 ();         foreach(var state in get_WorldState)         {             copy.Add(state.Key, state.Value.Invoke());         }         return copy;     } }

2. 任務(wù)類接口

「復合任務(wù)」、「方法」和「原子任務(wù)」它們有共通之處，我們把這些共通之處以接口的形式提煉出來，可以簡化我們在規(guī)劃環(huán)節(jié)的代碼邏輯。

//用于描述運行結(jié)果的枚舉（如果有看上一篇行為樹的話，也可以直接用行為樹的EStatus） public enum EStatus {     Failure, Success, Running,  } public interface IBaseTask {     //判斷是否滿足條件     bool MetCondition(Dictionary

 worldState);     //添加子任務(wù)     void AddNextTask(IBaseTask nextTask); }

3. 原子任務(wù)

原子任務(wù)是一個抽象類，相當于行為樹中的動作節(jié)點，用于開發(fā)者自定義的最小單元任務(wù)。一般就是像「開火」、「奔跑」之類的簡單動作。值得注意的是，這里的條件判斷和執(zhí)行影響都要分兩種情況，一種是規(guī)劃時，一種是實際執(zhí)行時，因為規(guī)劃時我們使用的并不是真正的世界狀態(tài)，而是一份模擬的世界狀態(tài)副本。

public abstractclassPrimitiveTask : IBaseTask {     //原子任務(wù)不可以再分解為子任務(wù)，所以AddNextTask方法不必實現(xiàn)     void IBaseTask.AddNextTask(IBaseTask nextTask)     {         thrownew System.NotImplementedException();     }     ///      /// 執(zhí)行前判斷條件是否滿足，傳入null時直接修改HTNWorld     ///      /// 用于plan的世界狀態(tài)副本     public bool MetCondition(Dictionary

 worldState = null)     {         if(worldState == null)//實際運行時         {             return MetCondition_OnRun();         }         else//模擬規(guī)劃時，若能滿足條件就直接進行Effect         {             if(MetCondition_OnPlan(worldState))             {                 Effect_OnPlan(worldState);                 returntrue;             }             returnfalse;         }     }     protected virtual bool MetCondition_OnPlan(Dictionary

 worldState)     {         returntrue;     }     protected virtual bool MetCondition_OnRun()     {         returntrue;     }     //任務(wù)的具體運行邏輯，交給具體類實現(xiàn)     public abstract EStatus Operator();     ///      /// 執(zhí)行成功后的影響，傳入null時直接修改HTNWorld     ///      /// 用于plan的世界狀態(tài)副本     public void Effect(Dictionary

 worldState = null)     {         Effect_OnRun();     }     protected virtual void Effect_OnPlan(Dictionary

 worldState)     {         ;     }     protected virtual void Effect_OnRun()     {         ;     } }

4. 方法

方法既可以添加「復合任務(wù)」又可以添加「原子任務(wù)」作組成的子任務(wù)，所以我們用IBaseTask列表來存儲；而方法的滿足與否，要看兩個條件，具體看代碼注釋吧：

public classMethod : IBaseTask {     //子任務(wù)列表，可以是復合任務(wù)，也可以是原點任務(wù)     public List SubTask {  get; privateset; }     //方法的前提條件     privatereadonly Func

 condition;     public Method(Func

 condition)     {         SubTask = new List ();         this.condition = condition;     }     //方法條件滿足的判斷=方法本身前提條件滿足+所有子任務(wù)條件滿足     public bool MetCondition(Dictionary

 worldState = null)     {         /*         再復制一遍世界狀態(tài)，用于追蹤每個子任務(wù)的Effect。方法有多個子任務(wù)，         只要其中一個不滿足條件，那整個方法不滿足條件，之前子任務(wù)進行Effect也不算數(shù)         因此用tpWorld記錄，待驗證了方法滿足條件后（所有子任務(wù)均滿足條件），再復制回worldState         */         var tpWorld = new Dictionary

 (worldState);         if (condition())//方法自身的前提條件是否滿足         {             for (int i = 0; i < SubTask.Count; ++i)             {                 //一旦有一個子任務(wù)的條件不滿足，這個方法就不滿足了                 if(!SubTask[i].MetCondition(tpWorld))                 {                     returnfalse;                 }             }             //最終滿足條件后，再將各Effect導致的新世界狀態(tài)（tpWorld）給worldState             worldState = tpWorld;             returntrue;//如果子任務(wù)全都滿足了，那就成了！         }         returnfalse;     }     //添加子任務(wù)     public void AddNextTask(IBaseTask nextTask)     {         SubTask.Add(nextTask);     } }

5. 復合任務(wù)

復合任務(wù)和「方法」類似，只不過只能添加「方法」作為子任務(wù)。

public classCompoundTask : IBaseTask {     //選中的方法     public Method ValidMethod { get; privateset; }     //子任務(wù)（方法）列表     privatereadonly 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];                 returntrue;             }         }         returnfalse;     } }

到這里，基本的組件類就全部完成了，對比行為樹那章，代碼量很少對吧？接下來就是有關(guān)構(gòu)造的類了。

6. 規(guī)劃器

規(guī)劃器的要點在于對「復合任務(wù)」的分解，這里提一下，一個HTN會保證有一個復合任務(wù)作為根任務(wù)，就和行為樹的根節(jié)點一樣。分解也是由此開始：

public classHTNPlanner {     //最終分解完成的所有原子任務(wù)存放的列表     public Stack FinalTasks {  get; privateset; }     //分解過程中，用來緩存被分解出的任務(wù)的棧，因為類型各異，故用IBaseTask類型     privatereadonly Stack taskOfProcess;     privatereadonly CompoundTask rootTask;//根任務(wù)     public HTNPlanner(CompoundTask rootTask)     {         this.rootTask = rootTask;         taskOfProcess = new Stack ();         FinalTasks = new Stack ();     }     //規(guī)劃（核心）     public void Plan()     {         //先復制一份世界狀態(tài)         var worldState = HTNWorld.CopyWorldState();         //將存儲列表清空，避免上次計劃結(jié)果的影響         FinalTasks.Clear();         //將根任務(wù)壓進棧中，準備分解         taskOfProcess.Push(rootTask);         //只要棧還沒空，就繼續(xù)分解         while(taskOfProcess.Count > 0)         {             //拿出棧頂?shù)脑?            var task = taskOfProcess.Pop();             //如果這個元素是復合任務(wù)             if(task is CompoundTask cTask)             {                 //判斷是否可以執(zhí)行                 if(cTask.MetCondition(worldState))                 {                     /*如果可以執(zhí)行，就肯定有可用的方法，                     就將該方法的子任務(wù)都壓入棧中，以便繼續(xù)分解*/                     var subTask = cTask.ValidMethod.SubTask;                     foreach(var t in subTask)                     {                         taskOfProcess.Push(t);                     }                     /*通過上面的步驟我們知道，能被壓進棧中的只有                     復合任務(wù)和原子任務(wù)，方法本身并不會入棧*/                 }             }             else//否則，這個元素就是原子任務(wù)             {                 //將該元素轉(zhuǎn)為原子任務(wù)，因為原本是IBaseTask類型                 var pTask = task as PrimitiveTask;                 //再將該原子任務(wù)加入存放分解完成的任務(wù)列表                 FinalTasks.Push(pTask);             }         }     } }

7. 執(zhí)行器

執(zhí)行器的關(guān)鍵在于如何確認一個原子任務(wù)是否執(zhí)行完成，并且要在執(zhí)行完成后產(chǎn)生影響并切換到下一個原子任務(wù)。

public classHTNPlanRunner {     //當前運行狀態(tài)     private EStatus curState;     //直接將規(guī)劃器包含進來，方便重新規(guī)劃     privatereadonly HTNPlanner planner;     //當前執(zhí)行的原子任務(wù)     private PrimitiveTask curTask;     //標記「原子任務(wù)列表是否還有元素、能夠繼續(xù)」     privatebool canContinue;     public HTNPlanRunner(HTNPlanner planner)     {         this.planner = planner;         curState = EStatus.Failure;     }     public void RunPlan()     {         //如果當前運行狀態(tài)是失?。ㄒ婚_始默認失?。?        if(curState == EStatus.Failure)         {             //就規(guī)劃一次             planner.Plan();         }         //如果當前運行狀態(tài)是成功，就表示當前任務(wù)完成了         if(curState == EStatus.Success)         {             //讓當前原子任務(wù)造成影響             curTask.Effect();         }         /*如果當前狀態(tài)不是「正在執(zhí)行」，就取出新一個原子任務(wù)作為當前任務(wù)         無論失敗還是成功，都要這么做。因為如果是失敗，肯定在代碼運行到這         之前，已經(jīng)進行了一次規(guī)劃，理應(yīng)獲取新規(guī)劃出的任務(wù)來運行；如果是因         為成功，那也要取出新任務(wù)來運行*/         if(curState != EStatus.Running)         {             //用TryPop的返回結(jié)果判斷規(guī)劃器的FinalTasks是否為空             canContinue = planner.FinalTasks.TryPop(out curTask);         }         /*如果canContinue為false，那curTask會為null也視作失敗（其實應(yīng)該是「全部         完成」，但全部完成和失敗是一樣的，都要重新規(guī)劃）。所以只有當canContinue && curTask.MetCondition()都滿足時，才讀取當前原子任務(wù)的運行狀態(tài)，否則就失敗。*/         curState = canContinue && curTask.MetCondition() ? curTask.Operator() : EStatus.Failure;     } }

差不多所有東西都完成了，為了方便使用，我們和上篇寫行為樹時一樣，也做一個構(gòu)造器。

8. 構(gòu)造器

構(gòu)造器會自帶規(guī)劃器和執(zhí)行器，并將任務(wù)的創(chuàng)建打包成函數(shù)。也和上篇行為樹一樣，用棧的方式描述構(gòu)建過程，提供一定可視化。

public partialclassHTNPlanBuilder {     private HTNPlanner planner;      private HTNPlanRunner runner;     privatereadonly Stack taskStack;     public HTNPlanBuilder()     {         taskStack = new Stack ();     }     private void AddTask(IBaseTask task)     {         if (planner != null)//當前計劃器不為空         {             //將新任務(wù)作為構(gòu)造棧頂元素的子任務(wù)             taskStack.Peek().AddNextTask(task);         }         else//如果計劃器為空，意味著新任務(wù)是根任務(wù)，進行初始化         {             planner = new HTNPlanner(task as CompoundTask);             runner = new HTNPlanRunner(planner);         }         //如果新任務(wù)是原子任務(wù)，就不需要進棧了，因為原子任務(wù)不會有子任務(wù)         if (task isnot PrimitiveTask)         {             taskStack.Push(task);         }     }     //剩下的代碼都很簡單，我相信能直接看得懂     public void RunPlan()     {         runner.RunPlan();     }     public HTNPlanBuilder Back()     {         taskStack.Pop();         returnthis;     }     public HTNPlanner End()     {         taskStack.Clear();         return planner;     }     public HTNPlanBuilder CompoundTask()     {         var task = new CompoundTask();         AddTask(task);         returnthis;     }     public HTNPlanBuilder Method(System.Func

 condition)     {         var task = new Method(condition);         AddTask(task);         returnthis;     } }

我還是來簡單畫圖，示意一下構(gòu)建棧的運作過程吧：

• 加入一個復合節(jié)點0后：

• 往這個復0加一個方法作為一個子任務(wù)：

• 如果要向復0再加一個方法，就要調(diào)用Back函數(shù)，再添加：

總之，用Back調(diào)整棧頂?shù)脑兀覀兛梢宰杂傻乜刂菩氯蝿?wù)作為誰的子任務(wù)。而且通過縮進可以較直觀的看到HTN的整個結(jié)構(gòu)，例如下面這樣：

//節(jié)選自我某個小游戲里的一個小怪的行動 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

 ("PlayerHp") > 0)                 .Enemy_Check(this)                 .Enemy_Track(this, PlayerTrans)                 .Enemy_Atk(this)                 .Back()             .Method(() => true)                 .Enemy_Idle(this, 3f)             .End(); }

上述中的Enemy_Check、Enemy_Atk都是實際開發(fā)實現(xiàn)的具體原子行為?，F(xiàn)在再來看，發(fā)現(xiàn)還是有問題的，HTN擅長規(guī)劃，其實并不擅長時時決策，所以在實際開發(fā)時，建議與有限狀態(tài)機結(jié)合。將受傷、死亡這類需要時時反饋的事交給狀態(tài)機，HTN本身也可以放進一個狀態(tài)，來進行復雜行為。而不是像我這樣，將受傷、死亡也當成原子任務(wù)，因為這樣做就要你為各個行為設(shè)計受傷中斷，代碼就會比較繁冗。

“狀態(tài)機+其它”的復合決策模型并不罕見，GOAP也經(jīng)常以這種形式出現(xiàn)。

最后分享一些設(shè)計原子任務(wù)的心得：

1. 如果一個原子任務(wù)有一定的運行過程，可以用一個bool值在Operator函數(shù)內(nèi)部判斷是否完成了動作。

2. 因為我們的世界狀態(tài)是用字符串來讀取的，如果我們想獲取某個士兵的血量該怎么辦？有很多士兵在，該如何區(qū)分？可以用Unity的GetInstanceID()獲取唯一的ID+“血量”，組合成字符串來區(qū)分，其它類似情況同理。例如：

HTNWorld.AddState(GetInstanceID() + "currentHp", () => currentHp, (v) => currentHp = (float)v); HTNWorld.AddState(GetInstanceID() + "IsHurt", () => isHurt, (v) => { isHurt = (bool)v; }); HTNWorld.AddState(GetInstanceID() + "IsDie", () => curHp <= 0, (v) => { });

其實真正要了解HTN還是應(yīng)當自己上手使用，鄙人也只是結(jié)合個人的學習和使用心得寫出了這篇文章。

參考

[1] 項目的代碼：

https://www.alipan.com/s/FbjejATyabd

[2] gitee倉庫：

https://gitee.com/OwlCat/some-projects-in-tutorials/tree/master/HTN_Game

[3] 視頻：

https://www.bilibili.com/video/BV1iG4y1i78Q/?spm_id_from=333.1007.top_right_bar_window_custom_collection.content.click&vd_source=c9a1131d04faacd4a397411965ea21f4

[4] 《Game AI Pro》：

http://www.gameaipro.com/

文末，再次感謝狐王駕虎 的分享， 作者主頁：https://home.cnblogs.com/u/OwlCat， 如果您有任何獨到的見解或者發(fā)現(xiàn)也歡迎聯(lián)系我們，一起探討。（QQ群： 793972859 ）。

近期精彩回顧

【萬象更新】

【萬象更新】

【厚積薄發(fā)】

【學堂上新】