자료구조 <행동 트리(Behavior Tree) 기반의 AI 구현하기>

행동트리(Behavior Tree) 정의하기

 

행동트리(Behavior Tree)란?

 

트리 기반의 모델로 게임 내에서 AI 혹은 대화 시스템 등 다양한 분야에서 사용이 가능합니다. 

 

행동 트리를 이루는 노드는 루트 노드를 제외하고 셀렉터(Selector), 시퀀스(Sequence), 액션(Action) 세 종류의 노드들로 구성되어 있으며 각 노드들은 저마다의 규칙을 가지고 있습니다. 또한 가장 왼쪽노드를 우선으로 처리합니다.

 

세 종류의 노드는 공통적으로 성공, 실패, 진행중 상태를 갖습니다. 그리고 행동의 결과가 어떤 상태인지 평가하여 반환하는 메서드가 존재합니다. 

 

• Action 노드 : Excution 노드 라고도 하며 리프 노드로 자식을 가지지 않습니다. Aciont 노드는 행동 트리에서 해당 행동에 대한 구체적인 함수를 호출합니다.
• Selector 노드 : fallback 노드 라고도 하며 자식 노드들을 왼쪽 부터 차례로 결과들을 평가했을 때 하나라도 성공상태인 자식이 있으면 그 Selector 노드는 성공으로 간주합니다.
• Sequence 노드 : 일련의 순서를 표현하는 노드로 자식 노드들은 왼쪽부터 해당 시퀀스 노드가 수행하고자 하는 일의 순서가 됩니다. 순서를 수행하던 도중 하나라도 실패하게되면 일을 그르치게 되는 것이므로 시퀀스 노드는 모든 자식노드가 성공 상태가 되었을 때 성공한 것으로 간주합니다. 

 

행동 트리의 구체적인 예시

 

위 사진에서 Root 는 말그대로 루트 노드입니다. 그 자식으로는 적의 행동 양식이라는 셀렉터가 있습니다. 

셀렉터 이므로 그 자식 노드들은 공격 시퀀스, 탐지 시퀀스, 귀환 액션, 대기 액션 노드들 중 하나라도 성공이면 적 행동 양식 셀렉터는 성공으로 간주합니다.

 

행동 트리는 왼쪽에서 오른쪽으로 행동을 수행합니다. 따라서 가장 먼저 검사할 노드는 공격 시퀀스가 됩니다. 

공격 시퀀스는 다시 공격 범위 체크 액션과 공격 방식 셀렉터 노드를 자식으로 갖습니다. 두 노드중 하나라도 실패이면 공격 시퀀스 노드는 실패이고 다음 노드인 탐지 시퀀스 노드로 넘어갑니다. 

 

탐지 시퀀스 노드도 마찬가지로 탐지 범위 체크 액션과 타겟 설정 셀렉터, 추격하기 액션을 자식으로 가집니다. 시퀀스 노드이기에 세 노드들이 전부 성공해야 탐지 시퀀스도 성공으로 간주합니다. 

 

만약 공격, 탐지가 모두 실패했다면 범위 내에 공격 대상이 없으므로 귀환하기 액션을 수행합니다. 그리고 귀환하기 액션이 끝나게 되면 대기하기 액션을 수행합니다. 

 

코드로 구현해보기

 

앞서 소개한 예시를 바탕으로 코드를 작성해보겠습니다. 작성된 언어는 Unity C# 입니다.

 

먼저, 트리를 구성할 노드부터 만듭니다. 

 

public interface INode
{
    public enum STATE
    { RUN, SUCCESS, FAILED }

    public INode.STATE Evaluate(); // 판단하여 상태 리턴
}

 

모든 노드는 공통적으로 성공, 실패, 실행중 상태를 갖습니다. 또한 성공인지 실패인지 평가하는 메서드도 공통으로 가집니다. 이를 인터페이스로 추상화하였습니다. 

 

public class ActionNode : INode
{
    public Func<INode.STATE> action; // 반환형이 INode.STATE 인 대리자

    public ActionNode(Func<INode.STATE> action) // 노드를 생성할 때 매개변수로 대리자를 받음(지정자)
    {
        this.action = action;
    }

    public INode.STATE Evaluate() 
    {
        // 대리자가 null 이 아닐 때 호출, null 인 경우 Failed 반환
        return action?.Invoke() ?? INode.STATE.FAILED;
    }
}

 

INode  인터페이스를 상속받는 Action 노드입니다. Action 노드는 트리 외부의 함수를 매개변수로 받아 대신 호출합니다.

 

public class SelectorNode : INode
{
    List<INode> children; // 여러 노드를 가질 수 있도록 리스트 생성

    public SelectorNode() { children = new List<INode>(); }

    public void Add(INode node) { children.Add(node); } // 셀렉터에 자식노드를 추가하는 메서드

