LimboNova

行为树入门工具包

Posted on Nov 28, 2017

偶然看到一个2012年 Alex Champandard 的演讲1，本想看看有什么可以借鉴，看到一半后，发现就是 Game AI Pro 的文章 《The Behavior Tree Starter Kit2》的演示版。结合代码3，对照着看一遍，有助于理解。

Motivation

行为树广泛应用于各个系统：角色，策略，小队，动画，镜头……

使用案例：

  • Rockstar Games： R.A.G.E.
  • Guerrilla Games：Killzone 2 & 3
  • Uncharted 2
  • Halo 3
  • NBA ‘09
  • Metro 2033
  • Crysis: Warhead
  • League of Legends

The Basics

v1：原型

一个基本的行为树实现：

enum Status
/**
 * Return values of and valid states for behaviors.
 */
{
    BH_INVALID,
    BH_SUCCESS,
    BH_FAILURE,
    BH_RUNNING,
    BH_ABORTED,
};

class Behavior
/**
 * Base class for actions, conditions and composites.
 */
{
public:
    virtual Status update()				= 0;

    virtual void onInitialize()			{}
    virtual void onTerminate(Status)	{}

    Behavior()
    :   m_eStatus(BH_INVALID)
    {
    }

    virtual ~Behavior()
    {
    }

    Status tick()
    {
        if (m_eStatus != BH_RUNNING)
        {
            onInitialize();
        }

        m_eStatus = update();

        if (m_eStatus != BH_RUNNING)
        {
            onTerminate(m_eStatus);
        }
        return m_eStatus;
    }

    void reset()
    {
        m_eStatus = BH_INVALID;
    }

    void abort()
    {
        onTerminate(BH_ABORTED);
        m_eStatus = BH_ABORTED;
    }

    bool isTerminated() const
    {
        return m_eStatus == BH_SUCCESS  ||  m_eStatus == BH_FAILURE;
    }

    bool isRunning() const
    {
        return m_eStatus == BH_RUNNING;
    }

    Status getStatus() const
    {
        return m_eStatus;
    }

private:
    Status m_eStatus;
};

复合节点

class Composite : public Behavior
{
public:
    void addChild(Behavior* child) { m_Children.push_back(child); }
    void removeChild(Behavior*);
    void clearChildren();
protected:
    typedef std::vector<Behavior*> Behaviors;
    Behaviors m_Children;
};
Sequence
class Sequence : public Composite
{
protected:
    virtual ~Sequence()
    {
    }

    virtual void onInitialize()
    {
        m_CurrentChild = m_Children.begin();
    }

    virtual Status update()
    {
        // Keep going until a child behavior says it's running.
        for (;;)
        {
            Status s = (*m_CurrentChild)->tick();

            // If the child fails, or keeps running, do the same.
            if (s != BH_SUCCESS)
            {
                return s;
            }

            // Hit the end of the array, job done!
            if (++m_CurrentChild == m_Children.end())
            {
                return BH_SUCCESS;
            }
        }
    }

    Behaviors::iterator m_CurrentChild;
};
Selector

class Selector : public Composite
{
protected:
    virtual ~Selector()
    {
    }

    virtual void onInitialize()
    {
        m_Current = m_Children.begin();
    }

    virtual Status update()
    {
        // Keep going until a child behavior says its running.
		for (;;)
        {
            Status s = (*m_Current)->tick();

            // If the child succeeds, or keeps running, do the same.
            if (s != BH_FAILURE)
            {
                return s;
            }

            // Hit the end of the array, it didn't end well...
            if (++m_Current == m_Children.end())
            {
                return BH_FAILURE;
            }
        }
    }

    Behaviors::iterator m_Current;
};

v2：共享结构

一个简单的行为树原型很容易实现，但有内存占用的问题：即使它们使用同一个行为树，使用它的每个 Agent 都要创建各自的行为树实例。解决的办法就是分离行为数据。

节点

  • 所有行为树的公共数据
  • 树的基本结构
  • 所有参数和其它设置

任务

  • 运行时实例的特定数据
  • 指针，计数器……

基本节点

class Node;
class Task;

enum Status
{
	BH_INVALID,
	BH_SUCCESS,
	BH_FAILURE,
	BH_RUNNING,
};

class Node
{
public:
	virtual Task* create() = 0;
	virtual void destroy(Task*) = 0;

