您的位置:澳门新葡萄京最大平台 > 动作小游戏 > 行为树理论及实现

行为树理论及实现

发布时间:2019-10-12 02:42编辑:动作小游戏浏览(197)

    从上古卷轴中丰富多彩的人员,到National Basketball Association2K中书写汗水的球员,从职分召唤中尔虞我诈的敌人,到刺客信条中活跃的人群。游戏AI差不离存在于游戏中的每一种角落,默默创设出一个令人恋慕的大幅游戏世界。
    那正是说那几个头眼昏花的AI又是怎么落实的啊?上边就让我们来掌握并亲手促成一下娱乐AI基础架构之一的一举一动树。

    表现树简要介绍

    行为树是一种树状的数据结构,树上的每二个节点都以贰个作为。每趟调用会从根节点开始遍历,通过检查行为的实行景况来实践不一的节点。他的独到之处是耦合度低扩张性强,每一个行为能够与其他展现完全部独用立。近些日子的一举一动树已经能够将大致率性架构(如规划器,功效论等)应用于AI之上。

    class BehaviorTree
    {
    public:
        BehaviorTree(Behavior* InRoot) { Root = InRoot; }
        void Tick()
        {
           Root->Tick();
        }
        bool HaveRoot() { return Root?true:false; }
        void SetRoot(Behavior* InNode) { Root= InNode; }
        void Release() { Root->Release(); }
    private:
        Behavior* Root;
    };
    

    地方提供了行为树的兑现,行为树有四个根节点和八个Tick()方法,在打闹经过中种种一段时间会调用依次Tick方法,令行为树从根节点初阶试行。

    行为(behavior)

    作为(behavior)是行为树最基础的定义,是差不离具有行为树节点的基类,是多个华而不实接口,而如动作规范等节点则是它的求实达成。
    下面是Behavior的完成,省略掉了一部分简易的论断状态的方法完整源码能够参见文尾的github链接

    class Behavior
    {
    public:
        //释放对象所占资源
        virtual void Release() = 0;
        //包装函数,防止打破调用契约
        EStatus Tick();
    
        EStatus GetStatus() { return Status; }
        virtual void AddChild(Behavior* Child){};
    
    protected:
        //创建对象请调用Create()释放对象请调用Release()
        Behavior():Status(EStatus::Invalid){}
        virtual ~Behavior() {}
        virtual void OnInitialize() {};
        virtual EStatus Update() = 0;
        virtual void OnTerminate(EStatus Status) {};
    
    protected:
        EStatus Status;
    };
    

    Behavior接口是全体行为举止树节点的中坚,且自个儿鲜明具备节点的组织和析构方法都必需是protected,防止止在栈上创立对象,全体的节点目的通过Create()静态方法在堆上创制,通过Release()方法销毁,由于Behavior是个抽象接口,故未有提供Create()方法,本接口满足如下左券

    • 在Update方法被第二回调用前,调用三次OnInitialize函数,负担伊始化等操作
    • Update()方法在作为树每一遍换代时调用且仅调用叁遍。
    • 充作为不再处于运市场价格况时,调用二遍OnTerminate(),并依靠再次回到状态不一样试行分歧的逻辑

    为了确认保障左券不被打破,大家将那四个措施包装在Tick()方法里。Tick()的实现如下

    //update方法被首次调用前执行OnInitlize方法,每次行为树更新时调用一次update方法
        //当刚刚更新的行为不再运行时调用OnTerminate方法
        if (Status != EStatus::Running)
        {
            OnInitialize();
        }
    
        Status = Update();
    
        if (Status != EStatus::Running)
        {
            OnTerminate(Status);
        }
    
        return Status;
    

    中间再次来到值Estatus是一个枚举值,表示节点运转境况。

    enum class EStatus:uint8_t
    {
        Invalid,   //初始状态
        Success,   //成功
        Failure,   //失败
        Running,   //运行
        Aborted,   //终止
    };
    

    动作(Action)

    动作是行为树的卡片节点,表示角色做的具体操作(如攻击,上弹,防范等),担负改动游戏世界的场所。动作节点可直接接轨自Behavior节点,通过兑现不相同的Update()方法达成区别的逻辑,在OnInitialize()方法中获取数据和财富,在OnTerminate中释放资源。

    //动作基类
    class Action :public Behavior
    {
    public:
        virtual void Release() { delete this; }
    
    protected:
        Action() {}
        virtual ~Action() {}
    };
    

    在那地作者完毕了叁个动作基类,首要是为着一个公用的Release方法担负释放节点内部存款和储蓄器空间,全数动作节点均可一连自这些措施

    条件

    准则一样是行为树的卡片节点,用于查看游戏世界音信(如冤家是或不是在抨击范围内,周边是不是有可攀登物体等),通过再次来到状态表示原则的打响。

    //条件基类
    class Condition :public Behavior
    {
    public:
        virtual void Release() { delete this; }
    
    protected:
        Condition(bool InIsNegation):IsNegation(InIsNegation) {}
        virtual ~Condition() {}
    
    protected:
        //是否取反
        bool  IsNegation=false;
    };
    

    那边小编达成了标准基类,二个IsNegation来标记规范是还是不是取反(比如是或不是看到仇敌得以成为是还是不是未有看到敌人)

    装饰器(Decorator)

    装饰器(Decorator)是唯有二个子节点的行事,看名就能够猜到其意义,装饰便是在子节点的原有逻辑上扩充细节(如重复施行子节点,更换子节点再次回到状态等)

    //装饰器
    class Decorator :public Behavior
    {
    public:
        virtual void AddChild(Behavior* InChild) { Child=InChild; }
    protected:
        Decorator() {}
        virtual ~Decorator(){}
        Behavior* Child;
    };
    

    落实了装饰器基类,下边大家来促成下实际的装饰器,相当于地点提到的再次实施多次子节点的装饰器

    class Repeat :public Decorator
    {
    public:
        static Behavior* Create(int InLimited) { return new Repeat(InLimited); }
        virtual void Release() { Child->Release(); delete this; }
    protected:
        Repeat(int InLimited) :Limited(InLimited) {}
        virtual ~Repeat(){}
        virtual void OnInitialize() { Count = 0; }
        virtual EStatus Update()override;
        virtual Behavior* Create() { return nullptr; }
    protected:
        int Limited = 3;
        int Count = 0;
    };
    

    正如下面提到的,Create函数负担成立节点,Release担负释放
    其间Update()方法的贯彻如下

    EStatus Repeat::Update()
    {
        while (true)
        {
            Child->Tick();
            if (Child->IsRunning())return EStatus::Success;
            if (Child->IsFailuer())return EStatus::Failure;
            if (++Count == Limited)return EStatus::Success;
            Child->Reset();
        }
        return EStatus::Invalid;
    }
    

    逻辑很轻松,倘若进行倒闭就当下回去,实践中就继续试行,试行成功就把计数器+1再度实践

    复合行为

    咱俩将作为树中具有四个子节点的行事称为复合节点,通过复合节点我们得以将轻易节点组合为更风趣更复杂的一言一动逻辑。
    上边达成了多少个切合节点的基类,将一些公用的措施放在了内部(如加多清除子节点等)

    //复合节点基类
    class Composite:public Behavior
    {  
        virtual void AddChild(Behavior* InChild) override{Childern.push_back(InChild);}
        void RemoveChild(Behavior* InChild);
        void ClearChild() { Childern.clear(); }
        virtual void Release()
        {
            for (auto it : Childern)
            {
                it->Release();
            }
    
            delete this;
        }
    
    protected:
        Composite() {}
        virtual ~Composite() {}
        using Behaviors = std::vector<Behavior*>;
        Behaviors Childern;
    };
    

    顺序器(Sequence)

    顺序器(Sequence)是复合节点的一种,它每一种施行种种子行为,直到全体子行为试行成功照旧有三个败诉告终。

    //顺序器:依次执行所有节点直到其中一个失败或者全部成功位置
    class Sequence :public Composite
    {
    public:
        virtual std::string Name() override { return "Sequence"; }
        static Behavior* Create() { return new Sequence(); }
    protected:
        Sequence() {}
        virtual ~Sequence(){}
        virtual void OnInitialize() override { CurrChild = Childern.begin();}
        virtual EStatus Update() override;
    
    protected:
        Behaviors::iterator CurrChild;
    };
    

    中间Update()方法的达成如下

    EStatus Sequence::Update()
    {
        while (true)
        {
            EStatus s = (*CurrChild)->Tick();
            //如果执行成功了就继续执行,否则返回
            if (s != EStatus::Success)
                return s;
            if (++CurrChild == Childern.end())
                return EStatus::Success;
        }
        return EStatus::Invalid;  //循环意外终止
    }
    

    选择器(Selector)

    接纳器(Selector)是另一种常用的复合行为,它会相继实践种种子行为直到当中贰个打响施行恐怕全体前功尽弃告终

    鉴于与顺序器仅仅是Update函数不一样,上边仅贴出Update方法

    EStatus Selector::Update()
    {
        while (true)
        {
            EStatus s = (*CurrChild)->Tick();
            if (s != EStatus::Failure)
                return s;   
            //如果执行失败了就继续执行,否则返回
            if (++CurrChild == Childern.end())
                return EStatus::Failure;
        }
        return EStatus::Invalid;  //循环意外终止
    }
    

    并行器(Parallel)

    顾名思义,并行器(Parallel)是一种让八个人作品表现并行施行的节点。但稳重侦查便会发觉其实只是他们的换代函数在平等帧被频仍调用而已。

    //并行器:多个行为并行执行
    class Parallel :public Composite
    {
    public:
        static Behavior* Create(EPolicy InSucess, EPolicy InFailure){return new Parallel(InSucess, InFailure); }
        virtual std::string Name() override { return "Parallel"; }
    
    protected:
        Parallel(EPolicy InSucess, EPolicy InFailure) :SucessPolicy(InSucess), FailurePolicy(InFailure) {}
        virtual ~Parallel() {}
        virtual EStatus Update() override;
        virtual void OnTerminate(EStatus InStatus) override;
    
    protected:
        EPolicy SucessPolicy;
        EPolicy FailurePolicy;
    };
    

    此地的Epolicy是三个枚举类型,表示成功和失败的规格(是打响或倒闭叁个照旧全体得逞或退步)

    //Parallel节点成功与失败的要求,是全部成功/失败,还是一个成功/失败
    enum class EPolicy :uint8_t
    {
        RequireOne,
        RequireAll,
    };
    

    update函数达成如下

    EStatus Parallel::Update()
    {
        int SuccessCount = 0, FailureCount = 0;
        int ChildernSize = Childern.size();
        for (auto it : Childern)
        {
            if (!it->IsTerminate())
                it->Tick();
    
            if (it->IsSuccess())
            {
                ++SuccessCount;
                if (SucessPolicy == EPolicy::RequireOne)
                {
                    it->Reset();
                    return EStatus::Success;
                }
    
            }
    
            if (it->IsFailuer())
            {
                ++FailureCount;
                if (FailurePolicy == EPolicy::RequireOne)
                {
                    it->Reset();
                    return EStatus::Failure;
                }       
            }
        }
    
        if (FailurePolicy == EPolicy::RequireAll&&FailureCount == ChildernSize)
        {
            for (auto it : Childern)
            {
                it->Reset();
            }
    
            return EStatus::Failure;
        }
        if (SucessPolicy == EPolicy::RequireAll&&SuccessCount == ChildernSize)
        {
            for (auto it : Childern)
            {
                it->Reset();
            }
            return EStatus::Success;
        }
    
        return EStatus::Running;
    }
    

    在代码中,并行器每一遍换代都实行每贰个尚无结束的子行为,并检讨成功和挫败条件,假若满意则立即赶回。
    另外,当并行器知足条件提前退出时,全体正在试行的子行为也相应及时被终止,大家在OnTerminate()函数中调用每一种子节点的告一段落方法

    void Parallel::OnTerminate(EStatus InStatus)
    {
         for (auto it : Childern)
        {
            if (it->IsRunning())
                it->Abort();
        }
    }
    

    监视器(Monitor)

    监视器是并行器的应用之一,通过在表现运行进程中不仅仅检查是不是满意某条件,要是不满足则即时退出。将标准放在并行器的尾巴就能够。

    再接再厉选用器

    继续努力选择器是选拔器的一种,与常见的选用器分化的是,主动选用器会不断的积极检查已经做出的仲裁,并连发的品味高优先级行为的可行性,当高优先级行为有效时胡立时打断低优先级行为的实行(如正在巡逻的长河中窥见仇人,即时中断巡逻,立刻攻击仇敌)。
    其Update()方法和OnInitialize方法完毕如下

    //初始化时将CurrChild初始化为子节点的末尾
    virtual void OnInitialize() override { CurrChild = Childern.end(); }
    
        EStatus ActiveSelector::Update()
        {
            //每次执行前先保存的当前节点
            Behaviors::iterator Previous = CurrChild;
            //调用父类OnInlitiallize函数让选择器每次重新选取节点
            Selector::OnInitialize();
            EStatus result = Selector::Update();
            //如果优先级更高的节点成功执行或者原节点执行失败则终止当前节点的执行
            if (Previous != Childern.end()&CurrChild != Previous)
            {
                (*Previous)->Abort();   
            }
    
            return result;
        }
    

    示例

    这里笔者创制了一名剧中人物,该剧中人物一同头处于巡逻情形,一旦开掘仇敌,先检查本身生命值是不是过低,假使是就逃跑,不然就攻击仇敌,攻击进程中假设生命值过低也会中断攻击,立时逃之夭夭,若是敌人过逝则立时停下攻击,这里大家利用了创设器来创制了一棵行为树,关于构建器的完毕前边会讲到,这里每一个函数创设了对应函数名字的节点,

    //构建行为树:角色一开始处于巡逻状态,一旦发现敌人,先检查自己生命值是否过低,如果是就逃跑,否则就攻击敌人,攻击过程中如果生命值过低也会中断攻击,立即逃跑,如果敌人死亡则立即停止攻击
        BehaviorTreeBuilder* Builder = new BehaviorTreeBuilder();
        BehaviorTree* Bt=Builder
            ->ActiveSelector()
                ->Sequence()
                    ->Condition(EConditionMode::IsSeeEnemy,false)
                         ->Back()       
                    ->ActiveSelector()
                         -> Sequence()
                              ->Condition(EConditionMode::IsHealthLow,false)
                                   ->Back()
                              ->Action(EActionMode::Runaway)
                                    ->Back()
                              ->Back()
                        ->Monitor(EPolicy::RequireAll,EPolicy::RequireOne)
                              ->Condition(EConditionMode::IsEnemyDead,true)
                                    ->Back()
                              ->Action(EActionMode::Attack)
                                    ->Back()
                              ->Back()
                        ->Back()
                    ->Back()
                ->Action(EActionMode::Patrol)
        ->End();
    
        delete Builder;
    

    接下来本人透过贰个巡回模拟行为树的举行。同一时常候在各条件节点内部通过任性数表示原则是不是推行成功(具体见文末github源码)

        //模拟执行行为树
        for (int i = 0; i < 10; ++i)
        {
            Bt->Tick();
            std::cout << std::endl;
        }
    

    施行结果如下,由于自由数的留存每趟实践结果都不相同样

    图片 1

    创设器的完成

    上面制造行为树的时候利用了创设器,上面作者就介绍一下和煦的创设器完毕

    //行为树构建器,用来构建一棵行为树,通过前序遍历方式配合Back()和End()方法进行构建
    class BehaviorTreeBuilder
    {
    public:
        BehaviorTreeBuilder() { }
        ~BehaviorTreeBuilder() { }
        BehaviorTreeBuilder* Sequence();
        BehaviorTreeBuilder* Action(EActionMode ActionModes);
        BehaviorTreeBuilder* Condition(EConditionMode ConditionMode,bool IsNegation);
        BehaviorTreeBuilder* Selector();
        BehaviorTreeBuilder* Repeat(int RepeatNum);
        BehaviorTreeBuilder* ActiveSelector();
        BehaviorTreeBuilder* Filter();
        BehaviorTreeBuilder* Parallel(EPolicy InSucess, EPolicy InFailure);
        BehaviorTreeBuilder* Monitor(EPolicy InSucess, EPolicy InFailure);
        BehaviorTreeBuilder* Back();
        BehaviorTree* End();
    
    private:
        void AddBehavior(Behavior* NewBehavior);
    
    private:
        Behavior* TreeRoot=nullptr;
        //用于存储节点的堆栈
        std::stack<Behavior*> NodeStack;
    };
    
    BehaviorTreeBuilder* BehaviorTreeBuilder::Sequence()
    {
        Behavior* Sq=Sequence::Create();
        AddBehavior(Sq);
        return this;
    }
    
    void BehaviorTreeBuilder::AddBehavior(Behavior* NewBehavior)
    {
        assert(NewBehavior);
        //如果没有根节点设置新节点为根节点
        if (!TreeRoot)
        {
            TreeRoot=NewBehavior;
        }
        //否则设置新节点为堆栈顶部节点的子节点
        else
        {
            NodeStack.top()->AddChild(NewBehavior);
        }
    
        //将新节点压入堆栈
        NodeStack.push(NewBehavior);
    }
    
    BehaviorTreeBuilder* BehaviorTreeBuilder::Back()
    {
        NodeStack.pop();
        return this;
    }
    
    BehaviorTree* BehaviorTreeBuilder::End()
    {
        while (!NodeStack.empty())
        {
            NodeStack.pop();
        }
        BehaviorTree* Tmp= new BehaviorTree(TreeRoot);
        TreeRoot = nullptr;
        return Tmp;
    }
    

    在下面的落实中,作者在每种方法里创造对应节点,检验当前是否有根节点,如果没有则将其设为根节点,假诺有则将其设为货仓最上端节点的子节点,随后将其压入货仓,每一回调用back则退栈,每一种创设节点的办法都回来this以方便调用下二个方法,最终经过End()表示作为树创制完毕并回到构建好的行事树。

    那正是说地点正是行为树的牵线和促成了,下一篇我们将对表现树进行优化,逐步走入第二代行为树。
    [github地址][1]

    本文由澳门新葡萄京最大平台发布于动作小游戏,转载请注明出处:行为树理论及实现

    关键词: