behavior tree

A behavior tree framework for Golang.

一、简介

什么是行为树？
参考 Chat GPT 的回答：
- 行为树（Behavior Tree）是一种用于描述和控制角色、机器人、NPC 等实体行为的一种树状结构。
- 行为树由一系列节点组成，每个节点代表一个行为或条件，并根据节点之间的关系来确定实体的行为。
- 行为树通常由根节点、内部节点和叶节点组成，根节点是整个行为树的入口，内部节点用于控制子节点的执行顺序和条件，叶节点则代表具体的行为或条件判断。
行为树的应用场景非常广泛，主要用于游戏开发、机器人控制、虚拟人物行为设计等领域。在游戏开发中，行为树可以用于描述 NPC 的行为逻辑，例如敌人的巡逻、追击和攻击行为，使游戏角色表现出更加智能和自然的行为。在机器人控制方面，行为树可以用于描述机器人的行为策略，例如在复杂环境中进行导航、避障、抓取等操作。在虚拟人物行为设计中，行为树可以用于描述人物的情绪、社交行为和动作表现，使虚拟人物更加生动和具有个性。
总的来说，行为树是一种灵活且强大的行为建模工具，可以帮助开发者设计和实现复杂的行为逻辑，提升实体的智能和交互性，为各种应用场景提供有效的解决方案。
因此，本文说明行为树框架的要点及实现。

二、行为树节点及规则

1、行为树运行规则

通常，行为树的节点是不能阻塞的，由一个线程（或协程）调度 Tick，定时 Tick 行为树，行为树会重新刷新一遍（某些节点可能在 Tick 中不会被执行，具体见行为树节点的定义）。
行为树状态达到终态（行为树的状态即为根节点的状态）时，后续 Tick 所有节点都将不再被执行

2、行为树节点

一般的，行为树节点包括：
- 叶子节点（Leaf Node）
- 复合节点（Composite Node）
- 装饰节点（Decorative Node）
叶子节点：真正执行业务逻辑的单元
复合节点：控制执行顺序和条件；对多个子节点的聚合，按一定规则执行子节点
装饰节点：控制的执行顺序和条件；有且仅有一个子节点，是对子节点的装饰

3、叶子节点

叶子节点主要包括：
- 行为节点（Action Node）
- 条件节点（Condition Node）
对叶子节点的抽象（注意，Name 方法通常应该注意保证在所有节点中的唯一性）：
```
type LeafNode interface {
    Name() string
    Blackboards() []Blackboard
}
```

行为节点通常包括 Action 方法：

type ActionNode interface {
    LeafNode
    Action(context.Context, []Blackboard) TickStatus
}

条件节点通常包括 Condition 方法：

type ConditionNode interface {
    LeafNode
    Condition(context.Context, []Blackboard) bool
}

注意到：
- Blackboards() 方法返回了 Blackboard 列表，叶子节点执行时接收参数 Blackboard 列表，什么是 Blackboard？

4、Blackboard

什么是 Blackboard？
参考 Chat GPT 的回答：
- Blackboard 是一个用于存储和共享信息的数据结构。它可以被所有的行为节点（准确的说是叶子节点，即：行为节点和条件节点）访问和修改，用于在执行行为时传递信息和状态
Blackboard 的作用包括：
- 存储临时数据和状态信息：Blackboard 可以用于存储当前的环境信息、任务状态、目标等数据，以便行为节点在执行时进行参考。
- 共享信息：Blackboard 可以在不同的行为节点之间共享信息，使得不同的行为节点可以协同工作，实现复杂的行为逻辑。
- 控制行为执行：Blackboard 中的信息可以影响行为节点的执行顺序和决策，从而实现更加灵活和智能的行为控制。
- 动态更新：Blackboard 中的信息可以根据环境变化和任务需求进行动态更新，使得系统能够适应不同的情况和需求。

这里，对 Blackboard 的抽象定义为：

// In behavior trees, the blackboard is a mechanism for sharing data storage
// used to pass and share information between different nodes.
// Nodes can read and modify data on the blackboard to share information during decision-making and execution processes.
type Blackboard interface {
    // Name returns a string as a unique identifier for the blackboard.
    Name() string

    // Default creates a default blackboard if it is used by the leaf node but not passed when building the behavior tree.
    Default() Blackboard

    // Reset resets the blackboard when creating the behavior tree.
    Reset()
}

注意 Name 方法通常应该保证在所有 Blackboard 中的唯一性。

