lua行为树设计与实现

来源：cnblogs　　作者：McYY丶　　时间：2019/10/22 12:51:18　　对本文有异议

项目需要，之前行为树用的是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