1 BehaviorTreeNode = {}
 2 
 3 BehaviorTreeNode.Type = {
 4     ACTION = "ACTION",
 5     CONDITION = "CONDITION",
 6     SELECTOR = "SELECTOR",
 7     SEQUENCE = "SEQUENCE"
 8 }
 9 
10 function BehaviorTreeNode.new(name,type)
11     local node = {}
12 
13     node.action_ = nil
14     node.children_ = {}
15     node.evaluator_ = nil
16     node.name_ = name or ""
17     node.parent_ = nil
18     node.type_ = type or BehaviorTreeNode.Type.ACTION
19 
20     node.AddChild = BehaviorTreeNode.AddChild
21     node.ChildIndex = BehaviorTreeNode.ChildIndex
22     node.GetChild = BehaviorTreeNode.GetChild
23     node.GetNumberOfChildren = BehaviorTreeNode.GetNumberOfChildren
24 
25     node.GetParent = BehaviorTreeNode.GetParent
26     node.SetAction = BehaviorTreeNode.SetAction
27     node.SetEvaluator = BehaviorTreeNode.SetEvaluator
28     node.SetType = BehaviorTreeNode.SetType
29 
30     return node
31 end
32 
33 function BehaviorTreeNode.AddChild(self,child,index)
34     index = index or (#self.children_ + 1)
35     table.insert(self.children_,index,child)
36     child.parent_ = self
37 end
38 
39 function BehaviorTreeNode.ChildIndex(self,child)
40     for index = 1, #self.children_ do
41         if self.children_[index] == child then
42             return index
43         end
44     end
45 
46     return -1
47 end
48 
49 function BehaviorTreeNode.GetChild(self,childIndex)
50     return self.children_[childIndex]
51 end
52 
53 function BehaviorTreeNode.GetNumberOfChildren(self)
54     return #self.children_
55 end
56 
57 function BehaviorTreeNode.GetParent(self)
58     return self.parent_
59 end
60 
61 function BehaviorTreeNode.SetAction(self,action)
62     self.action_ = action
63 end
64 
65 function BehaviorTreeNode.SetEvaluator(self,evaluator)
66     self.evaluator_ = evaluator
67 end
68 
69 function BehaviorTreeNode.SetType(self,type)
70     self.type_ = type
71 end

  1 require "BehaviorTreeNode"
  2 require "Action"
  3 
  4 BehaviorTree = {}
  5 
  6 local _EvaluateSelector
  7 local _EvaluateSequence
  8 
  9 function BehaviorTree.SetNode(self,node)
 10     self.node_ = node
 11 end
 12 
 13 function BehaviorTree.new(userData)
 14     local tree = {}
 15 
 16     tree.currentNode_ = nil
 17     tree.node_ = nil
 18     tree.userData_ = userData
 19 
 20     tree.SetNode = BehaviorTree.SetNode
 21     tree.Update = BehaviorTree.Update
 22 
 23     return tree
 24 end
 25 
 26 _EvaluateSelector = function(self,node,deltaTimeInMillis)
 27     for index = 1,#node.children_ do
 28         local child = node:GetChild(index)
 29 
 30         if child.type_ == BehaviorTreeNode.Type.ACTION then
 31             return {node = child,result = true}
 32         elseif child.type_ == BehaviorTreeNode.Type.CONDITION then
 33             assert(false)
 34             return {result = false}
 35         elseif child.type_ == BehaviorTreeNode.Type.SELECTOR then
 36             local result = _EvaluateSelector(self,child,deltaTimeInMillis)
 37 
 38             if result.result then
 39                 return result
 40             end
 41         elseif child.type_ == BehaviorTreeNode.Type.SEQUENCE then
 42             local result = _EvaluateSequence(self,child,deltaTimeInMillis)
 43 
 44             if result.result then
 45                 return result
 46             end
 47         end
 48 
 49     end
 50 
 51     return {result = false}
 52 end
 53 
 54 _EvaluateSequence = function(self,node,deltaTimeInMillis,index)
 55 
 56     index = index or 1
 57 
 58     for count = index,#node.children_ do
 59         local child = node:GetChild(count)
 60 
 61         if child.type_ == BehaviorTreeNode.Type.ACTION then
 62             return  { node = child,result = true }
 63         elseif child.type_ == BehaviorTreeNode.Type.CONDITION then
 64             local result = child.evaluator_(self.userData_)
 65 
 66             if not result then
 67                 return {result = false}
 68             end
 69 
 70         elseif child.type_ == BehaviorTreeNode.Type.SELECTOR then
 71             local result = _EvaluateSelector(self,child,deltaTimeInMillis)
 72 
 73             if not result.result then
 74                 return {result = false}
 75             elseif result.result and result.node ~= nil then
 76                 return result
 77             end
 78         elseif child.type_ == BehaviorTreeNode.Type.SEQUENCE then
 79             local result = _EvaluateSequence(self,child,deltaTimeInMillis)
 80 
 81             if not result.result then
 82                 return {result = false}
 83             elseif result.result and result.node ~= nil then
 84                 return result
 85             end
 86 
 87         end
 88 
 89         count = count + 1
 90 
 91     end
 92 
 93     return {result = true}
 94 end
 95 
 96 local function _EvaluateNode(self,node,deltaTimeInMillis)
 97     if node.type_ == BehaviorTreeNode.Type.ACTION then
 98         return node
 99     elseif node.type_ == BehaviorTreeNode.Type.CONDITION then
100         assert(false)
101     elseif node.type_ == BehaviorTreeNode.Type.SELECTOR then
102         local result = _EvaluateSelector(self,node,deltaTimeInMillis)
103 
104         if result.result then
105             return result.node
106         end
107     elseif node.type_ == BehaviorTreeNode.Type.SEQUENCE then
108         local result = _EvaluateSequence(self,node,deltaTimeInMillis)
109 
110         if result.result then
111             return result.node
112         end
113     end
114 end
115 
116 local function _ContinueEvaluation(self,node,deltaTimeInMillis)
117     local parentNode = node:GetParent()
118     local childNode = node
119     while parentNode ~= nil do
120         if parentNode.type_ == BehaviorTreeNode.Type.SEQUENCE then
121             local childIndex = parentNode:ChildIndex(childNode)
122 
123             if childIndex < parentNode:GetNumberOfChildren() then
124                 local result = _EvaluateSequence(self,parentNode,deltaTimeInMillis,childIndex + 1)
125 
126                 if result.result then
127                     return result.node
128                 end
129             end
130         end
131 
132         childNode = parentNode
133         parentNode = childNode:GetParent()
134     end
135 end
136 
137 function BehaviorTree.Update(self,deltaTimeInMillis)
138     if self.currentNode_ == nil then
139         self.currentNode_ = _EvaluateNode(self,self.node_,deltaTimeInMillis)
140     end
141 
142     if self.currentNode_ ~= nil then
143         local status = self.currentNode_.action_.status_
144         if status == Action.Status.UNINIIALIZED then
145             self.currentNode_.action_:Initialize()
146         elseif status == Action.Status.TERMINATED then
147             self.currentNode_.action_:CleanUp()
148 
149             self.currentNode_ = _ContinueEvaluation(self,self.currentNode_,deltaTimeInMillis)
150 
151         elseif status == Action.Status.RUNNING then
152             self.currentNode_.action_:Update(deltaTimeInMillis)
153         end
154     end
155 end

 1 Action = {}
 2 
 3 Action.Status = {
 4     RUNNING = "RUNNING",
 5     TERMINATED = "TERMINATED",
 6     UNINIIALIZED = "UNINIIALIZED"
 7 }
 8 
 9 Action.Type = "Action"
10 
11 
12 function Action.new(name,initializeFunction,updateFunction,cleanUpFunction,userData)
13 
14     local action = {}
15 
16     action.cleanUpFunction_ = cleanUpFunction
17     action.initializeFunction_ = initializeFunction
18     action.updateFunction_  = updateFunction
19     action.name_ = name or ""
20     action.status_ = Action.Status.UNINIIALIZED
21     action.type_ = Action.Type
22     action.userData_ = userData
23 
24     action.CleanUp = Action.CleanUp
25     action.Initialize = Action.Initialize
26     action.Update = Action.Update
27 
28     return action
29 end
30 
31 function Action.Initialize(self)
32     if self.status_ == Action.Status.UNINIIALIZED then
33         if self.initializeFunction_ then
34             self.initializeFunction_(self.userData_)
35         end
36     end
37 
38     self.status_ = Action.Status.RUNNING
39 end
40 
41 
42 function Action.Update(self,deltaTimeInMillis)
43     if self.status_ == Action.Status.TERMINATED then
44         return Action.Status.TERMINATED
45     elseif self.status_ == Action.Status.RUNNING then
46         if self.updateFunction_ then
47             self.status_ = self.updateFunction_(deltaTimeInMillis,self.userData_)
48 
49             assert(self.status_)
50         else
51             self.status_ = Action.Status.TERMINATED
52         end
53     end
54 
55     return self.status_
56 
57 end
58 function Action.CleanUp(self)
59     if self.status_ == Action.Status.TERMINATED then
60         if self.cleanUpFunction_ then
61             self.cleanUpFunction_(self.userData_)
62         end
63     end
64 
65     self.status_ = Action.Status.UNINIIALIZED
66 end