[Unity] Behavior Tree(BT) 만들어보기

1. Behavior Tree

Behavior Tree에 대한 이론은 가볍게만 짚고 넘어가려고 합니다

틀린 점이나 공유할만한 내용이 있다면 댓글로 공유해 주세요!

AI를 구현할 때 간단한 AI는 FSM으로도 충분히 구현할 수 있습니다.

FSM이란, 유한상태기계(finite-state machine, FSM)의 줄임말입니다.
말 그대로 “유한한 개수의 상태를 가질 수 있는 기계”를 뜻하고 A상태에서 B상태로 변화하는 것을 “전이(Transition)”이라고 합니다.
대표적인 예가 Unity의 Animator입니다.

간편해 보이는 FSM 또는 HFSM으로 복잡한 구조를 구현하다 보면 복잡성으로 인해 한계에 부딪히게 되는데
이를 극복하고자 나온 방법이 Behavior Tree입니다.
 

1.1 탐색 순서

Behavior Tree는 트리 구조이기 때문에 위에서 아래로, 왼쪽에서 오른쪽 순으로 진행하게 됩니다.
 

1.2 노드 구조

노드를 어떻게 구성했냐에 따라 다르지만
보통 Action(leaf node), Selector, Sequence 3개의 노드는 기본적으로 가지고 있습니다.
 

1.3 노드 상태

각 노드들은 자신의 상태를 반환해야 합니다
이 또한 어떻게 구성했냐에 따라 다르겠지만 대부분 아래 3가지로 구분합니다

• Failure(실패)
• Running(동작 중)
• Success(성공)

---

2. Node

2-1. Action Node(leaf Node)

Action Node는 말 그대로 “행동을 정의한 노드“입니다.
그렇기 때문에 트리의 leaf node로 있어야 합니다.

2-2. Selector Node

• or 연산자와 동일한 기능을 하는 노드입니다.
• 자식 노드들을 왼쪽에서 오른쪽 순으로 진행합니다.
  • 우선순위가 높은 자식 노드일수록 왼쪽에 배치되어야 합니다. 
  • 자식 노드들 중에서 성공한 노드가 있다면 그 노드를 실행하고 종료합니다.
  • 여기서 성공이란, Success / Running을 뜻합니다.
• 여러 행동 중 하나만 실행해야 할 때 사용하기 좋습니다.

2-3. Sequence Node

• and 연산자와 동일한 기능을 합니다.
• 자식 노드들을 왼쪽에서 오른쪽 순으로 진행합니다.
  • 먼저 진행해야 할 자식 노드가 왼쪽에 위치해야 합니다 
  • 자식 노드들 중에서 실패(Failure)한 노드가 있을 때까지 진행합니다.
• 여러 행동을 순서대로 진행해야 할 때 사용하기 좋습니다

---

