lua行為樹設計與實現
- 2019 年 10 月 22 日
- 筆記
項目需要，之前行為樹用的是behaviorDesigner，要改成純lua的
我先做了一版用遞歸實現，程式碼可讀性高但是中斷機制實現起來比較複雜，而且創建自定義action重寫方法時需要調用父類的方法， 如果忘了調用就會出現問題， 所以改成了用棧模擬遞歸。
用棧模擬遞歸好處在於效率高，並且容易控制，用非遞歸實現後自定義一個行為樹節點，那麼該節點不用知道父親的方法，只要做好自己的事情就OK了
完整測試工程已上傳到了github：https://github.com/MCxYY/LuaBT
行為樹整體結構
（和BehaviorDesigner很像，因為就是參考BehaviorDesigner設計的，要做的是c#移植成lua，移植成本儘可能低）
如上，base文件夾中是行為樹核心邏輯，最好不要修改，其他幾個文件夾是自定義節點，如果是Action節點那麼繼承Base中的Action.lua；如果是Composite節點則繼承Composite.lua等
行為樹類結構大致如下：（出於篇幅限制，有些方法沒寫出來）
其中BTManager存儲著所有行為樹BTree，unity每幀調用BTManager的Update，而BTManager調用所有運行中的BTree的Update，BTree管理著自身的節點Task，根據邏輯執行調用Task的OnAwake（）、OnStart等
Shared是節點共享數據，在後文中講述
Task的OnAwake是整顆行為樹激活時運行一次
OnStart是進入該Task時運行一次
OnUpdate是該Task執行中時每幀運行一次
OnPause（bPause）是整棵行為樹暫停或者從暫停中蘇醒時運行，bPause為true則暫停
OnEnd（）是該Task退出時運行一次
運行邏輯
行為樹（BTree）啟動的時候調用BTree.Init()方法先序遍歷該樹，獲得一系列節點數據，比如賦值兒子index，每個節點的兒子index是什麼，每個節點的父親index等，程式碼如下：
1 --先序遍歷，root的index為1、父親index為0 2 function BT.BTree:Init(task, parentIndex, compositeIndex) 3 task:Init(self) 4 task:OnAwake() 5 local curIndex = #self.tTaskList + 1 6 table.insert(self.tTaskList,task) --賦值task的index 7 table.insert(self.tParentIndex,parentIndex) --可以找到其父親的index 8 table.insert(self.tParentCompositeIndex,compositeIndex) --可以找到是Composite類型且離自己最近的祖先的index，用於中斷評估 9 10 if task:CheckType(BT.ParentTask) then 11 if task:CheckChildCount() == false then 12 LogMgr.Error(BT.ErrorRet.ChildCountMin.." index = "..curIndex.." count = "..#task.tChildTaskList) 13 return 14 end 15 self.tChildrenIndex[curIndex] = {} 16 self.tChildConditionalIndex[curIndex] = {} 17 for i = 1, #task.tChildTaskList do 18 table.insert(self.tRelativeChildIndex,i) --該task在其父親中處於第幾個 19 table.insert(self.tChildrenIndex[curIndex],#self.tTaskList + 1) --可以找到其所有兒子的index 20 if task:CheckType(BT.Composite) then 21 self:Init(task.tChildTaskList[i], curIndex, curIndex) 22 else 23 self:Init(task.tChildTaskList[i], curIndex, compositeIndex) 24 end 25 end 26 else 27 if task:CheckType(BT.Conditional) then 28 --可以找到是Conditional類型且離自己最近的子孫的index，用於中斷評估 29 table.insert(self.tChildConditionalIndex[self.tParentCompositeIndex[curIndex]],curIndex) 30 end 31 end 32 end
View Code
行為樹（BTree）中存儲著一個list<stack<taskindex>>，這個是運行棧，行為樹啟動時創建一個運行棧，塞進去樹根；每當有並行分支，則創建一個運行棧，塞進去分支第一個運行的節點。
節點（Task）的狀態有四種：
1、ETaskStatus.Inactive //未激活
2、ETaskStatus.Failure //失敗
3、ETaskStatus.Success //成功
4、ETaskStatus.Running //運行中
運行棧中放的節點都是處於Running狀態，update時遍歷運行棧，取出棧頂節點執行，如果節點執行完畢後狀態不等於running，說明該節點不需要再次運行，那麼就出棧，程式碼如下：
1 function BT.BTree:Update() 2 --進入評估階段，中斷修改運行棧 3 self:ConditionalReevaluate() 4 local status 5 if #self.tRunStack == 0 then 6 return BT.ETaskStatus.Inactive 7 end 8 --遍歷執行所有棧 9 for i = #self.tRunStack,1,-1 do 10 repeat 11 if self.tRunStack[i] == Const.Empty then 12 table.remove(self.tRunStack,i) 13 break 14 end 15 status = BT.ETaskStatus.Inactive 16 while status ~= BT.ETaskStatus.Running do 17 if self.tRunStack[i] ~= Const.Empty then 18 status = self:RunTask(self.tRunStack[i]:Peek(),i) 19 else 20 break 21 end 22 end 23 until(true) 24 end 25 return BT.ETaskStatus.Running 26 end
View Code
節點運行的時候
如果該節點是ParentTask類型則需要運行兒子，其狀態由兒子執行完畢後的狀態來決定
如果該節點是Task類型沒有兒子，那麼其狀態就是其Update的狀態
遞歸實現那麼程式碼大致如下：
status task.runParent(){
for task.childList {
if typeOf(task.childItem) == ParentTask {
status = task.childItem.runParent()
}
else{
status = task.childItem.OnUpdate()
}
if task.CanExcute(status) == false{
return task.status
}
}
return task.status
}
棧實現雖然麻煩點，但思路還是一樣的，多了出棧入棧和其他一些操作
RunTask()
1 function BT.BTree:RunTask(taskIndex, stackIndex) 2 local task = self.tTaskList[taskIndex] 3 self:PushTask(taskIndex,stackIndex) 4 5 local status = BT.ETaskStatus.Inactive 6 7 if task:CheckType(BT.ParentTask) then 8 status = self:RunParentTask(taskIndex,stackIndex) 9 else 10 status = task:OnUpdate() 11 end 12 13 if status ~= BT.ETaskStatus.Running then 14 self:PopTask(stackIndex, status) 15 end 16 return status 17 end
View Code
RunParent()
1 function BT.BTree:RunParentTask(taskIndex, stackIndex) 2 local task = self.tTaskList[taskIndex] 3 local curRelChildIndex = -1 4 local preRelChildIndex = -1 5 while task:CanExcute() do 6 curRelChildIndex = task:GetCurChildIndex() 7 if curRelChildIndex == preRelChildIndex then 8 return BT.ETaskStatus.Running 9 end 10 local childIndex = self.tChildrenIndex[taskIndex][curRelChildIndex] 11 if childIndex == nil then 12 break 13 end 14 --這個主要是為並行節點服務的 15 --其他類型的節點都是兒子執行完畢主動通知父親然後curChildIndex指向下個兒子 16 --但是並行節點是所有兒子一開始都同時執行 17 task:OnChildStart(curRelChildIndex) 18 if task:CanExcuteParallel() then 19 --並行節點創建新的分支 20 local newStack = Stack:New() 21 table.insert(self.tRunStack, newStack) 22 newStack:Push(childIndex) 23 self:RunTask(childIndex, #self.tRunStack) 24 else 25 self:RunTask(childIndex, stackIndex) 26 end 27 preRelChildIndex = curRelChildIndex 28 end 29 return task:GetStatus() 30 end
View Code
節點共享數據
節點共享數據分為三種：一，樹之間任意節點全局共享的數據 二，樹內任意節點共享的數據 三，節點內不共享數據
節點內數據那就不用說了，在節點內聲明的數據都是節點內數據
BehaviorDesigner的共享數據是通過編輯器保存讀取的
由於時間不允許，沒有做編輯器，所以我就做了個存儲的類簡單的實現了下
Shared.lua就是存儲的類，其實裡面就是一個table，對外只提供一個GetData(name)的方法，如果沒有name的變數就創建個值為空的table保存起來，返回這個table
結構大致是data = {
name1 = {name = name1, val = val1},
…
name2 = {name = name2, val = val2},
}
之所以用table存，是因為table在lua中屬於引用類型
shared.lua程式碼如下：
1 BT.Shared = {} 2 BT.Shared.__index = BT.Shared 3 4 function BT.Shared:New() 5 local o = {} 6 setmetatable(o,BT.Shared) 7 o.data = {} -- val is [name] = {name = name,val = val} 8 return o 9 end 10 11 function BT.Shared:GetData(name) 12 if self.data[name] == nil then 13 self.data[name] = {name = name,val = nil} 14 end 15 return self.data[name] 16 end
View Code
那麼全局共享數據放在BTManager中，使得樹都可以訪問
樹內共享數據放在樹中
在樹執行Init時將樹傳給task
程式碼如下：
1 BT.Mgr = { 2 ... 3 globalSharedData = BT.Shared:New() 4 } 5 6 function BT.BTree:New(gameObject, name) 7 local o = {} 8 setmetatable(o,this) 9 ... 10 o.sharedData = BT.Shared:New() 11 o.globalSharedData = BT.Mgr.globalSharedData 12 ... 13 } 14 15 function BT.BTree:Init(task, parentIndex, compositeIndex) 16 task:Init(self) 17 ... 18 }
View Code
中斷的實現
中斷的實現應該是行為樹中比較複雜的功能了，涉及到樹上的一些演算法及運行棧的操作，牽涉到的判斷也多，這裡會重點講述
中斷必要的原因是可能存在以下情況（不限於此情況）：
比如怪物正在向目標點移動的時候遇到玩家需要攻擊，此時移動的節點狀態是running，沒有中斷的時候只能走到目標點的時候返回success停止移動才開始進入其他節點，這時候就錯過了攻擊玩家，中斷的作用就體現出來了，就算是在running狀態也能打斷運行棧進入攻擊節點
BehaviorDesigner打斷的方法是將打斷類型分為這麼幾類：
EAbortType = {
None = 0, //不打斷
Self = 1, //打斷自身
LowerPriority = 2, //打斷低優先順序
Both = 3, //同時包括Self和LowerPriority兩種效果
}
其中只有Composite類型的節點可以擁有打斷操作
Self打斷類型：指的是Composite節點下面的直系子孫（這個名詞是我臨時取得。。意思是Composite與Conditional中間可以插入Decorate，可以插入Composite但插入得Composite類型必須是Self或Both）Conditional類型的節點的狀態發生變化時，那麼打斷正在運行且是Composite子孫的分支，重新進入變化的Conditional節點所處的分支中。打斷的結構大概如下圖所示：
（綠色的指正在運行中的節點）
那麼Conditional變化時可以打斷Task2，當然如果Task1處於運行時也可以打斷，因為Composite2的打斷類型為Self且Composite3的打斷類型也是Self，即AbortType是可以遞歸的
運行棧回退到Composite和運行節點的最近公共祖先節點，在此圖中回退到Composite3節點處。
假設Composite2的打斷類型是None或者LowerPriority且正在運行的是Task1，那麼就不會打斷
LowerPriority打斷類型：指的是當Composite直系子孫（意思同上，只是插入的Composite必須是LowerPriority或Both）Conditional類型的節點的狀態變化時，那麼打斷運行節點所處分支是Composite兄弟節點分支，打斷結構如下圖所示：
假設正在運行的是Task1，那麼不可以打斷
通過以上的例子，我們可以知道，從Composite到Conditional是一條鏈也就是打斷鏈，將打斷鏈存儲下來，每次樹update的時候先判斷運行分支是否和打斷鏈上的節點處於同一分支，那麼就可以打斷
Self打斷鏈和LowerPriority的打斷鏈如圖所示：（當運行分支處於紅色節點分支中，則可以打斷）
當然還有一種情況例外，比如並行節點Parallel，也屬於Composite，但是兩個子分支之間是不能打斷的，如下圖所示，不能打斷Task，因為Conditional和Task是兩個運行棧
通過上面所說，我們只需要算出打斷鏈算出來並存儲下來進行計算即可。
只有Conditional進行過一次才可以進行中斷評估
那麼在節點出棧的時候進行計算，將打斷鏈接上自己的父親，或者刪除打斷鏈，程式碼如下所示：
1 function BT.BTree:PopTask(stackIndex, status) 2 ... 3 ... 4 --reevaluate 5 local parentCompositeIndex = self.tParentCompositeIndex[taskIndex] 6 local parentComposite = self.tTaskList[parentCompositeIndex] 7 8 --如果節點是Conditional類型且父親Composite有中斷類型，那麼創建中斷鏈保存起來 9 if task:CheckType(BT.Conditional) then 10 if parentComposite ~= nil and parentComposite.abortType ~= BT.EAbortType.None then 11 if self.tConditionalReevaluateDic[taskIndex] == nil then 12 local reevaluate = BT.Reevaluate:New(taskIndex, status, stackIndex, parentComposite.abortType == BT.EAbortType.LowerPriority and 0 or parentCompositeIndex, parentComposite.abortType) 13 table.insert(self.tConditionalReevaluate,reevaluate) 14 self.tConditionalReevaluateDic[taskIndex] = reevaluate 15 end 16 end 17 elseif task:CheckType(BT.Composite) then 18 19 repeat 20 --LowerPriority延遲指向 21 if task.abortType == BT.EAbortType.LowerPriority then 22 for i = 1, #self.tChildConditionalIndex[taskIndex] do 23 local reevalute = self.tConditionalReevaluateDic[self.tChildConditionalIndex[taskIndex][i]] 24 if reevalute ~= nil then 25 reevalute.compositeIndex = taskIndex 26 end 27 end 28 end 29 30 --指向自己的reevalute重新指向自己的父親 31 local lam_BothOrOther = function(tab,abortType) 32 if tab.abortType == abortType or tab.abortType == BT.EAbortType.Both then 33 return true 34 end 35 return false 36 end 37 38 for i = 1, #self.tConditionalReevaluate do 39 local reevalute = self.tConditionalReevaluate[i] 40 if reevalute.compositeIndex == taskIndex then 41 if lam_BothOrOther(task,BT.EAbortType.Self) and lam_BothOrOther(parentComposite,BT.EAbortType.Self) and lam_BothOrOther(reevalute,BT.EAbortType.Self) or 42 lam_BothOrOther(task,BT.EAbortType.LowerPriority) and lam_BothOrOther(reevalute,BT.EAbortType.LowerPriority) 43 then 44 reevalute.compositeIndex = parentCompositeIndex 45 if reevalute.abortType == BT.EAbortType.Both then 46 if task.abortType == BT.EAbortType.Self or parentComposite.abortType == BT.EAbortType.Self then 47 reevalute.abortType = BT.EAbortType.Self 48 elseif task.abortType == BT.EAbortType.LowerPriority or parentComposite.abortType == BT.EAbortType.LowerPriority then 49 reevalute.abortType = BT.EAbortType.LowerPriority 50 end 51 end 52 end 53 end 54 end 55 56 --自己已經出棧，刪除目前還指向自己的中斷鏈 57 for i = #self.tConditionalReevaluate,1,-1 do 58 local reevalute = self.tConditionalReevaluate[i] 59 if reevalute.compositeIndex == taskIndex then 60 self.tConditionalReevaluateDic[reevalute.index] = nil 61 table.remove(self.tConditionalReevaluate,i) 62 end 63 end 64 until(true) 65 66 end 67 if stack:Empty() then 68 self.tRunStack[stackIndex] = Const.Empty 69 end 70 task:OnEnd() 71 end
View Code
經過上一步就計算並保存了中斷鏈，接下來就是打斷操作，程式碼如下所示：
1 --遍歷所有的中斷鏈 2 function BT.BTree:ConditionalReevaluate() 3 for i = 1, #self.tConditionalReevaluate do 4 repeat 5 local reevalute = self.tConditionalReevaluate[i] 6 if reevalute == nil or reevalute.compositeIndex == 0 then 7 break 8 end 9 local status = self.tTaskList[reevalute.index]:OnUpdate() 10 if status == reevalute.status then 11 break 12 end 13 --打斷 14 local bBreak = false 15 for stackIndex = 1, #self.tRunStack do 16 repeat 17 if self.tRunStack[stackIndex] == Const.Empty then 18 break 19 end 20 local runIndex = self.tRunStack[stackIndex]:Peek() 21 local lcaIndex = self:LCA(reevalute.compositeIndex,runIndex) 22 --只有在reevaluate打斷鏈上的運行節點才能被打斷 23 if not self:IsParent(reevalute.compositeIndex,lcaIndex) then 24 break 25 end 26 --如果運行節點和reevaluate的conditional處於同一個並行節點的不同分支上，不能被打斷 27 if stackIndex ~= reevalute.stackIndex and self.tTaskList[self:LCA(reevalute.index,runIndex)]:CanExcuteParallel() then 28 break 29 end 30 31 if reevalute.abortType == BT.EAbortType.LowerPriority and self.tParentCompositeIndex[reevalute.index] == self.tParentCompositeIndex[runIndex] then 32 break 33 end 34 35 --更改運行棧 36 while true do 37 if self.tRunStack[stackIndex] == Const.Empty or self.tRunStack[stackIndex]:Empty() then 38 break 39 end 40 runIndex = self.tRunStack[stackIndex]:Peek() 41 if runIndex == lcaIndex then 42 self.tTaskList[lcaIndex]:OnConditionalAbort() 43 break 44 end 45 self:PopTask(stackIndex,BT.ETaskStatus.Inactive) 46 end 47 bBreak = true 48 until(true) 49 end 50 51 if not bBreak then 52 break 53 end 54 --刪除同一個中斷鏈且優先順序較低的reevalute 55 for j = #self.tConditionalReevaluate, i,-1 do 56 local nextReevalute = self.tConditionalReevaluate[j] 57 if self:IsParent(reevalute.compositeIndex,nextReevalute.index) then 58 self.tConditionalReevaluateDic[nextReevalute.index] = nil 59 table.remove(self.tConditionalReevaluate,j) 60 end 61 end 62 until(true) 63 end 64 end
View Code
至此，行為樹講述完畢