    public INode.STATE Evaluate()
    {
        // 리스트 내의 노드들을 왼쪽부터(넣은 순으로) 검사
        foreach (INode child in children)
        {
            
            INode.STATE state = child.Evaluate();
            // child 노드의 state 가 하나라도 SUCCESS 이면 성공을 반환
            // 실행 중인 경우 RUN 반환
            switch (state)
            {
                case INode.STATE.SUCCESS:
                    return INode.STATE.SUCCESS;
                case INode.STATE.RUN:
                    return INode.STATE.RUN;
            }
        }
        // 반복문이 끝났다면 해당 셀렉터의 자식노드들은 전부 FAILED 상태이므로 셀렉터는 FAILED 반환
        return INode.STATE.FAILED;
    }
}

 

다음으로는 INode 인터페이스를 상속받는 셀렉터 노드입니다. 셀렉터 노드는 자식 노드들의 성공 여부를 검사하여 하나라도 성공이라면 성공을 반환합니다. 

 

public class SequenceNode : INode
{
    List<INode> children; // 자식 노드들을 담을 수 있는 리스트

    public SequenceNode() { children = new List<INode>(); }

    public void Add(INode node) { children.Add(node); }

    public INode.STATE Evaluate()
    {
        // 자식 노드의 수가 0 이하라면 실패
        if (children.Count <= 0)
            return INode.STATE.FAILED;

        foreach (INode child in children)
        {
            // 자식 노드들중 하나라도 FAILED 라면 시퀀스는 FAILED
            switch (child.Evaluate())
            {
                case INode.STATE.RUN:
                    return INode.STATE.RUN;
                // SUCCESS 이면 아래는 검사하지 않고 continue 키워드로 다시 반복문 호출
                case INode.STATE.SUCCESS:
                    continue;
                case INode.STATE.FAILED:
                    return INode.STATE.FAILED;
            }
        }
        // FAILED 에 걸리지 않고 반복문을 빠져나왔으므로 시퀀스는 SUCCESS
        return INode.STATE.SUCCESS;
    }
}

 

시퀀스 노드는 모든 자식노드들이 실패하지 않아야 성공으로 간주합니다. 

 

이제 적 스크립트를 만들어보겠습니다. 

 

public class Enemy : MonoBehaviour
{
    SelectorNode rootNode; // 루트 노드는 셀렉터노드
    SequenceNode attackSequence; // 공격 시퀀스 노드
    SequenceNode detectiveSequence; // 탐지 시퀀스 노드
    ActionNode idleAction; // 대기 액션 노드
    ActionNode returnAction; // 귀환 노드
    
    Transform target; // 타겟 변수
    public int detectiveRange; // 탐지 범위 변수
    public int attackRange; // 공격 범위 변수
    Vector3 originPos; // 초기 위치를 저장하는 변수

    void Start()
    {
        originPos = transform.position;
        
        // 루트 노드 생성
        rootNode = new SelectorNode();
        rootNode.Add(attackSequence); // 루트 노드의 자식으로 공격 시퀀스
        rootNode.Add(detectiveSequence); // 탐지 시퀀스
        rootNode.Add(returnAction); // 귀환 시퀀스
        rootNode.Add(idleAction); // 대기 시퀀스를 가진다.
    }

	// 업데이트 내에서는 루트 노드(행동 트리 전체)의 상태를 평가한다.
    void Update()
    {
        rootNode.Evaluate();
    }

}

 

이렇게 작성하면 이제 루트 노드의 자식이 생성됩니다. 하지만 아직 공격 시퀀스, 탐지 시퀀스, 귀환, 대기에 구체적인 함수를 할당하지 않았습니다. 바로 아래와 같은 상태입니다. 

 

자, 이제 여기서 공격 시퀀스 부터 하나씩 자식 노드를 추가하고 액션 노드에 함수를 할당해보겠습니다. 

 

public class Enemy : MonoBehaviour
{
    SelectorNode rootNode; // 루트 노드는 셀렉터노드
    SequenceNode attackSequence; // 공격 시퀀스 노드
    SequenceNode detectiveSequence; // 탐지 시퀀스 노드
    ActionNode idleAction; // 대기 액션 노드
    ActionNode returnAction; // 귀환 노드
    
    Transform target; // 타겟 변수
    public int detectiveRange; // 탐지 범위 변수
    public int attackRange; // 공격 범위 변수
    Vector3 originPos; // 초기 위치를 저장하는 변수

    void Start()
    {
        originPos = transform.position;
        
        attackSequence = new SequenceNode(); // 공격 시퀀스 노드 생성
        attackSequence.Add(new ActionNode(CheckInAttackRange)); // 공격 범위 체크 액션노드에 함수 할당
        attackSequence.Add(new ActionNode(Attack)); // 공격 액션 노드에 함수 할당
        
        // 루트 노드 생성
        rootNode = new SelectorNode();
        rootNode.Add(attackSequence); // 루트 노드의 자식으로 공격 시퀀스
        rootNode.Add(detectiveSequence); // 탐지 시퀀스
        rootNode.Add(returnAction); // 귀환 시퀀스
        rootNode.Add(idleAction); // 대기 시퀀스를 가진다.
    }
    
