投稿
  1. 高性能架构探索首页
  2. C/C++

行为树的一个C++实现

admin • • C/C++ • 阅读 214

1. 基本概念

   行为树，英文是Behavior Tree，简称BT，是由行为节点组成的树状结构。在BT中，节点是有层次的，子节点由其父节点来控制。

   每个节点的执行都有一个结果（成功Success，失败Failure或运行Running），该节点的执行结果都由其父节点来管理，从而决定接下来做

   什么，父节点的类型决定了不同的控制类型。

   节点从结构上分为两类：组合节点、叶节点，所谓组合节点就是出度大于0的节点，叶节点一般用来放置执行逻辑和条件判断。

      1）序列（Sequence）节点：组合结点，顺序执行所有子节点，如果子节点全部执行成功，返回成功。如果某个子节点失败则返回失败，且不再执行下一个子节点。

      2）选择（Selector）结点：组合结点，顺序执行所有子节点，只要碰到一个子节点返回成功，则返回成功，否则继续执行下一个。如果子结点全都执行失败，则返回失败。

      3）并行（Parallel）结点：组合结点，并行其下所有子节点，所有节点成功则返回成功（有任意子节点失败则失败）。

      4）条件（Condition）节点：叶子结点，根据条件的比较结果，返回成功或失败。

      5）动作（Action）节点：叶子结点，根据动作结果返回成功，失败，或运行。

      6）等待（Wait）节点：叶子节点，当指定的时间过去后返回成功。

      7）循环（Loop）节点：叶子节点，循环执行子节点到指定次数后返回成功，如果循环次数为-1，则无限循环。

   比如我们要实现这个行为：如果碰到主角，打招呼；否则，睡觉。 

   行为树的一个C++实现

 

2. 通过Json建立行为树

   输入使用Json格式。从结构上看，所有的数据最终都可以分解成三种类型：

      1）标量（scalar）：也就是一个单独的字符串或数字。

      2）序列（sequence）：也就是若干个相关的数据按照一定顺序并列在一起，又叫做数组（array）或列表（List）。

      3）映射（mapping）：也就是一个名/值对（Name/value），即数据有一个名称，还有一个与之相对应的值，这又称作散列（hash）或字典（dictionary）。

   Json的书写规则如下：

      1） 并列的数据之间用逗号（","）分隔。

      2） 映射用冒号（":"）表示。

      3） 并列数据的集合（数组）用方括号("[]")表示。

      4） 映射的集合（对象）用大括号（"{}"）表示。

   下面举一个由输入Json来构建行为树的例子，执行效果是车辆先播放音乐，然后右转，然后停下来。

   行为树的一个C++实现       行为树的一个C++实现

 

3. 生成结点的工厂类实现

class BtNodeFactory 
{
public:
    virtual ~BtNodeFactory() {}
    virtual BtNode* CreateNode() = 0;

public:
    static BtNode* CreateNode(json_t *btJson) 
    {
        const char *key;
        json_t *value;
        std::string nodeType;
        json_object_foreach(btJson, key, value) 
        {
            if (strncmp(key, "type", 2) == 0 && json_is_string(value)) 
            {
                nodeType = json_string_value(value);
                break;
            }
        }
        std::map<std::string, BtNodeFactory*> *factoriesMap = BtNodeFactory::GetNodeFactoriesMap_();
        std::map<std::string, BtNodeFactory*>::iterator it = factoriesMap->find(nodeType);
        if (it == factoriesMap->end()) return NULL; // Not registered         
        BtNode *node = it->second->CreateNode();
        if (node) 
        {
            if(node->Load(btJson)) return node;
            else delete node;
        }
        return NULL;
    }

protected:
    static std::map<std::string, BtNodeFactory*> *GetNodeFactoriesMap_()
    {
        static std::map<std::string, BtNodeFactory*> factoriesMap;
        return &factoriesMap;
    }
};