	virtual ~Node() {}
};

class Task
{
public:
	Task(Node& node)
	:	m_pNode(&node)
	{
	}

	virtual ~Task() {}

	virtual Status update() = 0;

	virtual void onInitialize() {}
	virtual void onTerminate(Status) {}

protected:
	Node* m_pNode;
};

class Behavior
{
protected:
	Task* m_pTask;
	Node* m_pNode;
	Status m_eStatus;

public:
	Behavior()
	:	m_pTask(NULL)
	,	m_pNode(NULL)
	,	m_eStatus(BH_INVALID)
	{
	}
	Behavior(Node& node)
	:	m_pTask(NULL)
	,	m_pNode(NULL)
	,	m_eStatus(BH_INVALID)
	{
		setup(node);
	}
	~Behavior()
	{
		m_eStatus = BH_INVALID;
		teardown();
	}

	void setup(Node& node)
	{
		teardown();

		m_pNode = &node;
		m_pTask = node.create();
	}
	void teardown()
	{
		if (m_pTask == NULL)
		{
			return;
		}

		ASSERT(m_eStatus != BH_RUNNING);
		m_pNode->destroy(m_pTask);
		m_pTask = NULL;
	}

	Status tick()
	{
		if (m_eStatus == BH_INVALID)
		{
			m_pTask->onInitialize();
		}

		m_eStatus = m_pTask->update();

		if (m_eStatus != BH_RUNNING)
		{
			m_pTask->onTerminate(m_eStatus);
		}

		return m_eStatus;
	}

	template <class TASK>
	TASK* get() const
	{
		// NOTE: It's safe to static_cast, the caller almost
		// always knows what kind of task type it is.
		return dynamic_cast<TASK*>(m_pTask);
	}
};

复合节点

typedef std::vector<Node*> Nodes;

class Composite : public Node
{
public:	
	Nodes m_Children;
};
Sequence
class Sequence : public Task
{
public:
	Sequence(Composite& node)
	:	Task(node)
	{
	}

	Composite& getNode()
	{
		return *static_cast<Composite*>(m_pNode);
	}

	virtual void onInitialize()
	{
		m_CurrentChild = getNode().m_Children.begin();
		m_CurrentBehavior.setup(**m_CurrentChild);
	}

	virtual Status update()
	{
		for (;;)
		{
			Status s = m_CurrentBehavior.tick();
			if (s != BH_SUCCESS)
			{
				return s;
			}
			if (++m_CurrentChild == getNode().m_Children.end())
			{
				return BH_SUCCESS;
			}
			m_CurrentBehavior.setup(**m_CurrentChild);
		}
	}

protected:
	Nodes::iterator m_CurrentChild;
	Behavior m_CurrentBehavior;
};
Selector
class Selector : public Task
{
public:
	Selector(Composite& node)
		:	Task(node)
	{
	}

	Composite& getNode()
	{
		return *static_cast<Composite*>(m_pNode);
	}

	virtual void onInitialize()
	{
		m_CurrentChild = getNode().m_Children.begin();
		m_Behavior.setup(**m_CurrentChild);
	}

	virtual Status update()
	{
		for (;;)
		{
			Status s = m_Behavior.tick();
			if (s != BH_FAILURE)
			{
				return s;
			}
			if (++m_CurrentChild == getNode().m_Children.end())
			{
				return BH_FAILURE;
			}
			m_Behavior.setup(**m_CurrentChild);
		}
	}

protected:
	Nodes::iterator m_CurrentChild;
	Behavior m_Behavior;
};

特点

优点

  • 易于实现
  • 易于调试
  • 易于理解 缺点
  • 代码完全基于轮询
  • 一系列的虚函数调用
  • 遍历过程涉及大量内存访问
  • 栈的最大大小取决于数据，潜在的栈溢出问题

Modern BTs

为了解决上述问题，可以编写一个专门的解释器，能够比C++更好地处理行为树。

优化策略：

  1. 使用直接办法
    • 设计数据结构
    • 减少函数调用
    • 考量内存访问
  2. 使用领域知识
    • 理解BT使用场景
    • 优化架构/算法
    • 简化BT结构

v3: Data-Oriented BT

优化内存分配

降低Cache miss，提高缓存一致性，内存分配采取以下方法：

  • 使用栈分配器为整个行为树分配内存
  • 连续分配行为树节点的内存
  • 默认使用深度优先顺序存储节点
  • 子节点紧随其父节点
