漫談游戲中的人工智能

2019-11-14 14:01:34

字體：大中小

來源：轉載

供稿：網友

寫在前面

　　今天我們來談一下游戲中的人工智能。當然，內容可能不僅僅限于游戲人工智能，還會擴展一些其他的話題。

　　游戲中的人工智能，其實還是算是游戲開發中有點挑戰性的模塊，說簡單點呢，是狀態機，說復雜點呢，是可以幫你打開新世界大門的一把鑰匙。有時候看到知乎上一些可能還是前公司同事的同學的一些話，感覺還是挺哭笑不得的，比如這篇：http://zhi.hu/qu1h，吹捧機器學習這種玄學，對游戲開發嗤之以鼻。我只能說，技術不到家、Vision不夠，這些想通過換工作可培養不來。

　　這篇文章其實我挺早就想寫了，在我剛進工作室不久，看了內部的AI workflow有感而發，evernote里面這篇筆記的創建時間還是今年1月份，現在都8個月過去了，唉。

　　廢話不說了，還是聊聊游戲中的人工智能吧。

從一個簡單的情景開始

　　怪物，是游戲中的一個基本概念。游戲中的單位分類，不外乎玩家、NPC、怪物這幾種。其中，AI一定是與三類實體都會產生交集的游戲模塊之一。

　　以我們熟悉的任意一款游戲中的人形怪物為例，假設有一種怪物的AI需求是這樣的：

大部分情況下，漫無目的巡邏。
玩家進入視野，鎖定玩家為目標開始攻擊。
Hp低到一定程度，怪會想法設法逃跑，并說幾句話。

　　我們以這個為模型，進行這篇文章之后的所有討論。為了簡化問題，以省去一些不必要的討論，將文章的核心定位到人工智能上，這里需要注意幾點的是：

不再考慮entity之間的消息傳遞機制，例如判斷玩家進入視野，不再通過事件機制觸發，而是通過該人形怪的輪詢觸發。
不再考慮entity的行為控制機制，簡化這個entity的控制模型。不論是底層是基于SteeringBehaviour或者是瞬移，不論是異步驅的還是主循環輪詢，都不在本文模型的討論之列。

　　首先可以很容易抽象出來IUnit：

 1     public interface IUnit 2     { 3         void ChangeState(UnitStateEnum state); 4         void Patrol();  5         IUnit GetNearestTarget();  6         void LockTarget(IUnit unit); 7         float GetFleeBloodRate(); 8         bool CanMove(); 9         bool HPRateLessThan(float rate);10         void Flee();11         void Speak();12     }

　　然后，我們可以通過一個簡單的有限狀態機(FSM)來控制這個單位的行為。不同狀態下，單位都具有不同的行為準則，以形成智能體。

　　具體來說，我們可以定義這樣幾種狀態：

巡邏狀態：會執行巡邏，同時檢查是否有敵對單位接近，接近的話進入戰斗狀態。

戰斗狀態：會執行戰斗，同時檢查自己的血量是否達到逃跑線以下，達成檢查了就會逃跑。

逃跑狀態：會逃跑，同時說一次話。

　　最原始的狀態機的代碼：

1     public interface IState<TState, TUnit> where TState : IConvertible2     {3         TState Enum { get; }4         TUnit Self { get; }5         void OnEnter();6         void Drive();7         void OnExit();8     }

　　以逃跑狀態為例：

 1     public class FleeState : UnitStateBase 2     { 3         public FleeState(IUnit self) : base(UnitStateEnum.Flee, self) 4         { 5         } 6         public override void OnEnter() 7         { 8             Self.Flee(); 9         }10         public override void Drive()11         {12             var unit = Self.GetNearestTarget();13             if (unit != null)14             {15                 return;16             }17 18             Self.ChangeState(UnitStateEnum.Patrol);19         }20     }

決策邏輯與上下文分離

　　上述是一個最簡單、最常規的狀態機實現。估計只有學生會這樣寫，業界肯定是沒人這樣寫AI的，不然游戲怎么死的都不知道。

　　首先有一個非常明顯的性能問題：狀態機本質是描述狀態遷移的，并不需要記錄entity的context，如果entity的context記錄在State上，那么狀態機這個遷移邏輯就需要每個entity都來一份instance，這么一個簡單的狀態遷移就需要消耗大約X個字節，那么一個場景1w個怪，這些都屬于白白消耗的內存。就目前的實現來看，具體的一個State實例內部hold住了Unit，所以State實例是沒辦法復用的。
　　針對這一點，我們做一下優化。對這個狀態機，把Context完全剝離出來。

　　修改狀態機接口定義：

1     public interface IState<TState, TUnit> where TState : IConvertible2     {3         TState Enum { get; }4         void OnEnter(TUnit self);5         void Drive(TUnit self);6         void OnExit(TUnit self);7     }

　　還是拿之前實現好的逃跑狀態作為例子：

 1     public class FleeState : UnitStateBase 2     { 3         public FleeState() : base(UnitStateEnum.Flee) 4         { 5         } 6         public override void OnEnter(IUnit self) 7         { 8             base.OnEnter(self); 9             self.Flee();10         }11         public override void Drive(IUnit self)12         {13             base.Drive(self);14 15             var unit = self.GetNearestTarget();16             if (unit != null)17             {18                 return;19             }20 21             self.ChangeState(UnitStateEnum.Patrol);22         }23     }

　　這樣，就區分了動態與靜態。靜態的是狀態之間的遷移邏輯，只要不做熱更新，是不會變的結構。動態的是狀態遷移過程中的上下文，根據不同的上下文來決定。

分層有限狀態機

　　最原始的狀態機方案除了性能存在問題，還有一個比較嚴重的問題。那就是這種狀態機框架無法描述層級結構的狀態。

　　假設需要對一開始的需求進行這樣的擴展：怪在巡邏狀態下有可能進入怠工狀態，同時要求，怠工狀態下也會進行進入戰斗的檢查。

　　這樣的話，雖然在之前的框架下，單獨做一個新的怠工狀態也可以，但是仔細分析一下，我們會發現，其實本質上巡邏狀態只是一個抽象的父狀態，其存在的意義就是進行戰斗檢查；而具體的是在按路線巡邏還是怠工，其實都是巡邏狀態的一個子狀態。

　　狀態之間就有了層級的概念，各自獨立的狀態機系統就無法滿足需求，需要一種分層次的狀態機，原先的狀態機接口設計就需要徹底改掉了。

　　在重構狀態框架之前，需要注意兩點：

　　因為父狀態需要關注子狀態的運行結果，所以狀態的Drive接口需要一個運行結果的返回值。

　　　　子狀態，比如怠工，一定是有跨幀的需求在的，所以這個Result，我們定義為Continue、Sucess、Failure。

　　子狀態一定是由父狀態驅動的。