template <class NodeClass>
class BtNodeFactoryTemplate : public BtNodeFactory 
{
public:
    virtual BtNode* CreateNode() { return new NodeClass(); }
    BtNodeFactoryTemplate(const std::string type) { (*BtNodeFactory::GetNodeFactoriesMap_())[type] = this; }
};

#define REGISTER_BT_NODE(_class_, __type__) static const BtNodeFactoryTemplate<_class_> _nodeFactory##_class_(__type__);

　　

4. 所有结点的基础类型(抽象接口)实现

   1）btNode.h代码

class BtNode
{
public:
    // Enumerates the states every node can be in after execution during a particular time step:
    // - "Idle"    indicates that the node hasn't run yet.
    // - "Running" indicates that the node has successfully moved forward during this time step, but the task is not yet complete;
    // - "Success" indicates that the node has completed running during this time step;
    // - "Failure" indicates that the node has determined it will not be able to complete its task;
    // - "Halted"  indicates that the node has been halted by its father.
    enum NodeState { Idle, Running, Success, Failure, Halted, Exit };

public:
    BtNode(std::string const& type) : parent(NULL), name_("null"), _type(type), _state(Idle) {}
    virtual ~BtNode() { _state = BtNode::Exit; }

public:
    // Load or Dump Behavior Tree
    virtual bool Load(json_t *btJson);
    virtual json_t *Dump();

    NodeState Play(BtBlackBoard& blackBoard);
    NodeState Halt(BtBlackBoard& blackBoard);
    NodeState Stop(BtBlackBoard& blackBoard);

    // The method that retrive the state of the node
    NodeState GetNodeState() { return _state; }

    BtNode *parent;

protected:
    virtual NodeState OnStart_(BtBlackBoard& blackBoard) = 0;
    virtual NodeState OnPause_(BtBlackBoard& blackBoard) = 0;
    virtual NodeState OnResume_(BtBlackBoard& blackBoard) = 0;
    virtual NodeState OnStop_(BtBlackBoard& blackBoard) = 0;

    std::string name_;

private:
    std::string _type;
    NodeState _state;
};

　　2）btNode.cpp代码

       Play、Halt、Stop代码进行了状态判断，比如只有当开始状态是Idle时，才能执行OnStart_。

bool BtNode::Load(json_t *btJson)
{
    if(json_is_object(btJson) == false) return false;
    const char *key;
    json_t *value;
    json_object_foreach(btJson, key, value) 
    {
        if(strncmp(key, "type", 2) == 0 && json_is_string(value)) 
            if (strcmp(json_string_value(value), _type.c_str())) // 类型对不上
                return false;
        else if(strncmp(key, "name", 2) == 0 && json_is_string(value)) 
            name_ = json_string_value(value);
    }
    return true;
}

json_t *BtNode::Dump()
{
    json_t *btJson = json_object();
    if (btJson) 
    {
        json_object_set_new(btJson, "type", json_string(_type.c_str()));
        json_object_set_new(btJson, "name", json_string(name_.c_str()));

        std::string stateString = "Error Value";
        const char* stateStringList_[] = {"Idle", "Running", "Success", "Failure", "Halted", "Exit"};
        if (_state >= BtNode::Idle && _state <= BtNode::Exit) 
            stateString = stateStringList_[_state];
        json_object_set_new(btJson, "[state]", json_string(stateString.c_str()));
    }
    return btJson;
}

BtNode::NodeState BtNode::Play(BtBlackBoard& blackBoard)
{
    if (_state == BtNode::Running || _state == BtNode::Halted) 
        _state = OnResume_(blackBoard);
    else if (_state == BtNode::Idle) 
        _state = OnStart_(blackBoard);
    return _state;
}

BtNode::NodeState BtNode::Halt(BtBlackBoard& blackBoard)
{
    if (_state == BtNode::Running) 
        _state = OnPause_(blackBoard);
    return _state;
}

