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
至此，行为树讲述完毕
