BehaviourTree

이준호·2023년 12월 29일
information
0
post-custom-banner

📌 Behaviour Tree

유한 상태 머신 (Finite State Machine) 이나 AI프로그래밍에 사용되는 기타 시스템과 달리 BT는 AI의 의사 결정 흐름을 제어하는 계층적인 노드 트리이다. Tree 범위에서 leaf(Action)은 AI 개체를 제어하는 실제 명령이고 가지를 형성하는 것은 상황에 가장 적합한 명령 시퀸스에 도달하기 위해 AI가 나무(Tree)따라 내려가는 것을 제어하는 다양한 유형의 유틸리티 노드이다.

➔ 탐색 순서

Behaviour Tree는 트리 구조이기 때문에, 위에서 아래로, 왼쪽에서 오른쪽 순으로 진행된다.

➔ 노드 구조

보통은 Leaf(Action), Selector, Sequence 3개의 노드를 기본적으로 가지고 있다.

➔ 노드 상태

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

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










📌 Node

➔ Leaf(Atcion Node)

Leaf(Action Node)는 나뭇잎, 트리의 끝 구조 즉, 행동을 정의한 노드 이다.

➔ Selector Node

  • or 연산자와 동일한 기능을 하는 노드이다.

  • 자식 노드들을 왼쪽에서 오른쪽 순으로 진행.

    • 우선순위가 높은 자식 노드일수록 왼쪽에 배치되어야 한다.
    • 자식 노드들 중에서 성공한 노드가 있다면 그 노드를 실행하고 종료한다.
    • 여기에서 성공이란, Success / Running을 뜻한다.

  • 여러 행동 중 하나만 실행해야 할 때 사용하기 좋다.

➔ Sequence Node

  • and 연산자와 동일한 기능을 한다.

  • 자식 노드들을 왼쪽에서 오른쪽 순으로 진행한다.
    - 먼저 진행해야 할 자식 노드가 왼쪽에 위치해야 한다.

    • 자식 노드들 중에서 실패(Failure)한 노드가 있을 때까지 진행한다.

  • 여러 행동을 순서대로 진행해야 할 때 사용하기 좋다.











📌 Node 구현 (C#)

➔ INode (interface)

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

public interface INode
{
    public enum ENodeState
    {
        ENS_Running, // 동작중
        ENS_Success, // 성공
        ENS_Failure  // 실패
    }

    public ENodeState Evaluate();
}

➔ Action(Leaf) Node

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

public sealed class ActionNode : INode // sealed : 다른 클래스에 상속하지 못하도록 한다.
{
    Func<INode.ENodeState> _onUpdate = null;    // Func : Atcion과 비슷하지만 차이점이 반환값이 있는 함수라는 것.

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

    public INode.ENodeState Evaluate() => _onUpdate?.Invoke() ?? INode.ENodeState.ENS_Failure; // ?? : 완쪽 값이 Null이라면 오른쪽 값으로 처리
}

➔ Selector Node

Selector Node는 자식 노드 중에서 처음으로 Success 또는 Running 상태를 가진 노드가 발생하면 그 노드까지 진행하고 멈춘다.

Evaluate() 메서드 구현은 아래와 같다.

  • 자식 상태 : Running일 때 ➔ Running 반환

  • 자식 상태 : Success일 때 ➔ Success 반환

  • 자식 상태 : Failure일 때 ➔ 다음 자식으로 이동

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

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

  • 자식 상태 : Running일 때 ➔ Running 반환

  • 자식 상태 : Success일 때 ➔ 다음 자식으로 이동

  • 자식 상태 : Failure일 때 ➔ Failure 반환

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_Failure;
    }
}

Sequence Node 주의점

Running 상태일 때는 그 상태를 유지해야 하기 때문에 다음 자식 노드로 이동하면 안 되고
다음 프레임 때도 그 자식에 대한 평가를 진행해야 한다.

예를 들어, Sequence Node에 적 발견(Detect), 이동(Move), 공격(Attack) 총 3개의 자식 노드가 있다고 가정해 본다면
프레임마다 노드에 진입하는 상황은 "N차"로 가정

  • 1차 : 적을 발견하고 적을 향해 이동한다.
  • 2차 : 발견한 적을 향해 아직 이동 중이다.
  • 3차 : 발견한 적을 향해 아직 이동 중이다.
  • 4차 : 이동이 완료되어 적을 공격한다.

만역 이 때, running에서 반환되지 않고 다음 자식 노드로 이동하게 된다면?
아직 적에게 다가가지 못했는데 적을 향해 공격하게 될 것이다.

그러므로, Running 상태에서는 Success와 다르게 다음 자식으로 이동하지 않고 Running을 반환해 줘서 다음 진입 시에도 Running 상태를 유지할 수 있도록 해주어야 한다.