BtNode::NodeState BtNode::Stop(BtBlackBoard& blackBoard)
{
    if (_state == BtNode::Running || _state == BtNode::Halted || _state == BtNode::Success || _state == BtNode::Failure) 
        _state = OnStop_(blackBoard);
    return _state;
}　

 

5. 组合结点的基础类型实现

   继承BtNode，是组合结点类型的基类，如parallel、selector、sequence等需要继承这个类，而叶子结点类型只需要继承BtNode类。

   1）BtGroupNode.h代码

class BtGroupNode : public BtNode
{
public:
    // Enumerates the options for when a parallel node is considered to have failed:
    // - "FailOnOne" indicates that the node will return failure as soon as one of its children fails;
    // - "FailOnAll" indicates that all of the node's children must fail before it returns failure.
    enum FailurePolicy {FailOnOne, FailOnAll};

    // Enumerates the options for when a parallel node is considered to have succeeded:
    // - "SucceedOnOne" indicates that the node will return success as soon as one of its children succeeds;
    // - "SucceedOnAll" indicates that all of the node's children must succeed before it returns success.
    enum SuccessPolicy {SucceedOnOne, SucceedOnAll};

public:
    BtGroupNode(std::string const& type);
    virtual ~BtGroupNode();

public:
    // Load or Dump Behavior Tree
    virtual bool Load(json_t *btJson);
    virtual json_t *Dump();

protected:
    std::vector<BtNode *> childNodes_;
    SuccessPolicy successPolicy_;
    FailurePolicy failurePolicy_;
};

   2）BtGroupNode.cpp代码

BtGroupNode::BtGroupNode(std::string const& type)
    : BtNode(type)
    , successPolicy_(SucceedOnAll)
    , failurePolicy_(FailOnAll)
{
}

BtGroupNode::~BtGroupNode()
{
    std::vector<BtNode *>::iterator iter;
    for(iter = childNodes_.begin(); iter != childNodes_.end(); iter++) 
    {
        if (*iter) 
            delete (*iter);
    }
    childNodes_.clear();
}

bool BtGroupNode::Load(json_t *btJson)
{
    if(BtNode::Load(btJson) == false) return false; 
    const char *key;
    json_t *value;
    json_object_foreach(btJson, key, value) 
    {
        if(strncmp(key, "behaviors", 2) == 0 && json_is_array(value)) 
        {
            unsigned int index;
            json_t *child;
            json_array_foreach(value, index, child) 
            {
                BtNode *node = BtNodeFactory::CreateNode(child);
                if (node) 
                {
                    childNodes_.push_back(node);
                    node->parent = this;
                }
            }
        }
        else if(strncmp(key, "successPolicy", 2) == 0 && json_is_string(value)) 
        {
            std::string valueString = json_string_value(value);
            if (valueString == "SucceedOnOne") 
                successPolicy_ = SucceedOnOne;
        }
        else if(strncmp(key, "failurePolicy", 2) == 0 && json_is_string(value)) 
        {
            std::string valueString = json_string_value(value);
            if (valueString == "FailOnAll") 
                failurePolicy_ = FailOnAll;
        }
    }
    return true;
}

json_t* BtGroupNode::Dump()
{
    json_t *btJson = BtNode::Dump();
    if (btJson == NULL) 
        return NULL; 
    json_object_set_new(btJson, "successPolicy", json_string(successPolicy_ == SucceedOnOne ? "SucceedOnOne" : "SucceedOnAll"));
    json_object_set_new(btJson, "failurePolicy", json_string(failurePolicy_ == FailOnAll ? "FailOnAll" : "FailOnOne"));
    json_t *childrenJson = json_array();
    if (childrenJson) 
    {
        std::vector<BtNode *>::iterator iter;
        for (iter = childNodes_.begin(); iter != childNodes_.end(); ++iter) 
        {
            if (*iter) 
            {
                json_t *childJson = (*iter)->Dump();
                json_array_append_new(childrenJson, childJson);
            }
        }
        json_object_set_new(btJson, "children", childrenJson);
    }
    return btJson;
}

　　

 6. parallel并行节点类实现

   1）BtParallelNode.h代码

