Behavior Tree

트리구조로 되어있고, 게임개발 혹은 인공지능 시스템에서 사용되는 디자인 패턴 중 하나이다. 

게임 서버내에 npc의 경우 위에 해당되는 경우라서, FSM 혹은 Behavior Tree 방식이 주로 활용된다. 

일전에 봤던 코드는 FSM(유한 상태 머신) 에 가까운 코드였는데, 이번에 접하게 된 코드는 Behavior Tree 를 이용해 AI 가 구성되어 있었고, 새로 공부하면서 글을 작성한다. 

 

아래는 간단한 예제. 

#include <iostream>
#include <vector>

// 동작 트리 노드 클래스
class BTNode {
public:
    virtual ~BTNode() {}

    // 동작 실행 메서드
    virtual bool run() = 0;
};

// 동작 트리 내부 노드 클래스
class BTComposite : public BTNode {
public:
    virtual ~BTComposite() {}

    // 자식 노드 추가 메서드
    void addChild(BTNode* child) {
        children.push_back(child);
    }

protected:
    std::vector<BTNode*> children;
};

// 시퀀스 노드 클래스
class BTSequence : public BTComposite {
public:
    virtual bool run() {
        for (BTNode* child : children) {
            if (!child->run()) {
                return false;
            }
        }
        return true;
    }
};

// 선택 노드 클래스
class BTSelector : public BTComposite {
public:
    virtual bool run() {
        for (BTNode* child : children) {
            if (child->run()) {
                return true;
            }
        }
        return false;
    }
};

// 조건 노드 클래스
class BTCondition : public BTNode {
public:
    BTCondition(bool condition) : condition(condition) {}

    virtual bool run() {
        return condition;
    }

private:
    bool condition;
};

// 동작 노드 클래스
class BTAction : public BTNode {
public:
    BTAction(const std::string& name) : name(name) {}

    virtual bool run() {
        std::cout << "Running action: " << name << std::endl;
        // 여기에 동작의 실제 구현을 추가할 수 있습니다.
        return true;
    }

private:
    std::string name;
};

int main() {
    // 동작 트리 구성
    BTSequence* root = new BTSequence();

    BTSelector* selector = new BTSelector();
    BTCondition* condition = new BTCondition(true);
    BTAction* action1 = new BTAction("Action 1");
    BTAction* action2 = new BTAction("Action 2");

    root->addChild(selector);
    root->addChild(action1);

    selector->addChild(condition);
    selector->addChild(action2);

    // 동작 트리 실행
    root->run();

    // 동작 트리 메모리 해제
    delete root;
    delete selector;
    delete condition;
    delete action1;
    delete action2;

    return 0;
}

 

추가로 병렬노드도 있다. 

 

// 병렬 노드 클래스
class BTParallel : public BTComposite {
public:
    BTParallel() : successThreshold(1), failureThreshold(children.size()) {}

    void setSuccessThreshold(int threshold) {
        successThreshold = threshold;
    }

    void setFailureThreshold(int threshold) {
        failureThreshold = threshold;
    }

    virtual bool run() {
        int successCount = 0;
        int failureCount = 0;

        for (BTNode* child : children) {
            if (child->run()) {
                successCount++;
            } else {
                failureCount++;
            }
        }

        return successCount >= successThreshold || failureCount >= failureThreshold;
    }

private:
    int successThreshold;
    int failureThreshold;
};

BTComposite 를 상속받아 만들어지는 Node 들은 시퀀스, 선택, 병렬노드 이렇게 세가지가 존재한다. 

이들 노드들은 자식노드들을 실행하기 위한 노드이며, 흐름제어를 도와주는 역할을 한다. 

 

아래 자식으로 포함될 작업노드들의 경우 작업을 한 뒤, true or false 만 return 해주게 되면, 

부모노드(composite)의 종류에 따라서, 계속해서 다음 작업을 할지, 상위 squence 노드의 종류에 따라 결정되게 된다. 

 

작업 노드의 경우, Task 혹은 Action 혹은 Execution 등의 이름으로 사용하기도 한다. 

 

작업 노드와 컴포지트 노드 사이에, Decorator Node 가 있다. 

Decorator 노드는 조건검사 또는 동작 변형을 수행할 수 있는 노드이다. 

 

추가적으로 언리얼 엔진에 있는 Behavior tree에서 BlackBoard 에 대해 알아보았다.

참고 - https://forums.unrealengine.com/t/blackboard-documentation/1795

Blackboard Documentation

 

정말 간단하게 설명하자면, 행동트리의 경우 AI로직을 포함하는 AI 프로세서인데, 언리얼에 있는 BlackBoard는 AI의 뇌라고 할 수 있다. 

개별 AI 혹은 AI집단의 의사결정에 참고하거나 도움될 만한 정보를 저장할 수 있는 공유메모리하고 생각하면된다.