3. Code(C#)로 Node 구현하기

유니티를 통해서 Behavior Tree를 구현해보려고 합니다.
구현하기 앞서, 각 노드들을 어떻게 코드로 구현할 수 있는지 살펴보도록 하겠습니다.
 

3-1. INode (interface)

노드의 통일성을 위해서 인터페이스 INode를 만들어 줍니다.
인터페이스에서 Node의 상태와 노드가 어떤 상태인지를 반환하는 Evaluate() 메소드를 추가했습니다.

public interface INode
{
    public enum ENodeState
    {
        ENS_Running,
        ENS_Success,
        ENS_Failure,
    }

    public ENodeState Evaluate();
}

3-2. Action Node

Action Node는 실제로 어떤 행위를 하는 노드입니다.
그렇기 때문에 Func() 델리게이트를 통해 행위를 전달받아 실행하려고 합니다

using System;

public sealed class ActionNode : INode
{
    Func<INode.ENodeState> _onUpdate = null;

    public ActionNode(Func<INode.ENodeState> onUpdate)
    {
        _onUpdate = onUpdate;
    }

    public INode.ENodeState Evaluate() => _onUpdate?.Invoke() ?? INode.ENodeState.ENS_Failure;
}

3-3. Selector Node

Selector Node는 자식 노드 중에서 처음으로 Success 나 Running 상태를 가진 노드가 발생하면 그 노드까지 진행하고 멈춥니다.
그러므로 Evaluate() 메소드 구현은 아래와 같습니다.

• 자식 상태: Running일 때 -> Running 반환
• 자식 상태: Success 일 때 -> Success 반환
• 자식 상태: Failure일 때 -> 다음 자식으로 이동

using System.Collections.Generic;

public sealed class SelectorNode : INode
{
    List<INode> _childs;

    public SelectorNode(List<INode> childs)
    {
        _childs = childs;
    }

    public INode.ENodeState Evaluate()
    {
        if (_childs == null)
            return INode.ENodeState.ENS_Failure;

        foreach (var child in _childs)
        {
            switch (child.Evaluate())
            {
                case INode.ENodeState.ENS_Running:
                    return INode.ENodeState.ENS_Running;
                case INode.ENodeState.ENS_Success:
                    return INode.ENodeState.ENS_Success;
            }
        }

        return INode.ENodeState.ENS_Failure;
    }
}

3-4. Sequence Node

Sequence Node는 자식 노드를 왼쪽에서 오른쪽으로 진행하면서 Failure 상태가 나올 때까지 진행하게 됩니다.
그러므로 Evaluate() 메소드 구현은 아래와 같습니다.

• 자식 상태: Running 일 때 -> Running 반환
• 자식 상태: Success 일 때 -> 다음 자식으로 이동
• 자식 상태: Failure 일 때 -> Failure 반환

3-4-1. Sequence Node의 주의점

여기서 주의할 점이 하나 있는데
Running 상태일 때는 그 상태를 계속 유지해야 하기 때문에 다음 자식 노드로 이동하면 안 되고
다음 프레임 때도 그 자식에 대한 평가를 진행해야 합니다.
 
예를 들어,
Sequence Node에 적 발견(Detect), 이동(Move), 공격(Attack) 총 3개의 자식 노드가 있다고 가정해 보겠습니다.

프레임마다 노드에 진입하는 상황은 “N차”로 가정하였습니다.

1차: 적을 발견하고 적을 향해 이동합니다.
2차: 발견한 적을 향해 아직 이동 중입니다.
3차: 발견한 적을 향해 아직 이동 중입니다.
4차: 이동이 완료되어 적을 공격합니다.
 
만약 이때 running에서 반환되지 않고 다음 자식 노드로 이동하게 되면 어떻게 될까요??
당연히 아직 적에게 다가가지도 못했는데 적을 향해 공격하게 됩니다.
 
그러므로, Running 상태에서는 Success와 다르게 다음 자식으로 이동하지 않고 Running을 반환해 줘서 다음 진입 시에도 Running 상태를 유지할 수 있도록 해주어야 합니다.

using System.Collections.Generic;

public sealed class SequenceNode : INode
{
    List<INode> _childs;

    public SequenceNode(List<INode> childs)
    {
        _childs = childs;
    }

    public INode.ENodeState Evaluate()
    {
        if (_childs == null || _childs.Count == 0)
            return INode.ENodeState.ENS_Failure;

        foreach (var child in _childs)
        {
            switch (child.Evaluate())
            {
                case INode.ENodeState.ENS_Running:
                    return INode.ENodeState.ENS_Running;
                case INode.ENodeState.ENS_Success:
                    continue;
                case INode.ENodeState.ENS_Failure:
                    return INode.ENodeState.ENS_Failure;
            }
        }

        return INode.ENodeState.ENS_Success;
    }
}

---

4. Unity로 Behavior Tree 구현해 보기

적을 탐지해서 공격하는 AI를 BT를 통해 구현해보려고 합니다.
구현하려는 BT는 아래와 같습니다.

노드 구현에 관한 코드는 3번에서 모두 설명하였음으로 생략합니다.

4-1. class BehaviorTreeRunner

BT를 실행하기 위해서 BehaviorTreeRunner class를 구현합니다.

구현은 간단해서 코드로도 충분히 이해하실 수 있다고 생각하기 때문에 설명은 생략했습니다.

public class BehaviorTreeRunner
{
    INode _rootNode;
    public BehaviorTreeRunner(INode rootNode)
    {
    _rootNode = rootNode;
    }

    public void Operate()
    {
        _rootNode.Evaluate();
    }
}

4-2. class EnemyAI

이제 EnemyAI를 구현해야 합니다.
일단 BehaviorTreeRunner 생성자로 넘겨줄 INode 인스턴스를 위해 아래와 같이 SettingBT() 메소드를 구현했습니다

메소드 내용은 위의 BT 구조를 그대로 넣어준 것입니다.

INode SettingBT()
{
    return new SelectorNode
    (
        new List<INode>()
        {
            new SequenceNode
            (
                new List<INode>()
                {
                    new ActionNode(CheckMeleeAttacking),
                    new ActionNode(CheckEnemyWithinMeleeAttackRange),
                    new ActionNode(DoMeleeAttack),
                }
            ),
            new SequenceNode
            (
                new List<INode>()
                {
                    new ActionNode(CheckDetectEnemy),
                    new ActionNode(MoveToDetectEnemy),
                }
            ),
            new ActionNode(MoveToOriginPosition)
        }
    );
}

 
 
메소드를 보면 ActionNode 생성자로 함수이름을 넘겨주는데 ActionNode 코드를 다시 살펴보면 아래와 같습니다.

using System;

public sealed class ActionNode : INode
{
    Func<INode.ENodeState> _onUpdate = null;

    public ActionNode(Func<INode.ENodeState> onUpdate)
    {
        _onUpdate = onUpdate;
    }

    public INode.ENodeState Evaluate() => _onUpdate?.Invoke() ?? INode.ENodeState.ENS_Failure;
}

코드를 보면 **Func()** 델리게이트를 통해 실제 행위를 전달할 것이기 때문에 **사용할 메소드들의 반환형은 INode.EnodeState이여야 합니다.**     마지막으로 아래와 같이 Update()에 BT를 실행해 주면 끝입니다

private void Awake()
{
    _BTRunner = new BehaviorTreeRunner(SettingBT());
}

private void Update()
{
    _BTRunner.Operate();
}

5. 결과

결과를 자세히 보기 위해 Gizmo를 넣어줍시다

private void OnDrawGizmos()
{
    // 탐지 거리
    Gizmos.color = Color.green;
    Gizmos.DrawWireSphere(this.transform.position, _detectRange);

    // 근접 공격 사거리
    Gizmos.color = Color.blue;
    Gizmos.DrawWireSphere(this.transform.position, _meleeAttackRange);
}

6. 전체 코드

BehaviorTree Runner

public class BehaviorTreeRunner
{
    INode _rootNode;
    public BehaviorTreeRunner(INode rootNode)
    {
        _rootNode = rootNode;
    }

    public void Operate()
    {
        _rootNode.Evaluate();
    }
}

EnemyAI

using System.Collections.Generic;
using UnityEngine;

[RequireComponent(typeof(Animator))]
public class EnemyAI : MonoBehaviour
{
    [Header("Range")]
    [SerializeField]
    float _detectRange = 10f;
    [SerializeField]
    float _meleeAttackRange = 5f;

    [Header("Movement")]
    [SerializeField]
    float _movementSpeed = 10f;

    Vector3 _originPos = default;
    BehaviorTreeRunner _BTRunner = null;
    Transform _detectedPlayer = null;
    Animator _animator = null;

    const string _ATTACK_ANIM_STATE_NAME = "Attack";
    const string _ATTACK_ANIM_TIRGGER_NAME = "attack";

    private void Awake()
    {
        _animator = GetComponent<Animator>();

        _BTRunner = new BehaviorTreeRunner(SettingBT());

        _originPos = transform.position;
    }

    private void Update()
    {
        _BTRunner.Operate();
    }

    INode SettingBT()
    {
        return new SelectorNode
            (
                new List<INode>()
                {
                    new SequenceNode
                    (
                        new List<INode>()
                        {
                            new ActionNode(CheckMeleeAttacking),
                            new ActionNode(CheckEnemyWithinMeleeAttackRange),
                            new ActionNode(DoMeleeAttack),
                        }
                    ),
                    new SequenceNode
                    (
                        new List<INode>()
                        {
                            new ActionNode(CheckDetectEnemy),
                            new ActionNode(MoveToDetectEnemy),
                        }
                    ),
                    new ActionNode(MoveToOriginPosition)
                }
            );
    }

    bool IsAnimationRunning(string stateName)
    {
        if(_animator != null)
        {
            if (_animator.GetCurrentAnimatorStateInfo(0).IsName(stateName))
            {
                var normalizedTime = _animator.GetCurrentAnimatorStateInfo(0).normalizedTime;

                return normalizedTime != 0 && normalizedTime < 1f;
            }
        }

        return false;
    }

    #region Attack Node
    INode.ENodeState CheckMeleeAttacking()
    {
        if (IsAnimationRunning(_ATTACK_ANIM_STATE_NAME))
        {
            return INode.ENodeState.ENS_Running;
        }

        return INode.ENodeState.ENS_Success;
    }

    INode.ENodeState CheckEnemyWithinMeleeAttackRange()
    {
        if (_detectedPlayer != null)
        {
            if (Vector3.SqrMagnitude(_detectedPlayer.position - transform.position) < (_meleeAttackRange * _meleeAttackRange))
            {
                return INode.ENodeState.ENS_Success;
            }
        }

        return INode.ENodeState.ENS_Failure;
    }

    INode.ENodeState DoMeleeAttack()
    {
        if (_detectedPlayer != null)
        {
            _animator.SetTrigger(_ATTACK_ANIM_TIRGGER_NAME);
            return INode.ENodeState.ENS_Success;
        }

        return INode.ENodeState.ENS_Failure;
    }
    #endregion

    #region Detect & Move Node
    INode.ENodeState CheckDetectEnemy()
    {
        var overlapColliders = Physics.OverlapSphere(transform.position, _detectRange, LayerMask.GetMask("Player"));

        if (overlapColliders != null && overlapColliders.Length > 0)
        {
            _detectedPlayer = overlapColliders[0].transform;

            return INode.ENodeState.ENS_Success;
        }

        _detectedPlayer = null;

        return INode.ENodeState.ENS_Failure;
    }

    INode.ENodeState MoveToDetectEnemy()
    {
        if (_detectedPlayer != null)
        {
            if (Vector3.SqrMagnitude(_detectedPlayer.position - transform.position) < (_meleeAttackRange * _meleeAttackRange))
            {
                return INode.ENodeState.ENS_Success;
            }

            transform.position = Vector3.MoveTowards(transform.position, _detectedPlayer.position, Time.deltaTime * _movementSpeed);

            return INode.ENodeState.ENS_Running;
        }

        return INode.ENodeState.ENS_Failure;
    }
    #endregion

    #region  Move Origin Pos Node
    INode.ENodeState MoveToOriginPosition()
    {
        if(Vector3.SqrMagnitude(_originPos - transform.position) < float.Epsilon * float.Epsilon)
        {
            return INode.ENodeState.ENS_Success;
        }
        else
        {
            transform.position = Vector3.MoveTowards(transform.position, _originPos, Time.deltaTime * _movementSpeed);
            return INode.ENodeState.ENS_Running;
        }
    }
    #endregion

    private void OnDrawGizmos()
    {
        Gizmos.color = Color.green;
        Gizmos.DrawWireSphere(this.transform.position, _detectRange);

        Gizmos.color = Color.blue;
        Gizmos.DrawWireSphere(this.transform.position, _meleeAttackRange);
    }
}

INode(interface)

public interface INode
{
    public enum ENodeState
    {
        ENS_Running,
        ENS_Success,
        ENS_Failure,
    }

    public ENodeState Evaluate();
}

Action Node

using System;

public sealed class ActionNode : INode
{
    Func<INode.ENodeState> _onUpdate = null;

    public ActionNode(Func<INode.ENodeState> onUpdate)
    {
        _onUpdate = onUpdate;
    }

    public INode.ENodeState Evaluate() => _onUpdate?.Invoke() ?? INode.ENodeState.ENS_Failure;
}

Selector Node

using System.Collections.Generic;

public sealed class SelectorNode : INode
{
    List<INode> _childs;

    public SelectorNode(List<INode> childs)
    {
        _childs = childs;
    }

    public INode.ENodeState Evaluate()
    {
        if (_childs == null)
            return INode.ENodeState.ENS_Failure;

        foreach (var child in _childs)
        {
            switch (child.Evaluate())
            {
                case INode.ENodeState.ENS_Running:
                    return INode.ENodeState.ENS_Running;
                case INode.ENodeState.ENS_Success:
                    return INode.ENodeState.ENS_Success;
            }
        }

        return INode.ENodeState.ENS_Failure;
    }
}

Sequence Node

using System.Collections.Generic;

public sealed class SequenceNode : INode
{
    List<INode> _childs;

    public SequenceNode(List<INode> childs)
    {
        _childs = childs;
    }

    public INode.ENodeState Evaluate()
    {
        if (_childs == null || _childs.Count == 0)
            return INode.ENodeState.ENS_Failure;

        foreach (var child in _childs)
        {
            switch (child.Evaluate())
            {
                case INode.ENodeState.ENS_Running:
                    return INode.ENodeState.ENS_Running;
                case INode.ENodeState.ENS_Success:
                    continue;
                case INode.ENodeState.ENS_Failure:
                    return INode.ENodeState.ENS_Failure;
            }
        }

        return INode.ENodeState.ENS_Success;
    }
}

---

참고 자료

Behavior tree (artificial intelligence, robotics and control) - Wikipedia