class BtParallelNode : public BtGroupNode
{
public:
    BtParallelNode() : BtGroupNode(NODE_TYPE) {};
    ~BtParallelNode() {};

protected:
    virtual NodeState OnStart_(BtBlackBoard& blackBoard);
    virtual NodeState OnPause_(BtBlackBoard& blackBoard);
    virtual NodeState OnResume_(BtBlackBoard& blackBoard);
    virtual NodeState OnStop_(BtBlackBoard& blackBoard);
};

   2）BtParallelNode.cpp代码

// from Idle to Running, Success, Failure
BtNode::NodeState BtParallelNode::OnStart_(BtBlackBoard& blackBoard)
{
    unsigned int failureCount = successCount = 0;
    std::vector<BtNode *>::iterator iter;
    for(iter = childNodes_.begin(); iter != childNodes_.end(); ++iter) 
    {
        BtNode::NodeState result = (*iter)->Play(blackBoard);
        if (result == Running)
            continue;
        if(result == BtNode::Success) 
            successCount++;
        else if(result == BtNode::Failure) 
            failureCount++;
    }
    if(failurePolicy_ == FailOnOne && failureCount) return BtNode::Failure;     // 孩子节点中存在 Failure 
    if(successPolicy_ == SucceedOnOne && successCount) return BtNode::Success;  // 孩子结点中存在 Success
    if(failurePolicy_ == FailOnAll && failureCount = childNodes_.size()) return BtNode::Failure;     // 孩子节点全部 Failure 
    if(successPolicy_ == SucceedOnAll && successCount = childNodes_.size()) return BtNode::Success;  // 孩子结点全部 Success
    if((failureCount + successCount) == childNodes_.size()) return BtNode::Failure;
    return BtNode::Running;    // 孩子结点全部都是 Running 状态
}

// from Halt, Running to Running, Success, Failure
BtNode::NodeState BtParallelNode::OnResume_(BtBlackBoard& blackBoard)
{
    unsigned int failureCount = successCount = 0;
    std::vector<BtNode *>::iterator iter;
    for(iter = childNodes_.begin(); iter != childNodes_.end(); ++iter) 
    {
        BtNode::NodeState result = (*iter)->Play(blackBoard);
        if (result == Running)
            continue;
        if(result == BtNode::Success) 
            successCount++;
        else if(result == BtNode::Failure) 
            failureCount++;
    }
    if(failurePolicy_ == FailOnOne && failureCount) return BtNode::Failure;     // 孩子节点中存在 Failure 
    if(successPolicy_ == SucceedOnOne && successCount) return BtNode::Success;  // 孩子结点中存在 Success
    if(failurePolicy_ == FailOnAll && failureCount = childNodes_.size()) return BtNode::Failure;     // 孩子节点全部 Failure 
    if(successPolicy_ == SucceedOnAll && successCount = childNodes_.size()) return BtNode::Success;  // 孩子结点全部 Success
    if((failureCount + successCount) == childNodes_.size()) return BtNode::Failure;
    return BtNode::Running;    // 孩子结点全部都是 Running 状态
}

// from Running to Halt
BtNode::NodeState BtParallelNode::OnPause_(BtBlackBoard& blackBoard)
{
    std::vector<BtNode *>::iterator iter;
    for(iter = childNodes_.begin(); iter != childNodes_.end(); ++iter) 
        (*iter)->Halt(blackBoard);
    return BtNode::Halted;
}

