Behavior Tree 개념 및 동작

개요

---

이 문서는 Beahvior Tree( 이하 BT ) 의 세부적인 구현이나 노드들에서 다루기 위해서 작성된 것이 아니라 전반적인 개념 및 흐름을 정리하기 위해서 작성되었습니다. 그러므로 BT 의 세부적인 동작 방식들에 대해 알고 싶으시다면 가마수트라의 [ Behavior trees for AI: How they work ][ 4 ] 를 읽어 보시기 바랍니다( 하지만 안타깝게도 영문입니다 ).

개념

---

BT 를 이야기하기 위해서는 유한 상태 기계( Finite State Machines, 이하 FSM )에 대해서 언급하지 않고 넘어 갈 수 없습니다. 

FSM 은 특정 유형의 로직을 제공합니다. 이는 상태( state )와 전이( transition )으로 구성됩니다. 상태는 동시에 실행되는 행동( action )의 집합입니다. 행동의 예를 들면 애니메이션, 사운드, 특정 시간동안 대기 등을 들 수 있습니다. 전이는 조건( condition )을 포함합니다. 전이의 조건이 충족되면, 상태는 다른 상태로 이동하게 됩니다.

게임에서 이러한 FSM 은 애니메이션 상태를 전환하는 데 많이 사용됩니다. 이러한 FSM 의 한 예는 Unity3D 의 메카님 스테이트 머신( Mechanim State Machine )입니다. 이것을 사용하면 한 애니메이션에서 다른 애니메이션으로 전환되는 로직을 쉽게 작성할 수 있습니다[ 5 ].

출처 : [ 4 ]

게다가 비주얼 디버깅( visual debugging )도 매우 쉽습니다. 현재 상태를 보여주기 때문입니다.

출처 : [ 5 ]

하지만 이러한 상태들이 매우 많아지게 되면 노드가 매우 복잡해집니다.  

그렇기 때문에 상태를 계층화( 혹은 그룹화)하는 계층적 유한 상태 기계( Hierarchical Finite State Machines, 이하 HFSM )라는 개념이 등장했습니다[ 3 ].

출처 : [ 3 ]

FSM 은 서로 다른 문맥을 가진 로직을 재사용할 수 있는 방법을 제공하지 않지만, HFSM 은 FSM 들을 그룹화하고 계층화함으로써 특정 문맥을 가진 상태를 재사용할 수 있게 해 줍니다. 그리고 FSM 이 그렇듯이 현재의 문맥( 상위 상태 )을 파악하기도 쉽습니다. 그래서 최근까지 게임 AI 에서 많이 사용되던 방식입니다.

그런데 이 HFSM 도 문제가 있습니다. HFSM 이 어느 정도의 확장성을 가지기는 하지만, ( 하위 ) 상태를 모듈화하는 기능을 제공하지는 않습니다. 예를 들어 같은 상태를 다른 문맥에서 사용할 수는 없습니다. 왜냐하면 특정 상태에서 전이되어야 한다는 조건이 붙어 있기 때문입니다.

좀 더 실용적인 예를 들어 보도록 하겠습니다. 여러분이 "걷기" 상태를 가지고 있다고 합시다. "걷기" 상태는 "전투" 상태의 하위 상태도 될 수 있지만, "추적" 상태의 하위 상태도 될 수 있습니다. 만약 HFSM 을 사용한다면 "전투" 상태에 "걷기" 상태를 추가하고, "추적" 상태에도 "걷기" 상태를 추가해야 합니다. 물론 각 문맥에서의 ( "걷기" 상태로의 ) 전이 조건은 서로 다르겠죠.

그래서 같은 상태를 재작성하지 않고도 다른 목적이나 상황에 따라 상태를 재사용할 수 있도록 하기 위한 목적을 가지고 행동트리( Behavior Tree )라는 것이 생겨났습니다[ 1 ].

BT 는 로직을 캡슐화함으로써 상태의 모듈성을 증가시킵니다. 예를 들면 내포된 상태( 하위 상태 )를 만드는 것이죠. 이는 HFSM 에서도 제공하고 있습니다만, 전이라는 것이 존재하지 않는다는 차이점을 가집니다. 그래서 상태는 그 자체로서 존재할 수 있습니다.

출처 : [ 1 ]

Behaviour Tree 작동 원리

---

이 부분은 자료구조에 대한 이해가 필요합니다. 일반적으로 BT 를 구현하기 위해서는 스택( Stack )이라는 자료구조를 사용하게 됩니다. 이것은 전형적인 후입선출( Last In First Out ) 방식의 자료구조입니다. 이를 간단하게 도식화하면 다음과 같습니다.

출처 : [ 6 ]

스택에 대해서 언급한 이유는 나중에 언급할 BT 노드들이 동작하는 방식을 이해하는 기반이 되기 때문입니다.

BT 는 태스크( Task ) 집합으로 구성됩니다. FSM 류에서는 행동 집합을 상태라고 하고 상태가 다른 상태로 넘어 갈 수 있는 방향 및 조건을 지정하는 것을 전이라 표현했습니다. 하지만 BT 에서는 모든 것을 노드로 표현합니다.

BT 구현에 따라서 조금씩 다르지만 태스크의 종류는 크게 Composite, Decorator, Condition, Action 으로 나뉩니다. Action 은 단말 태스크로서 FSM 의 행동 집합으로써의 상태에 가깝다고 보시면 됩니다. 보통 태스크와 노드( node )라는 용어를 같은 의미로 사용하는 경우가 많으므로 헷갈리지 않기를 바랍니다.

Action task

Action task 는 실제 행동을 표현하는 단말 노드입니다. 이것은 항상 true 나 false 를 반환하게 되어 있습니다. 일반적으로는 Action.OnStart(), Action.OnUpdate(), Action.OnEnd() 같은 메서드를 가지고 있는데, Action.OnUpdate() 에서 true 나 false 를 반환하면 그 Action 의 작업이 끝납니다. 메서드의 이름은 구현마다 다를 수 있습니다.

스택에 처음 올라갈 때 OnStart() 가 불리고, true 나 false 를 반환하지 않으면 계속해서 OnUpdate() 가 불립니다. 그러다가 true 나 false 가 반환되면 스택에서 빠지면서 OnEnd() 가 불립니다. 어떤 구현들( UE4, ParadoxNotations 의 NodeCanvas 등 )에서는 EndAction() 과 같은 메서드를 명시적으로 호출해서 Action 을 끝내기도 하고, 어떤 구현들( BehaviorDesigner 등 )에서는 true, false, running 과 같은 반환값을 기반으로 Action 이 끝났는지 판단하기도 합니다.

Composite task

Composite task 는 우리말로 하면 복합 태스크입니다. 이것은 말 그대로 ( 하나 이상의 ) 여러 개의 자식으로 구성된 태스크입니다. 자주 사용되는 Composite 으로는 Select, Sequence 등이 있습니다. 이러한 Composite 의 핵심 용도는 node 의 flow 를 제어하는 것입니다.

기본적으로 node 의 실행 순서는 위에서 아래로, 왼쪽에서 오른쪽으로입니다.

Select composite 은 자식 노드가 true 를 반환할 때까지 자식 노드들을 실행합니다. 말 그대로 하나를 선택하는 것이죠. 참고로 스샷은 ParadoxNotations 의 NodeCanvas 의 스샷입니다.

위의 Select 를 스택 구조로 도식화하면 다음과 같습니다. 그림이 복잡해지는 것을 방지하기 위해서, OnStart() 에서 바로 EndAction() 을 호출했다고 가정합니다.

다른 것들도 마찬가지로 동작하므로 스택 구조로 도식화하는 것은 여기까지만 하도록 하겠습니다. 

Sequence composite 는 자식 노드가 false 를 반환할 때까지 자식 노드들을 실행합니다. 말 그대로 순차적 실행입니다.

이것들을 잘 조합하면 다양한 로직을 구성할 수 있습니다.

Conditional Aborts

BT 의 단말 노드에 존재하는 Action 이 true 나 false 를 반환하지 않으면 계속해서 그 작업에 머물러 있게 됩니다. 그 Action 의 OnUpdate() 메서드 내부에서 종료 조건을 판단할 수 있으면 좋겠지만 외부에서 강제적으로 그 Action 의 실행을 중단시키고 싶을 수 있습니다. 

예를 들어 "추적" 이라는 Action 은 일반적으로 내부에서 추적이 완료되었는지 여부를 판단하고 있을 것입니다. 예외적인 조건 판단까지 그 Action 에 넣어 버리면 너무 복잡해지고, 다른 Action 에 대한 종속성을 가지게 될 것입니다. 이럴 경우에 "추적" Action 을 취소시킬 수 있는 방법이 있다면 좋을 것입니다. 그런 방법을 조건부 취소( Conditional Aborts )라 부릅니다. 어떤 구현에서는 평가를 재활성화한다( Reactive Evaluation )고 합니다.

조건부 취소는 실행 흐름에 영향을 주게 되므로 Composite 에 기능이 내장되어 있습니다. 어떤 변수를 계속 감시하고 있다가 변수의 값이 바뀌게 되면 지금의 실행 흐름을 취소시키고 자신의 노드로부터 재평가를 하는 것입니다. 

Conditional Aborts 는 보통 Self, Lower Priority, Both 로 이루어집니다. Self 는 자신의 하위에 있는 태스크를 취소시키는 것이고, Lower Priority 는 자신의 오른쪽에 있는 이웃 노드의 흐름을 취소시키는 것입니다. 그리고 Both 는 Self + Lower Priority 입니다. 여기에서 Lower Priority 라는 의미를 이해하기 힘든 분이 있을 수 있습니다. Lower 라는 이름이 붙은 이유는 BT 의 실행 흐름이 왼쪽에서 오른쪽으로 이어지기 때문입니다.

간단한 예를 들어 보도록 하겠습니다. 일단 NodeCanvas 의 경우에는 Composite 에 Dynamic 이라는 속성이 있습니다. 이것은 Conditional aborts on Self 를 의미합니다. UE4 나 BehaviorDesigner 는 Self, Lower Priority, Both 를 모두 가지고 있습니다. 어쨌든 계속해서 실행되는 어떤 Action 이 있다고 합시다. 아래 BT 에서는 "B" Action 을 실행한 후에 "Run Forever" 라는 Action 으로 제어가 넘어 갔기 때문에, "B" Action 은 앞으로 절대로 평가되지 않습니다.

그런데 특정 조건이 만족되면 다시 Sequece Composite 를 평가하고 싶다면 어떻게 해야 할까요? 이럴 때 Sequencer 노드를 dynamic 으로 변경하고, 하위에 Condition 노드를 추가해 Conditional Aborts 상황을 만들 수 있습니다. 형태는 다음과 같습니다.

이제 Cancel 이라는 변수에 false 를 할당하면, Sequencer 노드가 이를 감시하고 있다가 "Run Forever" Action 을 취소하고 다시 자신의 노드를 평가합니다. 참고로 취소될 때는 "Run Forever" 의 OnEnd() 가 호출됩니다.

여기에서 "Sequencer 가 첫 번째 노드에서 false 를 반환해서 멈춰버리네?" 라는 의문을 가지는 분이 계실 겁니다. 이런 사태에 대비해서 모든 Action.OnEnd() 안에서 Cancel = true 로 만들어 주는 방법이 있고, Condition 앞에서 true 로 만들어 줄 수도 있습니다. 어떤 방법을 선택하느냐는 취향의 문제입니다. 심지어는 Sequencer.OnUpdate() 에서 true 로 만들어 줘도 되겠죠.

그냥 순차적으로 실행되는 것이라고 생각하면 의미가 모호하지만, 이것의 실행 문맥( 스택이 rewind 된 것임 )을 잘 생각하면 문제가 없습니다.

참고로 NodeCanvas 같은 경우에는 Dynamic Composite 을 계층적으로 사용하면 Both 와 같은 Conditional Aborts 를 처리하는 것도 가능합니다. 그냥 Composite 에서 세 종류를 모두 설정할 수 있었으면 좋았겠지만 그 부분이 아쉽습니다.

Decoration task

Decoration task 는 조건을 의미합니다. Decoration 은 하나의 자식만을 가질 수 있는데, 조건을 만족하면 자식을 실행하고, 조건을 만족하지 못하면 false 를 반환합니다. Decoration 이 지정하는 조건을 만족했을 경우의 반환 결과는 자식의 반환 결과에 의존합니다. 자주 사용하는 Decoration 에는 Probability, TimeOut, CheckEvent 등이 있습니다. 

예를 들어 "B" Action 과 "C" Action 의 실행 확률을 결정하고 싶다고 합시다. 그러면 Probability task 를 사용해 다음과 같이 할 수 있습니다. 

참고

---

[ 1 ] Understanding Behavior Trees.

[ 2 ] On Finite State Machines and Reusablility.

[ 3 ] The Gist of Hierarchical FSM.

[ 4 ] Behavior trees for AI: How they work.

[ 5 ] 스테이트 머신 기초.

[ 6 ] Stack Data Structures.