[Unity] Behavior Tree

이전 포스팅에서 정리했었던 게임 AI 구현을 위한 디자인 패턴인 FSM의 단점이었던 상태가 많아질 수록 상태 전이 조건이 매우 복잡해진다는 단점을 해결하고 복잡한 행동 로직을 구현하기 위해 Behavior Tree를 사용한다.

 

BT는 논리적인 트리 구조를 사용하며 루트 노드에서 시작해 깊이 우선 탐색(DFS)으로 자식 노드를 평가하고 평가 결과를 다시 부모 노드에게 반환하는 구조를 가진다.

 

평가 결과는 일반적으로 아래 3가지 상태 중 하나를 반환한다.

1. Success : 노드가 조건을 만족함

2. Failure : 노드가 조건을 만족하지 않음

3. Running : 노드의 조건을 검사가 아직 진행중

* Running 상태는  조건의 평가 혹은 자식 노드들의 평가가 한 프레임만으로 처리될 수 없는 경우 게임의 흐름을 방해하지 않고 이를 다음 프레임에 다시 체크하기 위해 사용된다.

 

BT 에서 각 노드 타입은 다음과 같이 구분할 수 있다.

1. Action Node : 에이전트가 수행할 수 있는 어떤 종류의 행동도 될 수 있는 노드이다. 게임 캐릭터 AI의 경우 걷기, 공격하기, 적 탐지 등 행동에 대한 디테일한 구현이 정의되어야 한다. 중요한 점은 자식이 없는 계층의 가장 마지막 노드인 리프 노드(Leaf Node)이어야 한다는 점이다.

2. Composite Node : 합성 노드라고도 하며 하나 이상의 자식을 가지며 하나 이상의 자식을 수행하는 노드이다. 자식 노드들의 평가 결과를 통해 자신의 상태를 결정한다. 대표적인 합성 노드의 종류는 다음과 같다. 

1. 시퀀스 노드(Sequence node): 시퀀스 노드는 자식 노드들을 순서대로 실행한다. 하나의 자식 노드가 실패할 경우, 다음 자식 노드를 실행하지 않고 실패를 반환하며. 모든 자식 노드가 성공하면 성공을 반환한다.
2. 선택자 노드(Selector node): 선택자 노드는 자식 노드들을 순서대로 실행한다. 하나의 자식 노드가 성공할 경우, 다음 자식 노드를 실행하지 않고 성공을 반환한다. 모든 자식 노드가 실패하면 실패를 반환한다.
3. 병렬 노드(Parallel node): 병렬 노드는 자식 노드들을 병렬로 실행한다. 모든 자식 노드가 성공하면 성공을 반환한다. 모든 자식 노드가 실패하면 실패를 반환한다. 자식 노드 중 하나 이상이 Running 상태인 경우, Running을 반환한다.

3. Decorator Node : 자식 노드에 새로운 동작을 추가하거나 변경하는 역할을 하는 노드이다. 데코레이터 노드에는 다음과 같은 종류가 있다.

 

1. 인버터 노드(Inverter node): 자식 노드를 실행하고, 자식 노드가 실패하면 성공을 반환하고, 자식 노드가 성공하면 실패를 반환한다. 따라서, 자식 노드의 결과를 반대로 반환하는 데 사용된다.
2. 리피터 노드(Repeater node): 리피터 노드는 자식 노드를 지정된 횟수만큼 혹은 무한히 반복하게 한다.
3. 리미터 노드(Limiter node): 리미터 노드는 자식 노드를 지정된 시간 동안만 실행한다. 시간이 지난 후에는 Running 상태를 반환한다. 

---

위 내용을 바탕으로 BT를 구현해보자.

 

public enum BTNodeState
{
    Success,
    Failure,
    Running
}

먼저 각 노드의 평가 결과를 정의하는 열거형을 정의한다.

 

 

public abstract class BTNode
{
    protected List<BTNode> children = new List<BTNode>();

    public void AddChild(BTNode node)
    {
        children.Add(node);
    }

    public virtual BTNodeState Evaluate()
    {
        return BTNodeState.Failure;
    }
}

트리 구조에서 사용할 노드를 추상 클래스로 정의한다. childeren에 저장되는 노드는 트리에서 자식 노드를 뜻하며 Evaluate 메서드는 BT에서 핵심적인 역할을 하는 메서드로 상속받은 클래스에서 각 역할에 맞는 기능을 수행하고 평가 결과를 반환도록 구현한다.

다음부터는 노드들을 상속받는 각 노드 타입들을 구현해보자.

 

public class BTAction : BTNode
{
    private System.Func<BTNodeState> action;

    public BTAction(System.Func<BTNodeState> action)
    {
        this.action = action;
    }

    public override BTNodeState Evaluate()
    {
        return action();
    }
}

BT의 리프 노드에 해당하는 액션 노드이다. 특정 기능을 수행 후 노드의 평가 결과를 반환하는 기능을 하며 액션 노드의 형태는 액션 노드를 다시 상속받아 기능을 별도로 구현할 수 있지만 여기서는 간단하게 델리게이트로 수행하도록 한다.

 