// from Success, Failure, Running, Halt to Idle
BtNode::NodeState BtParallelNode::OnStop_(BtBlackBoard& blackBoard)
{
    std::vector<BtNode *>::iterator iter;
    for(iter = childNodes_.begin(); iter != childNodes_.end(); iter++) 
        (*iter)->Stop(blackBoard);
    return BtNode::Idle;
}

 

7. sequence序列节点类实现

　　1）BtSequenceNode.h代码

class BtSequenceNode : public BtGroupNode
{
public:
    BtSequenceNode() : BtGroupNode("sequence")
    ~BtSequenceNode() {}

protected:
    virtual NodeState OnStart_(BtBlackBoard& blackBoard);
    virtual NodeState OnPause_(BtBlackBoard& blackBoard);
    virtual NodeState OnResume_(BtBlackBoard& blackBoard);
    virtual NodeState OnStop_(BtBlackBoard& blackBoard);

};

    2）BtSequenceNode.cpp代码

// from Idle to Running, Success, Failure
BtNode::NodeState BtSequenceNode::OnStart_(BtBlackBoard& blackBoard)
{
    unsigned int failureCount = successCount = 0;
    std::vector<BtNode *>::iterator iter;
    for (iter = childNodes_.begin(); iter != childNodes_.end(); ++iter) 
    {
        BtNode::NodeState result = (*iter)->Play(blackBoard);
        if (result == Running)
            return BtNode::Running;
        if (result == BtNode::Success) 
            successCount++;
        else if(result == BtNode::Failure) 
            failureCount++;
    }
    if(failurePolicy_ == FailOnOne && failureCount) return BtNode::Failure;     // 孩子节点中存在 Failure 
    if(successPolicy_ == SucceedOnOne && successCount) return BtNode::Success;  // 孩子结点中存在 Success
    if(failurePolicy_ == FailOnAll && failureCount = childNodes_.size()) return BtNode::Failure;     // 孩子节点全部 Failure 
    if(successPolicy_ == SucceedOnAll && successCount = childNodes_.size()) return BtNode::Success;  // 孩子结点全部 Success
    if((failureCount + successCount) == childNodes_.size()) return BtNode::Failure;
    return BtNode::Failure;
}

// from Halt, Running to Running, Success, Failure
BtNode::NodeState BtSequenceNode::OnResume_(BtBlackBoard& blackBoard)
{
    unsigned int failureCount = successCount = 0;
    std::vector<BtNode *>::iterator iter;
    for(iter = childNodes_.begin(); iter != childNodes_.end(); ++iter) 
    {
        BtNode::NodeState result = (*iter)->Play(blackBoard);
        if(result == BtNode::Running)
            return result;
        if (result == Success) 
            successCount++;
        else if(result == BtNode::Failure) 
            failureCount++;
    }
    if(failurePolicy_ == FailOnOne && failureCount) return BtNode::Failure;     // 孩子节点中存在 Failure 
    if(successPolicy_ == SucceedOnOne && successCount) return BtNode::Success;  // 孩子结点中存在 Success
    if(failurePolicy_ == FailOnAll && failureCount = childNodes_.size()) return BtNode::Failure;     // 孩子节点全部 Failure 
    if(successPolicy_ == SucceedOnAll && successCount = childNodes_.size()) return BtNode::Success;  // 孩子结点全部 Success
    if((failureCount + successCount) == childNodes_.size()) return BtNode::Failure;
    return BtNode::Failure;
}

// from Running to Halt
BtNode::NodeState BtSequenceNode::OnPause_(BtBlackBoard& blackBoard)
{
    std::vector<BtNode *>::iterator iter;
    for (iter = childNodes_.begin(); iter != childNodes_.end(); ++iter) 
    {
        BtNode::NodeState state = (*iter)->GetNodeState();
        if (state == BtNode::Running)
            return (*iter)->Halt(blackBoard);
    }
    return BtNode::Failure;
}