📌 Unity로 Behaviour Tree 구현

➔ BehaviourTreeRunner Class

BT를 실행하기 위해서 BehaviourTreeRunner Class를 구현.

public class BehaviourTreeRunner
{
    INode _rootNode;

    public BehaviourTreeRunner(INode rootNode)
    {
        _rootNode = rootNode;
    }

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

➔ EnemyAI Class

BehaviourTreeRunner 생성자로 넘겨줄 INode 인스턴스를 위해 아래와 같이 SettingBT() 메소드를 구현

    protected INode SettingBT()
    {
        return new SelectorNode
            (
                new List<INode>()
                {
                    new SequenceNode
                    (
                        new List<INode>()
                        {
                            new ActionNode(CheckAttacking), // 공격중?
                            new ActionNode(CheckEnemyWithineAttackRange), // 공격 범위 안?
                            new ActionNode(DoAttack) // 공격
                        }
                    ),
                    new SequenceNode
                    (
                        new List<INode>()
                        {
                            new ActionNode(CheckDetectEnemy), // 적 발견?
                            new ActionNode(MoveToDetectEnemy) // 적한테 이동
                        }
                    ),
                    new ActionNode(MoveToOriginPosition) // 원래 자리로
                }
            );
    }

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

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를 실행해주면 된다.

    protected void Awake()
    {
        _BTRunner = new BehaviourTreeRunner(SettingBT());
        _animator = GetComponentInChildren<Animator>();
        _originPos = transform.position;
    }

