lua行为树设计与实现
分类:
IT文章
•
2022-04-06 09:08:46
项目需要，之前行为树用的是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
至此，行为树讲述完毕
欢迎转载，转载请注明出处：https://www.cnblogs.com/McYY/p/11689623.html，谢谢