　　　　考慮這樣一個組合狀態情景：巡邏時，需要依次得先走到一個點，然后怠工一會兒，再走到下一個點，然后再怠工一會兒，循環往復。這樣就需要父狀態（巡邏狀態）注記當前激活的子狀態，并且根據子狀態執行結果的不同來修改激活的子狀態集合。這樣不僅是Unit自身有上下文，連組合狀態也有了自己的上下文。

　　為了簡化討論，我們還是從non-ContextFree層次狀態機系統設計開始。

　　修改后的狀態定義：

1     public interface IState<TState, TCleverUnit, TResult> 2         where TState : IConvertible3     {4         // ...5         TResult Drive();6         // ...7     }

　　組合狀態的定義：

 1     public abstract class UnitCompositeStateBase : UnitStateBase 2     { 3         protected readonly LinkedList<UnitStateBase> subStates = new LinkedList<UnitStateBase>(); 4  5         // ... 6         protected Result ProcessSubStates() 7         { 8             if (subStates.Count == 0) 9             {10                 return Result.Success;11             }12 13             var front = subStates.First;14             var res = front.Value.Drive();15 16             if (res != Result.Continue)17             {18                 subStates.RemoveFirst();19             }20 21             return Result.Continue;22         }23         // ...24     }25

　　巡邏狀態現在是一個組合狀態：

 1     public class PatrolState : UnitCompositeStateBase 2     { 3         // ... 4         public override void OnEnter() 5         { 6             base.OnEnter(); 7             AddSubState(new MoveToState(Self)); 8         } 9 10         public override Result Drive()11         {12             if (subStates.Count == 0)13             {14                 return Result.Success;15             }16 17             var unit = Self.GetNearestTarget();18             if (unit != null)19             {20                 Self.LockTarget(unit);21                 return Result.Success;22             }23 24             var front = subStates.First;25             var ret = front.Value.Drive();26 27             if (ret != Result.Continue)28             {29                 if (front.Value.Enum == CleverUnitStateEnum.MoveTo)30                 {31                     AddSubState(new IdleState(Self));32                 }33                 else34                 {35                     AddSubState(new MoveToState(Self));36                 }37             }38             39             return Result.Continue;40         }41     }

　　看過《游戲人工智能編程精粹》的同學可能看到這里就會發現，這種層次狀態機其實就是這本書里講的目標驅動的狀態機。組合狀態就是組合目標，子狀態就是子目標。父目標/狀態的調度取決于子目標/狀態的完成情況。這種狀態框架與普通的trivial狀態機模型的區別僅僅是增加了對層次狀態的支持，狀態的遷移還是需要靠顯式的ChangeState來做。

　　這本書里面的狀態框架，每個狀態的執行status記錄在了實例內部，不方便后續的優化，我們這里實現的時候首先把這個做成純驅動式的。但是還不夠。現在之前的ContextFree優化成果已經回退掉了，我們還需要補充回來。

分層的上下文

　　我們對之前重構出來的層次狀態機框架再進行一次Context分離優化。

　　要優化的點有這樣幾個：

　　首先是繼續之前的，unit不應該作為一個state自己的內部status。
　　組合狀態的實例內部不應該包括自身執行的status。目前的組合狀態，可以動態增刪子狀態，也就是根據status決定了結構的狀態，理應分離靜態與動態。巡邏狀態組合了兩個子狀態——A和B，邏輯中是一個完成了就添加另一個，這樣一想的話，其實巡邏狀態應該重新描述——先進行A，再進行B，循環往復。
　　由于有了父狀態的概念，其實狀態接口的設計也可以再迭代，理論上只需要一個drive即可。因為狀態內部的上下文要全部分離出來，所以也沒必要對外提供OnEnter、OnExit，提供這兩個接口的意義只是做一層內部信息的隱藏，但是現在內部的status沒了，也就沒必要隱藏了。

　　具體分析一下需要拆出的status：

　　一部分是entity本身的status，這里可以簡單的認為是unit。
　　另一部分是state本身的status。
- 對于組合狀態，這個status描述的是我當前執行到哪個substate。
- 對于原子狀態，這個status描述的種類可能有所區別。
  - 例如MoveTo/Flee，OnEnter的時候，修改了unit的status，然后Drive的時候去check。
  - 例如Idle，OnEnter時改了自己的status，然后Drive的時候去check。

　　經過總結，我們可以發現，每個狀態的status本質上都可以通過一個變量來描述。一個State作為一個最小粒度的單元，具有這樣的Concept：輸入一個Context，輸出一個Result。

　　Context暫時只需要包括這個Unit，和之前所說的status。同時，考慮這樣一個問題：

　　父狀態A，子狀態B。
　　子狀態B向上返回Continue的同時，status記錄下來為b。
　　父狀態ADrive子狀態的結果為Continue，自身也需要向上拋出Continue，同時自己也有status為a。

　　這樣，再還原現場時，就需要即給A一個a，還需要讓A有能力從Context中拿到需要給B的b。因此上下文的結構理應是遞歸定義的，是一個層級結構。

　　Context如下定義：

 1     public class Continuation 2     { 3         public Continuation SubContinuation { get; set; } 4         public int NextStep { get; set; } 5         public object Param { get; set; } 6     } 7  8     public class Context<T> 9     {10         public Continuation Continuation { get; set; }11         public T Self { get; set; }12     }

　　修改State的接口定義為：

1     public interface IState<TCleverUnit, TResult>2     {3         TResult Drive(Context<TCleverUnit> ctx);4     }

　　已經相當簡潔了。

　　這樣，我們對之前的巡邏狀態也做下修改，達到一個ContextFree的效果。利用Context中的Continuation來確定當前結點應該從什么狀態繼續：

 1     public class PatrolState : IState<ICleverUnit, Result> 2     { 3         private readonly List<IState<ICleverUnit, Result>> subStates; 4         public PatrolState() 5         { 6             subStates = new List<IState<ICleverUnit, Result>>() 7             { 8                 new MoveToState(), 9                 new IdleState(),10             };11         }12         public Result Drive(Context<ICleverUnit> ctx)13         {14             var unit = ctx.Self.GetNearestTarget();15             if (unit != null)16             {17                 ctx.Self.LockTarget(unit);18 19                 return Result.Success;20             }21 22             var nextStep = 0;23             if (ctx.Continuation != null)24             {25                 // Continuation26                 var thisContinuation = ctx.Continuation;27 28                 ctx.Continuation = thisContinuation.SubContinuation;29 30                 var ret = subStates[nextStep].Drive(ctx);31 32                 if (ret == Result.Continue)33                 {34                     thisContinuation.SubContinuation = ctx.Continuation;35                     ctx.Continuation = thisContinuation;36 37                     return Result.Continue;38                 }39                 else if (ret == Result.Failure)40                 {41                     ctx.Continuation = null;42 43                     return Result.Failure;44                 }45 46                 ctx.Continuation = null;47                 nextStep = thisContinuation.NextStep + 1;48             }49 50             for (; nextStep < subStates.Count; nextStep++)51             {52                 var ret = subStates[nextStep].Drive(ctx);53                 if (ret == Result.Continue)54                 {55                     ctx.Continuation = new Continuation()56                     {57                         SubContinuation = ctx.Continuation,58                         NextStep = nextStep,59                     };60 61                     return Result.Continue;62                 } 63                 else if (ret == Result.Failure) 64                 {65                     ctx.Continuation = null;66 67                     return Result.Failure;68                 }69             }70 71             ctx.Continuation = null;72 73             return Result.Success;74         }75     }

　　subStates是readonly的，在組合狀態構造的一開始就確定了值。這樣結構本身就是靜態的，而上下文是動態的。不同的entity instance共用同一個樹的instance。

語義結點的抽象

　　優化到這個版本，至少在性能上已經符合要求了，所有實例共享一個靜態的狀態遷移邏輯。面對之前提出的需求，也能夠解決。至少算是一個經過對《游戲人工智能編程精粹》中提出的目標驅動狀態機模型優化后的一個符合工業應用標準的AI框架。拿來做小游戲或者是一些AI很簡單的游戲已經綽綽有余了。

　　不過我們在這篇博客的討論中是不能僅停留在能解決需求的層面上。目前的方案至少還存在一個比較嚴重的問題，那就是邏輯復用性太差。組合狀態需要coding的邏輯太多了，具體的狀態內部邏輯需要人肉維護，更可怕的是需要程序員來人肉維護，再多幾個組合狀態簡直不敢想象。程序員真的沒這么多時間維護這些東西好么。所以我們應該嘗試抽象一下組合狀態是否有一些通用的設計pattern。

　　為了解決這個問題，我們再對這幾個狀態的分析一下，可以對結點類型進行一下歸納。

　　結點基本上是分為兩個類型：組合結點、原子結點。

　　如果把這個狀態遷移邏輯體看做一個樹結構，那其中組合結點就是非葉子結點，原子結點就是葉子結點。

　　對于組合結點來說，其行為是可以歸納的。

　　巡邏結點，不考慮觸發進入戰斗的邏輯，可以歸納為一種具有這樣的行為的組合結點：依次執行每個子結點（移動到某個點、休息一會兒），某個子結點返回Success則執行下一個，返回Failure則直接向上返回，返回Continue就把Continuation拋出去。命名具有這樣語義的結點為Sequence。
設想攻擊狀態下，單位需要同時進行兩種子結點的嘗試，一個是釋放技能，一個是說話。兩個需要同時執行，并且結果獨立。有一個返回Success則向上返回Success，全部Failure則返回Failure，否則返回Continue。命名具有如此語義的結點為Parallel。
　　在Parallel的語義基礎上，如果要體現一個優先級/順序性質，那么就需要一個具有依次執行子結點語義的組合結點，命名為Select。

　　Sequence與Select組合起來，就能完整的描述一”趟“巡邏，Select(ReactAttack, Sequence(MoveTo, Idle))，可以直接干掉之前寫的Patrol組合狀態，組合狀態直接拿現成的實現好的語義結點復用即可。

組合結點的抽象問題解決了，現在我們來看葉子結點。

葉子結點也可以歸納一下pattern，能歸納出三種：

Flee、Idle、MoveTo三個狀態，狀態進入的時候調一下宿主的某個函數，申請開始一個持續性的動作。
四個原子狀態都有的一個pattern，就是在Drive中輪詢，直到某個條件達成了才返回。
Attack狀態內部，每次都輪詢都會向宿主請求一個數據，然后再判斷這個“外部”數據是否滿足一定條件。

　　pattern確實是有這么三種，但是葉子結點自身其實是兩種，一種是控制單位做某種行為，一種是向單位查詢一些信息，其實本質上是沒區別的，只是描述問題的方式不一樣。

　　既然我們的最終目標是消除掉四個具體狀態的定義，轉而通過一些通用的語義結點來描述，那我們就首先需要想辦法提出一種方案來描述上述的三個pattern。

　　前兩個pattern其實是同一個問題，區別就在于那些邏輯應該放在宿主提供的接口里面做實現，哪些邏輯應該在AI模塊里做實現。調用宿主的某個函數，調用是一個瞬間的操作，直接改變了宿主的status，但是截止點的判斷就有不同的實現方式了。

　　一種實現是宿主的API本身就是一個返回Result的函數，第一次調用的時候，宿主會改變自己的狀態，比如設置單位開始移動，之后每幀都會驅動這個單位移動，而AI模塊再去調用MoveTo就會拿到一個Continue，直到宿主這邊內部驅動單位移動到目的地，即向上返回Success；發生無法讓單位移動完成的情況，就返回Failure。
　　另一種實現是宿主提供一些基本的查詢API，比如移動到某一點、是否到達某個點、獲得下一個巡邏點，這樣的話就相當于是把輪詢判斷寫在了AI模塊里。這樣就需要有一個Check結點，來包裹這個查詢到的值，向上返回一個IO類型的值。

　　而針對第三種pattern，可以抽象出這樣一種需求情景，就是：

AI模塊與游戲世界的數據互操作

　　假設宿主提供了接受參數的api，提供了查詢接口，ai模塊需要通過調用宿主的查詢接口拿到數據，再把數據傳給宿主來執行某種行為。

　　我們稱這種語義為With，With用來求出一個結點的值，并合并在當前的env中傳遞給子樹，子樹中可以resolve到這個symbol。

　　有了With語義，我們就可以方便的在AI模塊中對游戲世界的數據進行操作，請求一個數據 => 處理一下 => 返回一個數據，更具擴展性。

　　With語義的具體需求明確一下就是這樣的：由兩個子樹來構造，一個是IOGet，一個是SubTree。With會首先求值IOGet，然后binding到一個symbol上，SubTree 可以直接引用這個symbol，來當做一個普通的值用。

然后考慮下實現方式。

C#中，子樹要想引用這個symbol，有兩個方法：

ioget與subtree共同hold住一個變量，ioget求得的值賦給這個變量，subtree構造的時候直接把值傳進來。
ioget與subtree共同hold住一個env，雙方約定統一的key，ioget求完就把這個key設置一下，subtree構造的時候直接從env里根據key取值。

　　考慮第一種方法，hold住的不應該是值本身，因為樹本身是不同實例共享的，而這個值會直接影響到子樹的結構。所以應該用一個class instance object對值包裹一下。

　　這樣經過改進后的第一種方法理論上速度應該比env的方式快很多，也方便做一些優化，比如說如果子樹沒有continue就不需要把這個值存在env中，比如說由于樹本身的驅動一定是單線程的，不同的實例可以共用一個包裹，執行子樹的時候設置下包裹中的值，執行完子樹再把包裹中的值還原。

　　加入了with語義，就需要重新審視一下IState的定義了。既然一個結點既有可能返回一個Result，又有可能返回一個值，那么就需要這樣一種抽象：

有這樣一種泛化的concept，他只需要提供一個drive接口，接口需要提供一個環境env，drive一下，就可以輸出一個值。這個concept的instance，需要是pure的，也就是結果唯一取決于輸入的環境。不同次輸入，只要環境相同，輸出一定相同。

　　因為描述的是一種與外部世界的通信，所以就命名為IO吧：

1     public interface IO<T>2     {3         T Drive(Context ctx);4     }

　　這樣，我們之前的所有結點都應該有IO的concept。

　　之前提出了Parallel、Sequence、Select、Check這樣幾個語義結點。具體的實現細節就不再細說了，簡單列一下代碼結構：

    public class Sequence : IO<Result>    {        private readonly ICollection<IO<Result>> subTrees;        public Sequence(ICollection<IO<Result>> subTrees)        {            this.subTrees = subTrees;        }        public Result Drive(Context ctx)        {            throw new NotImplementedException();        }    }

　　With結點的實現，采用我們之前說的第一種方案：

 1     public class With<T, TR> : IO<TR> 2     { 3         // ... 4         public TR Drive(Context ctx) 5         { 6             var thisContinuation = ctx.Continuation; 7             var value = default(T); 8             var skipIoGet = false; 9 10             if (thisContinuation != null)11             {12                 // Continuation13                 ctx.Continuation = thisContinuation.SubContinuation;14 15                 // 0表示需要繼續ioGet16                 // 1表示需要繼續subTree17                 if (thisContinuation.NextStep == 1)18                 {19                     skipIoGet = true;20                     value = (T) thisContinuation.Param;21                 }22             }23 24             if (!skipIoGet)25             {26                 value = ioGet.Drive(ctx);27 28                 if (ctx.Continuation != null)29                 {30                     // ioGet拋出了Continue31                     if (thisContinuation == null)32                     {33                         thisContinuation = new Continuation()34                         {35                             SubContinuation = ctx.Continuation,36                             NextStep = 0,37                         };38                     }39                     else40                     {41                         thisContinuation.SubContinuation = ctx.Continuation;42                         thisContinuation.NextStep = 0;43                     }44 45                     ctx.Continuation = thisContinuation;46 47                     return default(TR);48                 }49             }50             51             var oldValue = box.SetVal(value);52             var ret = subTree.Drive(ctx);53 54             box.SetVal(oldValue);55 56             if (ctx.Continuation != null)57             {58                 // subTree拋出了Continue59                 if (thisContinuation == null)60                 {61                     thisContinuation = new Continuation()62                     {63                         SubContinuation = ctx.Continuation,64                     };65                 }66 67                 ctx.Continuation = thisContinuation;68                 thisContinuation.Param = value;69             }70 71             return ret;72         }73     }

　　這樣，我們的層次狀態機就全部組件化了。我們可以用通用的語義結點來組合出任意的子狀態，這些子狀態是不具名的，對構建過程更友好。

　　具體的代碼例子：

Par(     Seq(IsFleeing, ((Box<object> a) => With(a, GetNearestTarget, Check(IsNull(a))))(new Box<object>()), Patrol)    ,Seq(IsAttacking, ((Box<float> a) => With(a, GetFleeBloodRate, Check(HpRateLessThan(a))))(new Box<float>()))    ,Seq(IsNormal, Loop(Par(((Box<object> a) => With(a, GetNearestTarget, Seq(Check(IsNull(a)), LockTarget(a)))(new Box<object>()), Seq(Seq(Check(ReachCurrentPatrolPoint), MoveToNextPatrolPoiont), Idle))))))

　　看起來似乎是變得復雜了，原來可能只需要一句new XXXState()，現在卻需要自己用代碼拼接出來一個行為邏輯。但是仔細想一下，改成這樣的描述其實對整個工作流是有好處的。之前的形式完全是硬編碼，而現在，似乎讓我們看到了轉數據驅動的可能性。

對行為結點做包裝

　　當然這個示例還少解釋了一部分，就是葉子結點，或者說是行為結點的定義。

　　我們之前對行為的定義都是在IUnit中，但是這里顯然不像是之前定義的IUnit。

　　如果把每個行為都看做是樹上的一個與Select、Sequence等結點無異的普通結點的話，就需要實現IO的接口。抽象出一個計算的概念，構造的時候可以構造出這個計算，然后通過Drive，來求得計算中的值。

　　包裝后的一個行為的代碼：

        #region HpRateLessThan        private class MessageHpRateLessThan : IO<bool>        {            public readonly float p0;            public MessageHpRateLessThan(float p0)            {                this.p0 = p0;            }            public bool Drive(Context ctx)            {                return ((T)ctx.Self).HpRateLessThan(p0);            }        }        public static IO<bool> HpRateLessThan(float p0)        {            return new MessageHpRateLessThan(p0);        }        #endregion

　　經過包裝的行為結點的代碼都是有規律可循的，所以我們可以比較容易的通過一些代碼生成的機制來做。比如通過反射拿到IUnit定義的接口信息，然后直接在這基礎之上做一下包裝，做出來個行為結點的定義。

　　現在我們再回憶下討論過的With，構造一個葉子結點的時候，參數不一定是literal value，也有可能是經過Box包裹過的。所以就需要對Boax和literal value抽象出來一個公共的概念，葉子結點/行為結點可以從這個概念中拿到值，而行為結點計算本身的構造也只需要依賴于這個概念。

　　我們把這個概念命名為Thunk。Thunk包裹一個值或者一個box，而就目前來看，這個Thunk，僅需要提供一個我們可以通過其拿到里面的值的接口就夠了。

    public abstract class Thunk<T>    {        public abstract T GetUserValue();    }

　　對于常量，我們可以構造一個包裹了常量的thunk；而對于box，其天然就屬于Thunk的concept。

　　這樣，我們就通過一個Thunk的概念，硬生生把樹中的結點與值分割成了兩個概念。這樣做究竟正確不正確呢？

　　如果一個行為結點的參數可能有的類型本來就是一些primitive type，或者是外部世界（相對于AI世界）的類型，那肯定是沒問題的。但如果需要支持這樣一種特性：外部世界的函數，返回值是AI世界的某個概念，比如一個樹結點；而我的AI世界，希望的是通過這個外部世界的函數，動態的拿到一個結點，再動態的加到我的樹中，或者再動態的傳給不通的外部世界的函數，應該怎么做？

　　對于一顆With子樹（Negate表示對子樹結果取反，Continue仍取Continue）：

((Box<IO<Result>> a) =>      With(a, GetNearestTarget, Negate(a)))(new Box<IO<Result>>())

　　語義需要保證，這顆子樹執行到任意時刻，都需要是ContextFree的。

　　假設IOGet返回的是一個普通的值，確實是沒問題的。

　　但是因為Box包裹的可能是任意值，例如，假設IOGet返回的是一個IO，

instance a，執行完IOGet之后，結構變為Negate(A)。
instance b，再執行IOGet，拿到一個B，設置box里的值為B，并且拿出來A，這時候再run subtree，其實就是按Negate(B)來跑的。

　　我們只有把IO本身，做到其就是Thunk這個Concept。這樣所有的Message對象，都是一個Thunk。不僅如此，所以在這個樹中出現的數據結構，理應都是一個Thunk，比如List。

　　再次改造IO：

    public abstract class IO<T> : Thunk<IO<T>>    {        public abstract T Drive(Context ctx);        public override IO<T> GetUserValue()        {            return this;        }    }

BehaviourTree

　　對AI有了解的同學可能已經清楚了，目前我們實現的就是一個行為樹的引擎，并且已經基本成型。到目前為止，我們接觸過的行為樹語義有：

　　Sequence、Select、Parallel、Check、Negate。

　　其中Sequence與Select是兩個比較基本的語義，一個相當于邏輯And，一個相當于邏輯Or。在組合子設計中這兩類組合子也比較常見。

　　不同的行為樹方案，對語義結點的選擇也不一樣。

　　比如以前在行為樹這塊比較權威的一篇halo2的行為樹方案的paper，里面提到的幾個常用的組合結點有這樣幾種：

prioritized-list ：每次執行優先級最高的結點，高優先級的始終搶占低優先級的。
sequential ：按順序執行每個子結點，執行完最后一個子結點后，父結點就finished。
sequential-looping ：同上，但是會loop。
probabilistic ：從子結點中隨機選擇一個執行。
one-off ：從子結點中隨機選擇或按優先級選擇，選擇一個排除一個，直到執行完為止。

　　而騰訊的behaviac對組合結點的選擇除了傳統的Select和Seqence，halo里面提到的隨機選擇，還自己擴展了SelectorProbability（雖然看起來像是一個select，但其實每次只會根據概率選擇一個，更傾向于halo中的Probabilistic），SequenceStochastic（隨機地決定執行順序，然后表現起來確實像是一個Sequence）。

　　其他還有各種常用的修飾結點，比如前文實現的Check，還有一些比較常用的：

　　Wait ：子樹返回Success的時候向上Success，否則向上Continue?！　?/li>
　　Forever ：永遠返回Continue。
　　If-Else、Switch-Cond ：對于有編程功底的我想就不需要再多做解釋了。
　　forcedXX ：對子樹結果強制取值。

　　還有一類屬于特色結點，雖然通過其他各種方式也都能實現，但是在行為樹這個層面實現的話肯定擴展性更強一些，畢竟可以分離一部分程序的職責。一個比較典型的應用情景是事件驅動，halo的paper中提到了Behaviour Impulse，但是我在在behaviac中并沒有找到類似的概念。

　　halo的paper里面還提到了一些比較細節的hack技巧，比如同一顆行為樹可以應用不同的Style，Parameter Creep等等，有興趣的同學也可以自行研究。

　　至此，行為樹的runtime話題需要告一段落了，畢竟是一項成熟了十幾年的技術。雖然這是目前游戲AI的標配，但是，只有行為樹的話，離一個完整的AI工作流還很遠。到目前為止，行為樹還都是程序寫出來的，但是正確來說AI應該是由策劃或者AI腳本配出來的。因此，這篇文章的話題還需要繼續，我們接下來就討論一下這個程序與策劃之間的中間層。

　　之前的優化思路也好，從其他語言借鑒的設計pattern也好，行為樹這種理念本身也好，本質上都是術。術很重要，但是無助于優化工作流。這時候，我們更需要一種略。那么，

略是什么

這里我們先擴展下游戲AI開發中的一種比較經典的工作流。策劃輸出AI配置，直接在游戲內調試效果。如果現有接口不滿足需求，就向程序提開發需求，程序加上新接口之后，策劃可以在AI配置里面應用新的接口。這個AI配置是個比較廣義的概念，既可以像很多從立項之初并沒有規劃AI模塊的游戲那樣，逐漸地、自發地形成了一套基于配表做的決策樹；也可以是像騰訊的behaviac那樣的，用xml文件來描述。XML天生就是描述數據的，騰訊系的組件普遍特別鐘愛，tdr這種配表轉數據的工具是xml，tapp tcplus什么的配置文件全是XML，倒不是說XML，而是很多問題解決起來并不直觀。

配表也好，XML也好，json也好，這種描述數據的形式本身并沒有錯。配表幫很多團隊跨過了從硬編碼到數據驅動的開發模式的轉變，現在國內小到創業手游團隊，大到天諭這種幾百人的MMO，策劃的工作量除了配關卡就是配表。

但是，配表無法自我進化 http://blog.csdn.net/noslopforever/article/details/20833931 ，配表無法自己描述流程是什么樣，而是流程在描述配表是什么樣。

針對策劃配置AI這個需求，我們希望抽象出來一個中間層，這樣，基于這個中間層，開發相應的編輯器也好，直接利用這個中間層來配AI也好，都能夠靈活地做到調試AI這個最終需求。如何解決？我們不妨設計一種DSL。

DSL

　　Domain-specific Language，領域特定語言，顧名思義，專門為特定領域設計的語言。設計一門DSL遠容易于設計一門通用計算語言，我們不用考慮一些特別復雜的特性，不用加一些增加復雜度的模塊，不需要care跟領域無關的一些流程。Less is more。

游戲AI需要怎樣一種DSL

痛點：

　　對于游戲AI來說，需要一種語言可以描述特定類型entity的行為邏輯。
　　而對于程序員來說，只需要提供runtime即可。比如組合結點的類型、表現等等。而具體的行為決策邏輯，由其他層次的協作者來定義。
　　核心需求是做另一種/幾種高級語言的目標代碼生成，對于當前以及未來幾年來說，對C#的支持一定是不能少的，對python/lua等服務端腳本的支持也可以考慮。
　　對語言本身的要求是足夠簡單易懂，declarative，這樣既可以方便上層編輯器的開發，也可以在沒編輯器的時候快速上手。

分析需求：

　　因為需要做目標代碼生成，而且最主要的目標代碼應該是C#這種強類型的，所以需要有簡單的類型系統，以及編譯期簡單的類型檢查。可以確保語言的源文件可以最終codegen成不會導致編譯出錯的C#代碼。
　　決定行為樹框架好壞的一個比較致命的因素就是對With語義的實現。根據我們之前對With語義的討論，可以看到，這個With語義的描述其實是天然的可以轉化為一個lambda的，所以這門DSL同樣需要對lambda進行支持。
　　關于類型系統，需要支持一些內建的復雜類型，目前來看僅需要List，只有在seq、select等結點的構造時會用到。還是由于需要支持lambda的原因，我們需要支持Applicative Type，也就是形如A -> B應該是first class type，而一個lambda也應該是first class function。根據之前對runtime的實現討論，我們的DSL還需要支持Generic Type，來支持IO<Result>這樣的類型，以及List<IO<Result>>這樣的類型。對內建primitive類型的支持只要有String、Bool、Int、Float即可。需要支持簡單的類型推導，實現hindley-milner的真子集即可，這樣至少我們就不需要在聲明lambda的時候寫的太復雜。
　　需要支持模塊化定義，也就是最基本的import語義。這樣的話可以方便地模塊化構建AI接口，也可以比較方便地定義一些預制件。
- 　模塊分為兩類：
- 　一類是抽象的聲明，只有declare。比如Prelude，seq、select等一些結點的具體實現邏輯一定是在runtime中做的，所以沒必要在DSL這個層面填充這類邏輯。具體的代碼轉換則由一些特設的模塊來做。只需要類型檢查通過，目標語言的CodeGenerator生成了對應的目標代碼，具體的邏輯就在runtime中直接實現了。
- 　一類是具體的定義，只有define。比如定義某個具體的AIXXX中的root結點，或者定義某個通用行為結點。具體的定義就需要對外部模塊的define以及declare進行組合。import語義就需要支持從外部模塊導入符號。

一種non-trivial的DSL實現方案

　　由于原則是簡單為主，所以我在語言的設計上主要借鑒的是Scheme。S表達式的好處就是代碼本身即數據，也可以是我們需要的AST。同時，由于需要引入簡單類型系統，需要混入一些其他語言的描述風格。我在declare類型時的語言風格借鑒了haskell，import語句也借鑒了haskell。

　　具體來說，declare語句可能類似于這樣：

(declare     (HpRateLessThan :: (Float -> IO Result))    (GetFleeBloodRate :: Float)    (IsNull :: (Object -> Bool))    (Idle :: IO Result))(declare     (check :: (Bool -> IO Result))    (loop :: (IO Result -> IO Result))    (par :: (List IO Result -> IO Result)))

　　因為是以Scheme為主要借鑒對象，所以內建的復雜類型實現上本質是一個ADT，當然，有針對list構造專用的語法糖，但是其parse出來拿到的AST中一個list終究還是一個ADT。

　　直接拿例子來說比較直觀：

(import Prelude)(import BaseAI)(define Root    (par [(seq [(check IsFleeing)               ((/a (check (IsNull a))) GetNearestTarget)])          (seq [(check IsAttacking)               ((/b (HpRateLessThan b)) GetFleeBloodRate)])          (seq [(check IsNormal)               (loop                     (par [((/c (seq [(check (IsNull c))                                     (LockTarget c)])) GetNearestTarget)                          (seq [(seq [(check ReachCurrentPatrolPoint)                                     MoveToNextPatrolPoiont])                               Idle])]))])]))

　　可以看到，跟S-Expression沒什么太大的區別，可能lambda的聲明方式變了下。

　　然后是詞法分析和語法分析，這里我選擇的是Haskell的ParseC。一些更傳統的選擇可能是lex+yacc/flex+bison。但是這種兩個工具一起混用學習成本就不用說了，也違背了simple is better的初衷。ParseC使用起來就跟PEG是一樣的，PEG這種形式，是天然的結合了正則與top-down parser。haskell支持的algebraic data types，天然就是用來定義AST結構的，簡單直觀。haskell實現的hindly-miner類型系統，又是讓你寫代碼基本編譯通過就能直接run出正確結果，從一定程度上彌補了PEG天生不適合調試的缺陷。一個haskell的庫就能解決lexical&grammar，實在方便。

　　先是一些AST結構的預定義：

module Common whereimport qualified Data.Map as Maptype Identifier = Stringtype ValEnv = Map.Map Identifier Valtype TypeEnv = Map.Map Identifier Typetype DecEnv = Map.Map Identifier (String,Dec)data Type =     NormalType String    | GenericType String Type    | APPType [Type]data Dec =    DefineDec Pat Exp    | ImportDec String    | DeclareDec Pat Type    | DeclaresDec [Dec]        data Exp =     ConstExp Val    | VarExp Identifier    | LambdaExp Pat Exp    | AppExp Exp Exp    | ADTExp String [Exp]        data Val =    NilVal    | BoolVal Bool    | IntVal Integer    | FloatVal Float    | StringVal String    data Pat =    VarPat Identifier

　　我在這里省去了一些跟這篇文章討論的DSL無關的語言特性，比如Pattern的定義我只保留了VarPat；Value的定義我去掉了ClosureVal，雖然語言本身仍然是支持first class function的。

　　algebraic data type的一個好處就是清晰易懂，定義起來不過區區二十行，但是我們一看就知道之后輸出的AST會是什么樣。

haskell的ParseC用起來其實跟PEG是沒有本質區別的，組合子本身是自底向上描述的，而parser也是通過parse小元素的parser來構建parse大元素的parser。

例如，haskell的ParseC庫就有這樣幾個強大的特性：

提供了char、string，基元的parse單個字符或字符串的parser。
提供了sat，傳一個predicate，就可以parse到符合predicate的結果的parser。
提供了try，支持parse過程中的lookahead語義。
提供了chainl、chainr，這樣就省的我們在構造parser的時候就無需考慮左遞歸了。不過這個我也是寫完了parser才了解到的，所以基本沒用上，更何況對于S-expression來說，需要我來處理左遞歸的情況還是比較少的。

　　我們可以先根據這些基本的，封裝出來一些通用combinator。

　　比如正則規則中的star：

star   :: Parser a -> Parser [a]star p = star_p    where         star_p = try plus_p <|> (return [])         plus_p = (:) <$> p <*> star_p

　　比如plus：

plus   :: Parser a -> Parser [a]plus p = plus_p    where        star_p = try plus_p <|> (return []) <?> "plus_star_p"        plus_p = (:) <$> p <*> star_p  <?> "plus_plus_p"

　　基于這些，我們可以做組裝出來一個parse lambda-exp的parser（p_seperate是對char、plus這些的組裝，表示形如a,b,c這樣的由特定字符分隔的序列）：

p_lambda_exp :: Parser Expp_lambda_exp =  p_between '(' ')' inner              <?> "p_lambda_exp"    where        inner = make_lambda_exp                <$  char '//'                <*> p_seperate (p_parse p_pat) ","                <*> p_parse p_exp        make_lambda_exp []     e = (LambdaExp NilPat e)        make_lambda_exp (p:[]) e = (LambdaExp p e)        make_lambda_exp (p:ps) e = (LambdaExp p (make_lambda_exp ps e))

　　有了所有exp的parser，我們就可以組裝出來一個通用的exp parser：

p_exp :: Parser Exp    p_exp =  listplus [p_var_exp, p_const_exp, p_lambda_exp, p_app_exp, p_adt_exp, p_list_exp]         <?> "p_exp"

　　其中，listplus是一種具有優先級的lookahead：

listplus :: [Parser a] -> Parser alistplus lst = foldr (<|>) mzero (map try lst)

　　對于parser來說，其輸入是源文件其輸出是AST。具體來說，其實就是parse出一個Dec數組，拿到AST，供后續的pipeline消費。

我們之前舉的AI的例子，parse出來的AST大概是這副模樣：

-- Prelude.bh
Right [DeclaresDec [ DeclareDec (VarPat "seq") (AppType [GenericType "List" (GenericType "IO" (NormalType "Result")),GenericType "IO" (NormalType "Result")]),DeclareDec (VarPat "check") (AppType [NormalType "Bool",GenericType "IO" (NormalType "Result")])]]
-- BaseAI.bhRight [DeclaresDec [ DeclareDec (VarPat "HpRateLessThan") (AppType [NormalType "Float",GenericType "IO" (NormalType "Result")]),DeclareDec (VarPat "Idle") (GenericType "IO" (NormalType "Result"))]]
-- AI00001.bhRight [ ImportDec "Prelude",ImportDec "BaseAI",DefineDec (VarPat "Root") (AppExp (VarExp "par") (ADTExp "Cons" [     AppExp (VarExp "seq") (ADTExp "Cons" [         AppExp (VarExp "check") (VarExp "IsFleeing")        ,ADTExp "Cons" [             AppExp (LambdaExp (VarPat "a")(AppExp (VarExp "check") (AppExp (VarExp "IsNull") (VarExp "a")))) (VarExp "GetNearestTarget")            ,ConstExp NilVal]])    ,ADTExp "Cons" [         AppExp (VarExp "seq") (ADTExp "Cons" [             AppExp (VarExp "check") (VarExp "IsAttacking")            ,ADTExp "Cons" [                 AppExp (LambdaExp (VarPat "b") (AppExp (VarExp "HpRateLessThan") (VarExp "b"))) (VarExp "GetFleeBloodRate")                ,ConstExp NilVal]])        ,ADTExp "Cons" [             AppExp (VarExp "seq") (ADTExp "Cons" [                 AppExp (VarExp "check") (VarExp "IsNormal")                ,ADTExp "Cons" [                     AppExp (VarExp "loop") (AppExp (VarExp "par") (ADTExp "Cons" [                         AppExp (LambdaExp (VarPat "c") (AppExp (VarExp "seq") (ADTExp "Cons" [                             AppExp (VarExp "check") (AppExp (VarExp"IsNull") (VarExp "c"))                            ,ADTExp "Cons" [                                 AppExp (VarExp "LockTarget") (VarExp "c")                                ,ConstExp NilVal]]))) (VarExp "GetNearestTarget")                        ,ADTExp "Cons" [                             AppExp (VarExp"seq") (ADTExp "Cons" [                                 AppExp (VarExp "seq") (ADTExp "Cons" [                                     AppExp (VarExp "check") (VarExp "ReachCurrentPatrolPoint")                                    ,ADTExp "Cons" [                                         VarExp "MoveToNextPatrolPoiont"                                        ,ConstExp NilVal]])                                ,ADTExp "Cons" [                                     VarExp "Idle"                                    ,ConstExp NilVal]])                            ,ConstExp NilVal]]))                    ,ConstExp NilVal]])            ,ConstExp NilVal]]]))]

　　前面兩部分是我把在其他模塊定義的declares，選擇性地拿過來兩條。第三部分是這個人形怪AI的整個的AST。其中嵌套的Cons展開之后就是語言內置的List。

　　正如我們之前所說，做代碼生成之前需要進行一步類型檢查的工作。類型檢查工具其輸入是AST其輸出是一個檢查結果，同時還可以提供AST中的一些輔助信息，包括各標識符的類型信息等等。

　　類型檢查其實主要的邏輯在于處理Appliacative Type，這中間還有個類型推導的邏輯。形如(/a (Func a)) 10，AST中并不記錄a的type，我們的DSL也不需要支持concept、typeclass等有關type、subtype的復雜機制，推導的時候只需要著重處理AppExp，把右邊表達式的類型求出，合并一下env傳給左邊表達式遞歸檢查即可。

　　這部分的代碼：

exp_type :: Exp -> TypeEnv -> Maybe Typeexp_type (AppExp lexp aexp) env =     (exp_type aexp env) >>= (/at ->         case lexp of             LambdaExp (VarPat var) exp -> (merge_type_env (Just env) (make_type_env var (Just at))) >>= (/env1 -> exp_type lexp env1)              _ -> (exp_type lexp env) >>= (/ltype -> check_type ltype at))    where        check_type (AppType (t1:(t2:[]))) at =             if t1 == at then (Just t2) else Nothing        check_type (AppType (t:ts)) at =             if t == at then (Just (AppType ts)) else Nothing

　　此外，還需要有一個通用的CodeGenerator模塊，其輸入也是AST，其輸出是另一些AST中的輔助信息，主要是注記下各標識符的import源以及具體的define內容，用來方便各目標語言CodeGenerator直接復用邏輯。

　　目標語言的CodeGenerator目前只做了C#的。

　　目標代碼生成的邏輯就比較簡單了，畢竟該有的信息前面的各模塊都提供了，這里根據之前一個版本的runtime，代碼生成的大致樣子：

public static IO<Result> Root =     Prelude.par(Help.MakeList(         Prelude.seq(Help.MakeList(             Prelude.check(BaseAI.IsFleeing)            ,(((Box<Object> a) => Help.With(a, BaseAI.GetNearestTarget, Prelude.check(BaseAI.IsNull())))(new Box<Object>()))))        ,Prelude.seq(Help.MakeList(             Prelude.check(BaseAI.IsAttacking)            ,(((Box<Float> b) => Help.With(b, BaseAI.GetFleeBloodRate, BaseAI.HpRateLessThan()))(new Box<Float>()))))        ,Prelude.seq(Help.MakeList(             Prelude.check(BaseAI.IsNormal)            ,Prelude.loop(Prelude.par(Help.MakeList(                 (((Box<Object> c) => Help.With(c, BaseAI.GetNearestTarget, Prelude.seq(Help.MakeList(                     Prelude.check(BaseAI.IsNull())                    ,BaseAI.LockTarget()))))(new Box<Object>()))                ,Prelude.seq(Help.MakeList(                     Prelude.seq(Help.MakeList(                         Prelude.check(BaseAI.ReachCurrentPatrolPoint)                        ,BaseAI.MoveToNextPatrolPoiont))                    ,BaseAI.Idle)))))))))

　　總的來說，大致分為這幾個模塊：Parser、TypeChecker、CodeGenerator、目標語言的CodeGenerator。再加上目標語言的runtime，基本上就可以組成這個DSL的全部了。

　　上面列出來的代碼風格比較混搭，畢竟是前后差的時間比較久了。。parser部分大概是7月左右完成的，那時候喜歡applicative的風格，大量用了<$> <*>；后面的TypeChecker和CodeGenerator都是最近寫的，寫monad expression的時候，Maybe Monad我比較傾向于寫原生的>>=調用，IO Monad如果這樣寫就煩了，所以比較多的用了do-notaion。優化什么的由于時間原因還沒看RWH的后面幾章，而且DSL的compiler對性能需求的優先級其實很低了，所以暫時沒有考慮過，各位看官將就一下。

再擴展runtime

　　對比DSL，我們可以發現，DSL支持的特性要比之前實現的runtime版本多。比如：

runtime中壓根就沒有Closure的概念，但是DSL中我們是完全可以把一個lambda作為一個ClosureVal傳給某個函數的。
缺少對標準庫的支持。比如常用的math函數。
基于上面這點，還會引入一個With結點的性能問題，在只有runtime的時候我們也許不會With a <- 1+1。但是DSL中是有可能這樣的，而且生成出來的代碼會每次run這棵樹的時候都會重新計算一次1+1。

　　針對第一個問題，我們要做的工作就多了。首先我們要記錄下這個閉包hold住的自由變量，要傳給runtime，runtime也要記錄，也要做各種各種，想想都麻煩，而且完全偏離了游戲AI的話題，不再討論。

　　針對第二個問題，我們可以通過解決第三個問題來順便解決這個問題。

　　針對第三個問題，我們重新審視一下With語義。

　　With語義所要表達的其實是這樣一個概念：

　　　　把一個可能會Continue/Lazy Evaluation的計算結果，綁定到一個variable上，對于With下面的子表達式來說，這個variable的值具有lexical scope。

　　但是在runtime中，我們按照之前的寫法，subtree中直接就進行了函數調用，很顯然是存在問題的。

　　With結點本身的返回值不一定只是一個IO<Result>，有可能是一個IO<float>。

　　舉例：

((Box<float> a) => (Help.With(a, UnitAI.GetFleeBloodRate, Math.Plus(a, 0.1)))(new Box<float>())

　　這里Math.Plus屬于這門DSL標準庫的一部分，實現上我們就對底層數學函數做一層簡單的wrapper。但是這樣由于C#語言是pass-by-value，我們在構造這顆With的時候，Math.Plus(a, 0.1)已經求值。但是這個時候Box的值還沒有被填充，求出來肯定是有問題的。

　　所以我們需要對這樣一種計算再進行一次抽象。希望可以得到的效果是，對于Math.Plus(0.1, 0.2)，可以在構造樹的時候直接求值；對于Math.Plus(0.1, a)，可以得到某種計算，在我們需要的時候再求值。

　　先明確下函數調用有哪幾種情況：

對UnitAI，也就是外部世界的定義的接口的調用。這種調用，對于AI模塊來說，本質上是pure的，所以不需要考慮這個延遲計算的問題
對標準庫的調用

　　按我們之前的runtime設計思路，Math.Plus這個標準庫API也許會被設計成這樣：

        public static Thunk<float> Plus(Thunk<float> a, Thunk<float> b)        {            return Help.MakePureThunk(a.GetUserValue() + b.GetUserValue());        }

　　如果a和b都是literal value，那就沒問題，但是如果有一個是被box包裹的，那就很顯然是有問題的。

　　所以需要對Thunk這個概念做一下擴展，使之能區別出動態的值與靜態的值。一般情況下的值，都是pure的；box包裹的值，是impure的。同時，這個pure的性質具有值傳遞性，如果這個值屬于另一個值的一部分，那么這個整體的pure性質與值的局部的pure性質是一致的。這里特指的值，包括List與IO。

　　整體的概念我們應該拿haskell中的impure monad做類比，比如haskell中的IO。haskell中的IO依賴于OS的輸入，所以任何返回IO monad的函數都具有傳染性，引用到的函數一定還會被包裹在IO monad之中。

　　所以，對于With這種情況的傳遞，應該具有這樣的特征：

With內部引用到了With外部的symbol，那么這個With本身應該是impure的。
With內部只引用了自己的IOGet，那么這個With本身是pure的，但是其SubTree是impure的。

　　所以With結點構造的時候，計算pure應該特殊處理一下。但是這個特殊處理的代碼污染性比較大，我在本文就不列出了，只是這樣提一下。

　　有了pure與impure的標記，我們在對函數調用的時候，就需要額外走一層。

　　本來一個普通的函數調用，比如UnitAI.Func(p0, p1, p2)與Math.Plus(p0, p1)。前者返回一種computing是毫無疑問的，后者就需要根據參數的類型來決定是返回一種計算還是直接的值。

　　為了避免在這個Plus里面改來改去，我們把Closure這個概念給抽象出來。同時，為了簡化討論，我們只列舉T0 -> TR這一種情況，對應的標準庫函數取Abs。

    public class Closure<T0, TR> : Thunk<Closure<T0, TR>>    {        class UserFuncApply : Thunk<TR>        {            private Closure<T0, TR> func;            private Thunk<T0> p0;            public UserFuncApply(Closure<T0, TR> func, Thunk<T0> p0)            {                this.func = func;                this.p0 = p0;                this.pure = false;            }            public override TR GetUserValue()            {                return func.funcThunk(p0).GetUserValue();            }        }        private bool isUserFunc = false;        private FuncThunk<T0, TR> funcThunk;        private Func<T0, TR> userFunc;         public Closure(FuncThunk<T0, TR> funcThunk)        {            this.funcThunk = funcThunk;        }        public Closure(Func<T0, TR> func)        {            this.userFunc = func;            this.funcThunk = p0 => Help.MakePureThunk(userFunc(p0.GetUserValue()));            this.isUserFunc = true;        }        public override Closure<T0, TR> GetUserValue()        {            return this;        }        public Thunk<TR> Apply(Thunk<T0> p0)        {            if (!isUserFunc || Help.AllPure(p0))            {                return funcThunk(p0);            }            return new UserFuncApply(this, p0);        }    }

　　其中，UserFuncApply就是之前所說的一層計算的概念。UserFunc表示的是等效于可以編譯期計算的一種標準庫函數。

　　這樣定義：

    public static class Math    {        public static readonly Thunk<Closure<float, float>> Abs = Help.MakeUserFuncThunk<float,float>(System.Math.Abs);    }

　　Message類型的Closure構造，都走FuncThunk構造函數；普通函數類型的構造，走Func構造函數，并且包裝一層。

　　Help.Apply是為了方便做代碼生成，描述一種declarative的application。其實就是直接調用Closure的Apply。

　　考慮以下幾種case：

        public void Test()        {            var box1 = new Box<float>();            // Math.Abs(box1) -> UserFuncApply            // 在GetUserValue的時候才會求值            var ret1 = Help.Apply(Math.Abs, box1);            // Math.Abs(0.2f) -> Thunk<float>            // 直接構造出來了一個Thunk<float>(0.2f)            var ret2 = Help.Apply(Math.Abs, Help.MakePureThunk(0.2f));            // UnitAISets<IUnit>.HpRateLessThan(box1) -> Message            var ret3 = Help.Apply(UnitAISets<IUnit>.HpRateLessThan, box1);            // UnitAISets<IUnit>.HpRateLessThan(0.2f) -> Message            var ret4 = Help.Apply(UnitAISets<IUnit>.HpRateLessThan, Help.MakePureThunk(0.2f));        }