    INode.STATE Attack() // 공격 액션에 할당될 함수
    {
        Debug.Log("공격중");
        return INode.STATE.RUN;
    }

    INode.STATE CheckInAttackRange() // 공격 범위 체크 액션에 할당될 함수
    {
        if (target == null)
            return INode.STATE.FAILED;
        if (Vector3.Distance(transform.position, target.position) < attackRange)
        {
            Debug.Log("공격 범위 감지 됨");
            return INode.STATE.SUCCESS;
        }
        return INode.STATE.FAILED;
    }

	// 업데이트 내에서는 루트 노드(행동 트리 전체)의 상태를 평가한다.
    void Update()
    {
        rootNode.Evaluate();
    }

}

 

 

다른 자식 노드들도 추가하여 할당해보겠습니다. 

 

public class Enemy : MonoBehaviour
{
    public int detectiveRange;
    public int attackRange;

    SelectorNode rootNode;
    SequenceNode attackSequence;
    SequenceNode detectiveSequence;
    ActionNode idleAction;
    ActionNode returnAction;
    Transform target;

    Vector3 originPos;


    // Start is called before the first frame update
    void Start()
    {
        originPos = transform.position;

        attackSequence = new SequenceNode();
        attackSequence.Add(new ActionNode(CheckInAttackRange));
        attackSequence.Add(new ActionNode(Attack));

        detectiveSequence = new SequenceNode(); // 탐지 시퀀스
        detectiveSequence.Add(new ActionNode(CheckInDetectiveRange)); // 탐지 체크 액션
        detectiveSequence.Add(new ActionNode(TraceTarget)); // 쫓기 액션
        
        returnAction = new ActionNode(ReturnAction); // 귀환 액션 노드
        idleAction = new ActionNode(IdleAction); // 대기 액션노드
        

        rootNode = new SelectorNode();
        rootNode.Add(attackSequence);
        rootNode.Add(detectiveSequence);
        rootNode.Add(returnAction);
        rootNode.Add(idleAction);
    }


    INode.STATE Attack()
    {
        Debug.Log("공격중");
        return INode.STATE.RUN;
    }

    INode.STATE CheckInAttackRange()
    {
        if (target == null)
            return INode.STATE.FAILED;
        if (Vector3.Distance(transform.position, target.position) < attackRange)
        {
            Debug.Log("공격 범위 감지 됨");
            return INode.STATE.SUCCESS;
        }
        return INode.STATE.FAILED;
    }

    INode.STATE TraceTarget()
    {
        if (Vector3.Distance(transform.position, target.position) >= 0.1f)
        {
            Debug.Log("Trace!!");
            transform.forward = (target.position - transform.position).normalized;
            transform.Translate(Vector3.forward * Time.deltaTime, Space.Self);
            return INode.STATE.RUN;
        }
        else
            return INode.STATE.FAILED;
    }

    INode.STATE IdleAction()
    {
        Debug.Log("Idle..");
        return INode.STATE.RUN;
    }
    INode.STATE ReturnAction()
    {
        if (Vector3.Distance(transform.position, originPos) >= 0.1f)
        {
            Debug.Log("Return..");
            transform.forward = (originPos - transform.position).normalized;
            transform.Translate(Vector3.forward * Time.deltaTime, Space.Self);
            return INode.STATE.RUN;
        }
        else
            return INode.STATE.FAILED;
    }

    INode.STATE CheckInDetectiveRange()
    {
        Collider[] cols = Physics.OverlapSphere(transform.position, detectiveRange, 1 << 8);
        if (cols.Length > 0)
        {
            Debug.Log("Detective..");
            target = cols[0].transform;
            return INode.STATE.SUCCESS;
        }

        return INode.STATE.FAILED;
    }

    // Update is called once per frame
    void Update()
    {
        rootNode.Evaluate();
    }

    private void OnDrawGizmos()
    {
        Gizmos.color = Color.yellow;
        Gizmos.DrawWireSphere(transform.position, detectiveRange);
        Gizmos.color = Color.red;
        Gizmos.DrawWireSphere(transform.position, attackRange);
    }



}

 

다음과 같이 작성할 수 있으며 유니티에서 실행시 Enemy 스크립트를 가진 오브젝트와 Player 레이어를 가진 오브젝트 끼리 상호 작용이 가능합니다. 

 

여기까지 작성하면 맨 처음 사진에서 여기까지 구현한 것이 됩니다. 

 

마무리

 

위 코드에서는 공격 방식 셀렉터와 타겟 설정 셀렉터를 따로 작성하지 않았습니다. 행동 트리와 예시 코드가 충분히 이해 된다면 직접 작성해보는 것도 좋을 것 같습니다.