5、节点状态

在说明复合节点和装饰节点前，需要先知道什么是节点状态
本质上，前面提到的叶子节点、复合节点、装饰节点都是 Ticker，能够进行 Tick 并返回 Tick 状态

对 Tick 状态的定义如下：

/* ============================== TickStatus ============================== */
//

type TickStatus byte

const (
    TickStatusNotTick TickStatus = iota
    TickStatusSuccess
    TickStatusFailure
    TickStatusRunning
)

func (s TickStatus) String() string {
    switch s {
    case TickStatusNotTick:
        return "NotTick"
    case TickStatusSuccess:
        return "Success"
    case TickStatusFailure:
        return "Failure"
    case TickStatusRunning:
        return "Running"
    }
    panic(errors.New("unknown node status"))
}

func (s TickStatus) IsFinal() bool {
    return s == TickStatusSuccess || s == TickStatusFailure
}

func (s TickStatus) Invert() TickStatus {
    switch s {
    case TickStatusSuccess:
        return TickStatusFailure
    case TickStatusFailure:
        return TickStatusSuccess
    default:
        return s
    }
}

上述定义了节点的 Tick 状态、终态、以及状态对应的相反状态
TickStatusNotTick：表示节点从未被执行过
TickStatusSuccess：表示节点执行成功
TickStatusFailure：表示节点执行失败
TickStatusRunning：表示节点尚未执行完成
一般的，行为树 Tick 刷新时，处于终态的节点会被跳过不再执行，除非其状态被重置
行为节点执行后可以是 TickStatusSuccess、TickStatusFailure、TickStatusRunning 状态
条件节点返回 bool 值，只有 TickStatusSuccess、TickStatusFailure 状态，没有 TickStatusRunning 状态

6、复合节点

复合节点主要包括：
- 顺序节点（Sequence Node）
- 选择节点（Selector Node）
- 并行节点（Parallel Node）
顺序节点的执行规则：
- 示例有如下顺序节点：
```
Sequence
-- SubTreeA
-- SubTreeB
-- SubTreeC
```
- Sequence 节点在被 Tick 时，会按顺序 Tick 其直接子节点（本质上是子树）SubTreeA、SubTreeB、SubTreeC，满足：
  - 任意节点 Tick 状态是 Running 时，Sequence 的 Tick 状态是 Running，后续子节点不再 Tick
  - 任意节点 Tick 状态是 Failure 时，Sequence 的 Tick 状态是 Failure，后续子节点不再 Tick
  - 所有节点都是 Success 时，Sequence 的 Tick 状态是 Success
- 有点像与逻辑：A && B && C
选择节点的执行规则：
- 示例有如下选择节点：
```
Selector
-- SubTreeA
-- SubTreeB
-- SubTreeC
```
- Selector 节点在被 Tick 时，会按顺序 Tick 其直接子节点（本质上是子树）SubTreeA、SubTreeB、SubTreeC，满足：
  - 任意节点 Tick 状态是 Running 时，Selector 的 Tick 状态是 Running，后续子节点不再 Tick
  - 任意节点 Tick 状态是 Success 时，Selector 的 Tick 状态是 Success，后续子节点不再 Tick
  - 所有节点都是 Failure 时，Selector 的 Tick 状态是 Failure
  - 有点像或逻辑：A || B || C
并行节点执行规则：
- 示例有如下选择节点：
```
Parallel
-- SubTreeA
-- SubTreeB
-- SubTreeC
```
- Parallel 在被 Tick 时，会按顺序 Tick 其直接子节点（本质上是子树）SubTreeA、SubTreeB、SubTreeC，满足：
  - 不论子节点返回什么状态，所有子节点都会被 Tick
  - 所有子节点 Tick 完后，若存在 Success 的情况，则 Parallel 的 Tick 状态为 Success
  - 所有子节点 Tick 完后，若不存在 Success 的情况，但是存在 Failure 的情况，则 Parallel 的 Tick 状态为 Failure
  - 所有子节点 Tick 完后，所有子节点状态都是 Running，则 Parallel 的 Tick 状态为 Running

7、装饰节点