代码实现

基础部分没有什么变化

enum Status
{
    BH_INVALID,
    BH_SUCCESS,
    BH_FAILURE,
    BH_RUNNING,
};

class Behavior
{
public:
    Behavior()
    :	m_eStatus(BH_INVALID)
    {
    }

    virtual ~Behavior()
    {
    }

    Status tick()
    {
        if (m_eStatus == BH_INVALID)
            onInitialize();

        m_eStatus = update();

        if (m_eStatus != BH_RUNNING)
            onTerminate(m_eStatus);

        return m_eStatus;
    }

protected:
	virtual Status update() = 0;

    virtual void onInitialize() {}
    virtual void onTerminate(Status) {}

    Status m_eStatus;
};

typedef std::vector<Behavior*> Behaviors;

变化在这里：

const size_t k_MaxBehaviorTreeMemory = 8192;

class BehaviorTree
{
public:
    BehaviorTree()
	:	m_pBuffer(new uint8_t[k_MaxBehaviorTreeMemory])
    ,	m_iOffset(0)
    {
    }

    ~BehaviorTree()
    {
        delete [] m_pBuffer;
    }

    template <typename T>
    T& allocate()
    {
		T* node = new ((void*)((uintptr_t)m_pBuffer + m_iOffset)) T;
        m_iOffset += sizeof(T);
		ASSERT(m_iOffset < k_MaxBehaviorTreeMemory);
        return *node;
    }

protected:
	uint8_t* m_pBuffer;
    size_t m_iOffset;
};

使用节点索引

降低内存消耗，可以使用以下方法：

  • 不依赖指针
  • 使用下标或相对偏移量
  • 让复合节点的子节点更易查找
代码实现
const size_t k_MaxChildrenPerComposite = 7;

class Composite : public Behavior
{
public:
    Composite()
    :	m_ChildCount(0)
    {
    }

    void addChild(Behavior& child)
    {
		ASSERT(m_ChildCount < k_MaxChildrenPerComposite);
		ptrdiff_t p = (uintptr_t)&child - (uintptr_t)this;
		ASSERT(p < std::numeric_limits<uint16_t>::max());
		m_Children[m_ChildCount++] = static_cast<uint16_t>(p);
    }

	Behavior& getChild(size_t index)
    {
		ASSERT(index < m_ChildCount);
		return *(Behavior*)((uintptr_t)this + m_Children[index]);
    }

	size_t getChildCount() const
    {
        return m_ChildCount;
    }

private:
	uint16_t m_Children[k_MaxChildrenPerComposite];
	uint16_t m_ChildCount;
};

class Sequence : public Composite
{
protected:
    virtual ~Sequence()
    {
    }

    virtual void onInitialize()
    {
        m_Current = 0;
    }

    virtual Status update()
    {
		for (;;)
        {
            Status s = getChild(m_Current).tick();
            if (s != BH_SUCCESS)
            {
                return s;
            }
            ASSERT(m_Current < std::numeric_limits<uint16_t>::max() - 1);
            if (++m_Current == getChildCount())
            {
                return BH_SUCCESS;
            }
        }
    }

	uint16_t m_Current;
};

class Selector : public Composite
{
protected:
        virtual ~Selector()
        {
        }

    virtual void onInitialize()
    {
        m_Current = 0;
    }

    virtual Status update()
    {		
		for (;;)
        {
            Status s = getChild(m_Current).tick();
            if (s != BH_FAILURE)
            {
                return s;
            }
            ASSERT(m_Current < std::numeric_limits<uint16_t>::max() - 1);
            if (++m_Current == getChildCount())
            {
                return BH_FAILURE;
            }
        }
    }

	uint16_t m_Current;
};

特点

优点

  • 实现难度不算太大
  • 优化方法简单易行

缺点

  • 不易调试，需要借助工具
  • 代码不易阅读和理解

v4: Event-Driven BT

执行顺序

首次遍历

  • 所有节点按深度优先顺序开始
  • 一切照旧

后续遍历

  • 不再从根节点遍历！
  • 子节点会广播其状态变化
  • 父节点做出响应并应用
  • 只在最坏的情况下，重新从根节点开始

代码实现