public class BTSequence : BTNode
{
    public override BTNodeState Evaluate()
    {
        bool isAnyChildRunning = false;

        foreach (BTNode node in children)
        {
            BTNodeState result = node.Evaluate();
            if (result == BTNodeState.Failure)
            {
                return BTNodeState.Failure;
            }
            else if (result == BTNodeState.Running)
            {
                isAnyChildRunning = true;
            }
        }

        return isAnyChildRunning ? BTNodeState.Running : BTNodeState.Success;
    }
}

시퀀스 노드는 앞서 설명했던 컴포지트 노드 중 하나로 자식 노드들을 순차적으로 실행하는 노드이다. 트리 그래프 상 왼쪽부터 오른쪽 노드(코드상으로는 먼저 입력된 순으로 처리)로 순차적으로 실행하며 모든 자식 노드가 Success를 반환할 때 까지 실행을 계속한다. 만약 자식 노드 중 Failure를 반환한다면 즉시 실행을 중단하고 Failure를 반환한다.

 

public class BTSelector : BTNode
{
    public override BTNodeState Evaluate()
    {
        foreach (BTNode node in children)
        {
            BTNodeState result = node.Evaluate();
            if (result == BTNodeState.Success)
            {
                return BTNodeState.Success;
            }
            else if (result == BTNodeState.Running)
            {
                return BTNodeState.Running;
            }
        }

        return BTNodeState.Failure;
    }
}

셀렉터 노드 또한 컴포지트 노드 중 하나이며 마찬가지로 자식 노드를 왼쪽부터 오른쪽으로 순차적으로 실행하지만 자식 노드가 Success를 반환하면 즉시 실행을 중단하고 Success를 반환한다. 만약 모든 자식 노드가 Failure를 반환했다면 실행을 중단하고 Failure를 반환한다.

 

public class BTCondition : BTNode
{
    private System.Func<bool> condition;

    public BTCondition(System.Func<bool> condition)
    {
        this.condition = condition;
    }

    public override BTNodeState Evaluate()
    {
        return condition() ? BTNodeState.Success : BTNodeState.Failure;
    }
}

컨디션 노드는 노드 타입 중 데코레이터 노드 중 하나로, 조건을 검사하여 해당 조건식이 참이면 Success, 거짓이면 Failure를 반환하는 코드이다.  주로 시퀀스 노드나 셀렉터 노드와 함께 사용되어 자식 노드들의 실행을 제어하는 역할을 한다.

 

마지막으로 위에서 구현한 BT 노드들을 활용하는 몬스터 클래스 예시를 보자.

public class MonsterAI : MonoBehaviour
{
    public Transform playerTransform;
    public float attackRange = 1.5f;
    public float moveSpeed = 2.0f;

    private BTSelector root;

    private void Start()
    {
        root = new BTSelector();
        BTSequence attackSequence = new BTSequence();
        BTSequence chaseSequence = new BTSequence();
        BTAction attackAction = new BTAction(Attack);
        BTAction chaseAction = new BTAction(Chase);
        BTCondition playerInRange = new BTCondition(IsPlayerInRange);

        root.AddChild(attackSequence);
        root.AddChild(chaseSequence);
        attackSequence.AddChild(playerInRange);
        attackSequence.AddChild(attackAction);
        chaseSequence.AddChild(chaseAction);

        root.Evaluate();
    }

    private void Update()
    {
        root.Evaluate();
    }

    private bool IsPlayerInRange()
    {
        float distanceToPlayer = Vector3.Distance(transform.position, playerTransform.position);
        return distanceToPlayer <= attackRange;
    }

    private BTNodeState Attack()
    {
        Debug.Log("Attacking player!");
        return BTNodeState.Success;
    }

    private BTNodeState Chase()
    {
        Debug.Log("Chasing player!");
        transform.position = Vector3.MoveTowards(transform.position, playerTransform.position, moveSpeed * Time.deltaTime);
        return BTNodeState.Running;
    }
}

위 코드에서 구현된 몬스터 AI는 플레이어를 추적하면서 플레이어가 공격할 수 있는 거리안에 있을 때 공격한다.

Start에서 각 노드들을 선언해 몬스터 AI를 위한 BT를 생성하고 Update문에서 매 프레임마다 루트를 평가하고 잇다.

 

위 코드의 BT를 그림으로 표현하면 다음과 같다.

- 루트는 셀렉터이기 때문에 왼쪽 자식 노드(attackSequence)를 먼저 평가한다.

- attackSequence는 시퀀스로 왼쪽 자식부터 오른쪽 자식 노드로 순차적으로 평가하기 때문에 플레이어가 사정거리 안에 있는지 체크하는 playerRange를 먼저 평가한다.

 

[분기]

1.  playerRange가 참이라면 Success를 반환하기 때문에 시퀀스는 다음 노드인 attackAction이 실행된다.  

2.  playerRange가 거짓이라면 Failure를 반환하기 때문에 시퀀스는 즉시 중단되어 Failure를 반환한다. root 노드는 셀렉터이기 때문에             attckSequence에서 Failure가 반환되었다면 다음 노드인 chaseSequence를 평가한다.