    protected void Update()
    {
        _BTRunner.Operate();
    }
  • 결과를 자세히 보기 위한 Gizmo
private void OnDrawGizmos()
{
    // 탐지 거리
    Gizmos.color = Color.green;
    Gizmos.DrawWireSphere(this.transform.position, _detectRange);

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










📌 전체코드

➔ BehaviourTreeRunner.cs

// BT를 실행하기 위해서 BehaviourTreeRunner clsss 구현

public class BehaviourTreeRunner
{
    INode _rootNode;

    public BehaviourTreeRunner(INode rootNode)
    {
        _rootNode = rootNode;
    }

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

➔ EnemyAI.cs

➔ INode(Interface)

public class Enemy : MonoBehaviour
{
    // Distance
    [Header("Distnace")]
    [SerializeField]
    protected float _detectDistance;
    [SerializeField]
    protected float _attackDistance;

    // Movement
    [Header("Movement")]
    [SerializeField]
    protected float _movementSpeed;

    protected BehaviourTreeRunner _BTRunner = null;
    protected Transform _detectedPlayer = null;
    protected Vector3 _originPos = default;
    protected Animator _animator = null;

    protected const string _ATTACK_ANIM_STATE_NAME = "Attack";
    protected const string _ATTACK_ANIM_TIRGGER_NAME = "IsAttack";

    public Enemy()
    {
        this._detectDistance = 0;
        this._attackDistance = 0;
        this._movementSpeed = 0;
    }

    protected void Awake()
    {
        _BTRunner = new BehaviourTreeRunner(SettingBT());
        _animator = GetComponentInChildren<Animator>();
        _originPos = transform.position;
    }

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

    protected INode SettingBT()
    {
        return new SelectorNode
            (
                new List<INode>()
                {
                    new SequenceNode
                    (
                        new List<INode>()
                        {
                            new ActionNode(CheckAttacking), // 공격중?
                            new ActionNode(CheckEnemyWithineAttackRange), // 공격 범위 안?
                            new ActionNode(DoAttack) // 공격
                        }
                    ),
                    new SequenceNode
                    (
                        new List<INode>()
                        {
                            new ActionNode(CheckDetectEnemy), // 적 발견?
                            new ActionNode(MoveToDetectEnemy) // 적한테 이동
                        }
                    ),
                    new ActionNode(MoveToOriginPosition) // 원래 자리로
                }
            );
    }

    protected bool IsAnimationRunning(string stateName)
    {
        if (_animator != null)
        {
            if (_animator.GetCurrentAnimatorStateInfo(0).IsName(stateName)) // (stateName) 애니메이션이 진행중인가?
            {
                var normalizedTime = _animator.GetCurrentAnimatorStateInfo(0).normalizedTime;

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

        return false;
    }

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

        return INode.ENodeState.ENS_Success;
    }

    protected INode.ENodeState CheckEnemyWithineAttackRange()
    {
        if (_detectedPlayer != null)
        {
            if (Vector3.SqrMagnitude(_detectedPlayer.position - transform.position) < (_attackDistance * _attackDistance)) // 제곱근(피타고라스)
            {
                return INode.ENodeState.ENS_Success;
            }
        }

        return INode.ENodeState.ENS_Failure;
    }

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

        return INode.ENodeState.ENS_Failure;
    }
    #endregion

    #region Detect & Move Node
    protected INode.ENodeState CheckDetectEnemy()
    {
        // var overlapColliders = Physics.OverlapSphere(transform.position, _detectDistance, LayerMask.GetMask("Player")); // OverlapSphere : 구 형태로 "주변 콜라이더" 감지 <= 3D
        var overlapColliders = Physics2D.OverlapCircleAll(transform.position, _detectDistance, 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;
    }

    protected virtual INode.ENodeState MoveToDetectEnemy()
    {
        if (_detectedPlayer != null)
        {
/*          if (Vector3.SqrMagnitude(_detectedPlayer.position - transform.position) < (_attackDistance * _attackDistance))
            {
                transform.position = Vector3.MoveTowards(transform.position, -_detectedPlayer.position, Time.deltaTime * _movementSpeed);
                return INode.ENodeState.ENS_Running;
            }*/

            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 Position Node
    protected INode.ENodeState MoveToOriginPosition()
    {
        if (Vector3.SqrMagnitude(_originPos - transform.position) < float.Epsilon * float.Epsilon) // Epsilon : 수학에서 매우 작은 수를 의미하는 기호
        {
            return INode.ENodeState.ENS_Success;
        }
        else
        {
            transform.position = Vector3.MoveTowards(transform.position, _originPos, Time.deltaTime * _movementSpeed);
            return INode.ENodeState.ENS_Running;
        }
    }
    #endregion

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

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

➔ ActionNode.cs

// 실제로 어떤 행위를 하는 노드.
// Func() 델리게이트를 통해 행위를 전달 받아 실행.
public sealed class ActionNode : INode // sealed : 다른 클래스에 상속하지 못하도록 한다.
{
    Func<INode.ENodeState> _onUpdate = null;    // Func : Atcion과 비슷하지만 차이점이 반환값이 있는 함수라는 것.

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

    public INode.ENodeState Evaluate() => _onUpdate?.Invoke() ?? INode.ENodeState.ENS_Failure; // ?? : 완쪽 값이 Null이라면 오른쪽 값으로 처리
}

➔ SelectorNode.cs

// 자식 노드 중에서 처음으로 Succes나 Running상태를 가진 노드가 발생하면 그 노드까지 진행하고 멈춘다.
// Evaluate() 메서드의 구현
// 자식 상태 : Running일 때 -> Running 반환
// 자식 상태 : Success일 때 -> Success 반환
// 자식 상태 : Failure 때 -> 다음 자식으로 이동
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;
    }
}

➔ SequenceNode.cs

// 자식 노드를 왼쪽에서 오른쪽으로 진행하면서 Failure상태가 나올 때까지 진행하게 된다.
// Evaluate() 메소드 구현
// 자식 상태 : Running일 때 -> Running 반환
// 자식 상태 : Success일 때 -> 다음 자식으로 이동
// 자식 상태 : Failure일 때 -> Failure 반환

// 주의할 점 : Running상태일 때, 그 상태를 계속 유지해야 하기 때문에 다음 자식 노드로 이동하면 안 되고
// 다음 프레임 때도 그 자식에 대한 평가를 진행해야 한다.
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_Failure;
    }
}

➔ FarEnemy.cs

public class FarEnemyAI : Enemy
{
    public FarEnemyAI() : base()
    {
        this._detectDistance = 7;
        this._attackDistance = 4;
        this._movementSpeed = 2;
    }


    protected override INode.ENodeState MoveToDetectEnemy()
    {
        if (_detectedPlayer != null)
        {
            if (Vector3.SqrMagnitude(_detectedPlayer.position - transform.position) < (_attackDistance * _attackDistance))
            {
                return INode.ENodeState.ENS_Running;
            }
            // (수정필요) 플레이어 위치 + 사정거리 포지션으로 이동해야함 (플레이어 위치로 이동하는게 아니라)

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

            return INode.ENodeState.ENS_Running;
        }

        return INode.ENodeState.ENS_Failure;
    }
}

➔ NearEnemy.cs

public sealed class NearEnemyAI : Enemy
{
    public NearEnemyAI() : base()
    {
        this._detectDistance = 4;
        this._attackDistance = 1;
        this._movementSpeed = 3;
    }
}










📌 출저

Night's Devlog

AI의 행동 트리:작동방식

profile
이준호
No Easy Day
이전 포스트

클래스, 구조체, 제네릭, 인터페이스

다음 포스트

AI (노드, A*, 휴리스틱, NavMesh)

post-custom-banner

0개의 댓글