enum Status
{
    BH_INVALID,
    BH_SUCCESS,
    BH_FAILURE,
    BH_RUNNING,
    BH_SUSPENDED,
};

typedef std::function<void (Status)> BehaviorObserver;

class Behavior
{
public:
    Behavior()
    :	m_eStatus(BH_INVALID)
    {
    }

    virtual ~Behavior()
    {
    }

    Status tick()
    {
        if (m_eStatus == BH_INVALID)
        {
            onInitialize();
        }

        m_eStatus = update();

        if (m_eStatus != BH_RUNNING)
        {
            onTerminate(m_eStatus);
        }
        return m_eStatus;
    }

    virtual Status update() = 0;

    virtual void onInitialize() {}
    virtual void onTerminate(Status) {}

    Status m_eStatus;
    BehaviorObserver m_Observer;
};

class BehaviorTree
{
public:

    void start(Behavior& bh, BehaviorObserver* observer = NULL)
    {
        if (observer != NULL)
        {
            bh.m_Observer = *observer;
        }
        m_Behaviors.push_front(&bh);
    }

    void stop(Behavior& bh, Status result)
    {
        ASSERT(result != BH_RUNNING);
        bh.m_eStatus = result;

        if (bh.m_Observer)
        {
            bh.m_Observer(result);
        }
    }

    void tick()
    {
        // Insert an end-of-update marker into the list of tasks.
        m_Behaviors.push_back(NULL);

        // Keep going updating tasks until we encounter the marker.
        while (step())
        {
            continue;
        }
    }

    bool step()
    {
        Behavior* current = m_Behaviors.front();
        m_Behaviors.pop_front();

        // If this is the end-of-update marker, stop processing.
        if (current == NULL)
        {
            return false;
        }

        // Perform the update on this individual task.
        if (current->m_eStatus != Status::BH_SUSPENDED)
        {
            current->tick();
        }

        // Process the observer if the task terminated.
        if (current->m_eStatus != BH_RUNNING  &&  current->m_Observer)
        {
            current->m_Observer(current->m_eStatus);
        }
        else // Otherwise drop it into the queue for the next tick().
        {
            m_Behaviors.push_back(current);
        }
        return true;
    }

protected:
    std::deque<Behavior*> m_Behaviors;
};

// ============================================================================

class Composite : public Behavior
{
public:
    typedef std::vector<Behavior*> Behaviors;
    Behaviors m_Children;
};

class Sequence : public Composite
{
public:
    Sequence(BehaviorTree& bt)
    :	m_pBehaviorTree(&bt)
    {
    }

protected:
    BehaviorTree* m_pBehaviorTree;

    virtual void onInitialize()
    {
        m_Current = m_Children.begin();
        BehaviorObserver observer = std::bind(&Sequence::onChildComplete, this, std::placeholders::_1);
        m_pBehaviorTree->start(**m_Current, &observer);
    }

    void onChildComplete(Status)
    {
        Behavior& child = **m_Current;
        if (child.m_eStatus == BH_FAILURE)
        {
            m_pBehaviorTree->stop(*this, BH_FAILURE);
            return;
        }

        ASSERT(child.m_eStatus == BH_SUCCESS);
        if (++m_Current == m_Children.end())
        {
            m_pBehaviorTree->stop(*this, BH_SUCCESS);
        }
        else
        {
            BehaviorObserver observer = std::bind(&Sequence::onChildComplete, this, std::placeholders::_1);
            m_pBehaviorTree->start(**m_Current, &observer);
        }
    }

    virtual Status update()
    {
        return BH_RUNNING;
    }

    Behaviors::iterator m_Current;
};

特点

优点

  • 保证最小计算量
  • 容易实现一个单步调试工具
  • 优雅简洁

缺点

  • 使用回调函数，代码不直观，不易理解。
  • 不只依赖于优化技巧，还需要其他方面的知识。

What Next?

尚未实现的部分

节点

  • 装饰节点（Decorators）
  • 并行节点（Parellel）

API

  • 如何 abort()行为以及整个行为树
  • 如何支持不可中断的行为。

  1. https://www.youtube.com/watch?v=n4aREFb3SsU ↩︎

  2. https://www.gameaipro.com/GameAIPro/GameAIPro_Chapter06_The_Behavior_Tree_Starter_Kit.pdf ↩︎

  3. Behavior Tree Starter Kit (github.com) ↩︎