[ 게임이론 ] AI 캐릭터 구현 Behavior Tree(행동트리)

행동 트리란?

게임 AI에서 널리 사용되는 트리기반의 의사결정 구조, AI캐릭터가 순서,조건에 따라 어떤 행동을 할지 처리합니다.

 

기본 구조

• 루트(root): 트리의 시작점
• 컴포지트 노드(Composite): 자식 노드를 여러개 가짐
  • Selector: 자식이 하나라도 성공하면 성공 (OR)
  • Sequence: 자식이 모두 성공해야 성공(AND)
• 데코레이터 노드(Decorator): 한 개의 자식을 감싸 조건을 붙임
  • repeat, Inverter, UntilFail
• 리프 노드(Leaf)
  • Action: 실제 행동 수행(공격, 이동 등)
  • condition: 조건 평가

노드의 반환에는 Success, Run, Fail로

• Success: 조건에 해당하여 해당 노드의 코드 실행
• Run: 노드 실행중
• Fail: 조건에 실패하여 실패 반환

 

예시 실행 흐름

root에서 시작하여 깊이 우선 탐색(DFS)으로 탐색하며

Selector에서는 시퀀스 노드가 추가되있으므로 해당 노드를 탐색하러갑니다.

탐색 순위에 따라 왼쪽 노드를 먼저 방문하며 해당 노드에서 3가지 반환이 무엇인지에 따라 오른쪽 액션노드를 탐색할지 정합니다.

Success를 반환시켜 Run중이라면 오른쪽 액션노드를 가지 않고, Fail을 반환했다면 넘어가서 똑같이 검사를 수행합니다.

---

트리의 추상클래스

public enum ESTATE
{
    RUN, SUCCESS, FAILED
}

public abstract class ENode
{
    protected ESTATE currentEState;

    //현재의 노드상태를 평가하고 실행하거나 제어하는 역할
    public abstract ESTATE Evaluate(); //행동 반환 메소드

}

 

Enum으로 노드의 현재 상태를 Run, Success, Failed로 반환하도록 하고,

ENode를 추상클래스로 하여, 현재 노드의 상태, 행동을 반환할 메소드를 선언합니다.

 

Sequence노드 클래스

/*
 * 시퀀스는 셀럭터 내에서 순찰내에서 탐지범위체크, 타겟설정 행동에 대한 노드
 */

public class SequenceNode : ENode
{
    //N개의 자식 노드들
    private List<ENode> children;

    public SequenceNode(List<ENode> children) //생성자
    {
        this.children = children;
    }

    //모든 자식이 성공해야 성공으로 간주한다.
    public override ESTATE Evaluate()
    {
       foreach (var child in children) //자식 노드를 순회
        {
            switch (child.Evaluate()){ //자식 노드의 상태를 파악한다.
                case ESTATE.SUCCESS: //success면 다른 자식을 검사하러 다시 foreach로
                    continue;
                case ESTATE.RUN:
                    return ESTATE.RUN;
                case ESTATE.FAILED:
                    return ESTATE.FAILED;
            }
        }

       //Failed에 걸리지 않고 빠져나왔으므로 Success
       return currentEState = ESTATE.SUCCESS; ; //모두 성공해야 SUCCESS반환
    }
}

 

시퀀스 노드와 셀렉터는 여러 노드를 가지는 노드이므로 생성자에 자식 노드들을 리스트로 받아 생성하도록 합니다.

Evaluate() 노드에서는 자식 노드들을 순회하여 자식노드들에 있는 해당 메소드를 실행하여 반환타입을 결정합니다.

Success를 반환하면 현재 노드를 실행중으로 넘기기위해 Continue로 Run을 반환시킵니다.

이렇게 Failed에 걸리지 않고 모두 통과하면 메소드에서는 모든 자식 노드가 Filed에 걸리지 않았을때 Sucess 상태를 반환합니다.

 

Selector노드 클래스

/*
 * Selector는 순찰 접근 공격 행동에 해당하는 노드
 */
public class SelectorNode : ENode
{
    protected List<ENode> children; //N개의 자식 노드