// from Success, Failure, Running, Halt to Idle
BtNode::NodeState BtSequenceNode::OnStop_(BtBlackBoard& blackBoard)
{
    std::vector<BtNode *>::iterator iter;
    for (iter = childNodes_.begin(); iter != childNodes_.end(); ++iter) 
        (*iter)->Stop(blackBoard);
    return BtNode::Idle;
}

 

8. action动作节点类实现

   1）BtActionNode.h代码

class BtActionNode : public BtNode
{
public:
    class IPlayer 
    {
    public:
        typedef enum
        {
            STATE_UNKNOWN = 0,
            STATE_STOP = 1,
            STATE_PLAY = 2,
            STATE_PAUSE = 3
        }PlayerStatus;

        IPlayer() {}
        virtual ~IPlayer() {}
        virtual bool Play(std::string const& actionName, float duration) = 0;
        virtual bool Pause(std::string const& actionName) = 0;
        virtual bool Resume(std::string const& actionName) = 0;
        virtual bool Stop(std::string const& actionName) = 0;
        virtual bool GetStatus(std::string const &action, PlayerStatus &status) = 0;
    };

public:
    BtActionNode() : BtNode("action"), _duration(0)
    ~BtActionNode();

public:
    // Load or Dump Behavior Tree
    virtual bool Load(json_t *btJson);
    virtual json_t *Dump();

protected:
    virtual NodeState OnStart_(BtBlackBoard& blackBoard);
    virtual NodeState OnPause_(BtBlackBoard& blackBoard);
    virtual NodeState OnResume_(BtBlackBoard& blackBoard);
    virtual NodeState OnStop_(BtBlackBoard& blackBoard);

private:
    std::string _action;
    float _duration;
};

   2）BtActionNode.cpp代码

bool BtActionNode::Load(json_t *btJson)
{
    if (BtNode::Load(btJson) == false) return false; 
    const char *key;
    json_t *value;
    json_object_foreach(btJson, key, value) 
    {
        if (strncmp(key, "duration", 2) == 0 && json_is_number(value)) 
            _duration = json_number_value(value) * 1000;
        else if (strncmp(key, "action", 2) == 0 && json_is_string(value)) 
            _action = json_string_value(value);
    }
    return true;
}

json_t *BtActionNode::Dump()
{
    json_t *btJson = BtNode::Dump();
    if (btJson) 
    {
        json_object_set_new(btJson, "action", json_string(_action.c_str()));
        json_object_set_new(btJson, "duration", json_integer(_duration));
    }
    return btJson;
}

BtNode::NodeState BtActionNode::OnStart_(BtBlackBoard& blackBoard)
{
    IPlayer *player = NULL;
    if (blackBoard.GetValue("Action", player) && player) 
        return player->Play(_action, _duration) ? BtNode::Running : BtNode::Failure;
    return BtNode::Failure;
}

BtNode::NodeState BtActionNode::OnPause_(BtBlackBoard& blackBoard)
{
    IPlayer *player = NULL;
    if (blackBoard.GetValue("Action", player) && player) 
        return player->Pause(_action) ? BtNode::Halted : BtNode::Failure;
    return BtNode::Failure;
}

BtNode::NodeState BtActionNode::OnResume_(BtBlackBoard& blackBoard)
{
    IPlayer *player = NULL;
    if (blackBoard.GetValue("Action", player) && player) 
        return player->Resume(_action) ? BtNode::Running : BtNode::Failure;
    return BtNode::Failure;
}

BtNode::NodeState BtActionNode::OnStop_(BtBlackBoard& blackBoard)
{
    IPlayer *player = NULL;
    if (blackBoard.GetValue("Action", player) && player) 
        return player->Stop(_action) ? BtNode::Idle : BtNode::Failure;
    return BtNode::Failure;
}

 

　　

原文链接: https://www.cnblogs.com/yanghh/p/12924745.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    行为树的一个C++实现

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/349718

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 上午5:49
下一篇 2023年3月2日 上午5:50

相关推荐