装饰节点主要包括（有且仅有一个子节点）：
- 成功节点（Succeeder Node）
- 反转节点（Inverter Node）
- 重复节点（Repeater Node）
- 重复直到失败节点（RepeatUntilFail Node）
成功节点：
- 不论子节点返回什么状态，均返回 Success
反转节点：
- 返回与子节点相反的状态，Running->Running, Success->Failure, Failure->Success
通过成功节点与反转节点，即可组合出失败节点
重复节点：
- 不论子节点返回什么，都返回 Running，若子节点返回的不是 Running 状态，则子树在下次 Tick 前会被重置
重复直到失败节点：
- 直到子节点返回 Failure 状态时，返回 Failure 状态；若子节点返回 Success 状态，则子树在下次 Tick 前会被重置

8、可选装饰节点

成功节点（Succeeder Node）不论子节点返回什么状态，均返回 Success，相反的可以有失败节点（Failure Node）：不论子节点返回什么状态，均返回 Failure
```
Failure
-- SubTree
```
等效于：
```
Inverter
-- Succeeder
  -- SubTree
```
同样的，重复直到失败节点（RepeatUntilFail Node），也可以对应（RepeatUntilSucceed Node）：
```
RepeatUntilFail
-- SubTree
```

等效于：

Inverter
-- RepeatUntilSucceed
  -- Inverter
    -- SubTree

三、DSL

行为树支持支持 DSL（Domain Specific Language, 领域特定语言）生成，一般的，可以定义 DSL，编译生成 Json 等可反序列化为静态行为树，再由静态行为树生成动态行为树
引入 DSL 会导致行为树变得更复杂，行为树代码跳转也会更不易。DSL 不是本文的重点，但是提供 DSL 的替代方案：
- 可以直接用 Golang 编写行为树，得到的是 StaticTree，对 StaticTree 序列化（如 json 序列化）即可得到 DSL 编写编译生成的序列化文件
- 再对得到的序列化文件加载反序列化，即可得到 StaticTree，就像没有中间的序列化反序列化以及 DSL 编译过程一样

jsontree.go 中实现了对 StaticTree 的序列化与反序列化，序列化结构如下：

type JsonTreeNode struct {
    Name  string     `json:"name"`
    Depth uint16     `json:"depth"`
    Type  TickerType `json:"type"`
}

type JsonTree struct {
    Name  string         `json:"name"`
    Nodes []JsonTreeNode `json:"nodes"`
}

通过序列化的 StaticTree 文件，按需加载，一定程度能够降低内存占用，提高编译速度。

四、示例

这里示例同时按时间间隔采样输出日志，以及按次数输入日志，执行：go test
代码示例：见 behaviortree_test.go
大致流程：
- 定义节点
- 创建节点对象
- 创建行为树

行为树示例：

var (
    counterSampleLogTree = bt.NewCompiler("counterSampleLogTree").
        Sequence("counter sample log").
        I__().Action(ResetCounterSampleLogCount).
        I__().Repeater("").
        I__().I__().Selector("").
        I__().I__().I__().Sequence("").
        I__().I__().I__().I__().Condition(IsCounterSampleLogMoreThanCount).
        I__().I__().I__().I__().Succeeder("force true").
        I__().I__().I__().I__().I__().Action(CounterSampleLog).
        I__().I__().I__().I__().Action(ResetCounterSampleLogCount).
        I__().I__().I__().Action(IncreaseCounterSampleLogCount).
        Compile()
)

以上定义了一棵根据 count 采样的日志的行为树，若没有达到 Count 计数，则增加 Count，到达 Count 计数后则输出日志，并重新计数，一直循环。
ResetCounterSampleLogCount 重置 Count，IsCounterSampleLogMoreThanCount 检测是否达到 Count，CounterSampleLog 输出日志，IncreaseCounterSampleLogCount 增加 Count 计数。

Name		Name	Last commit message	Last commit date
Latest commit History 4 Commits
common		common
log		log
README.md		README.md
behaviortree_test.go		behaviortree_test.go
benchmark_test.go		benchmark_test.go
blackboard.go		blackboard.go
builder.go		builder.go
compiler.go		compiler.go
go.mod		go.mod
jsontree.go		jsontree.go
logger.go		logger.go
node.go		node.go
option.go		option.go
ticker.go		ticker.go
tree.go		tree.go

uzutizd/behaviortree

Folders and files

Latest commit

History

Repository files navigation

behavior tree

一、简介

二、行为树节点及规则

1、行为树运行规则

2、行为树节点

3、叶子节点

4、Blackboard

5、节点状态

6、复合节点

7、装饰节点

8、可选装饰节点

三、DSL

四、示例

About

Resources

Stars

Watchers

Forks

Languages