    public SelectorNode(List<ENode> children)
    {
        this.children = children;
    }


    //셀럭터 노드는 하나라도 성공자식이 있으면 성공으로 간주한다.
    public override ESTATE Evaluate()
    {
        foreach (var child in children) //자식 노드를 순회
        {
            switch(child.Evaluate()){
                case ESTATE.SUCCESS:
                    currentEState = ESTATE.SUCCESS;
                    return ESTATE.SUCCESS;
                case ESTATE.RUN:
                    currentEState = ESTATE.RUN;
                    return ESTATE.RUN;
                default:
                    continue;
            }
        }

        return currentEState = ESTATE.FAILED; //하나라도 실패하면 Failed반환
    }
}

 

Selector도 시퀀스와 비슷하지만 다른점은 자식노드가 Success를 반환하면 그 즉시 리턴시켜 성공으로 간주시킵니다.

 

Action노드 클래스

/*
 * 액션은 말단노드(자식 노드가 없음)로 부모노드들에 행동을 하겠다고 반환해줄 노드
 * 행동을 수행할 노드
 */

public class ActionNode : ENode
{
    //ESTATE 반환 델리게이트
    public delegate ESTATE ActionNodeDelegate();

    private ActionNodeDelegate action; //다음에 할 행동

    public ActionNode (ActionNodeDelegate action) //행동을 결정하는 생성자, 델리게이트 매개변수
    {
        this.action = action;
    }

    public override ESTATE Evaluate()
    {
        currentEState = action(); // 행동 실행 후 결과 저장
        return currentEState;
    }

}

 

액션 노드에는 델리게이트를 통해 외부에서 정의한 행동 메소드를 받아서 이 노드가 실행되도록 합니다. 그럼 외부의 메소드에서 반환값을 받게하여 해당 상태가 현재 노드의 상태가 되도록 합니다.

---

셀렉터와 시퀀스의 차이점

	Selector	Sequence
차이점	하나라도 Success를 반환하면 성공반환, 모두 실패를 반환해야 실패	하나라도 Failed를 반환하면 실패 반환, 모두 성공을 반환해야 성공
공통점	하나라도 Running 이면 전체가 Running

 

주의점

Selector는 Sequence보다 부모 노드로 쓰이는게 좋다.

이유: bh트리는 우선 순위 기반으로 의사결정을 합니다. 만약 Selector가 자식이고 Sequence가 부모인 노드일 경우,
자식인 Selector에서 하나라도 성공을 반환할경우 부모인 Sequence는 자식인노드의 자식들이 모두 성공했구나 라고 판단해버려서 조건에 맞지 않는데도 모두 성공으로 간주해버려 다음 노드로 넘어가버릴 수 있습니다.

 

행동트리 구조

  protected override void SetupTree()
  {
      // 탐지 트리
      ENode detectTree = new SelectorNode(new List<ENode> {
          new ActionNode(CheckDetectRange)
      });

      // 이동 트리
      ENode moveTree = new SelectorNode(new List<ENode> {
          new ActionNode(MoveToPlayer)
      });

      // 공격 트리
      ENode attackTree = new SequenceNode(new List<ENode> {
          new ActionNode(CheckAttackRange),
          new ActionNode(NormalAttack)
      });

      // 전체 트리 구성
      behaviorTree = new SequenceNode(new List<ENode> {
          detectTree, moveTree, attackTree
      });
  }

 

제가 만든 적 bh트리 입니다.

탐지, 이동, 공격 순으로 노드를 구성했습니다.

사실 코드로는 탐지랑 이동에는 셀렉터노드에 넣지 않아도 되는데 흘러가는걸 보고싶어서 넣었습니다.

탐지에서 Success를 반환해야 이동으로 갈 수 있고, 이동에서도 Success를 반환해야 공격으로 넘어갈 수 있습니다.

공격에서는 공격범위에 들어오면 공격을 수행하도록 앞으로 우선배치해서 넣었습니다.

 

언리얼에는 이 행동트리가 블랙보드로 있다는데 유니티에는 직접 구현해야 합니다.