행동 트리(Behavior Tree)

NDC Replay에서 AI 구현에 대한 내용을 찾다가 행동 트리라는 것을 알게 됐다.

행동 트리는 기존의 FSM, HFSM의 문제점을 보완하고, 보다 다양한 AI 패턴을 구현하는데 최적화된 방법이다.

확장성과 유지보수가 좋다고 한다. 현업에서 AI 구현할 때 자주 사용하는 방법인 것 같다. AI 기사를 보니 듀랑고, 디비전2에서 확인할 수 있었다. 대부분 행동 트리를 사용할 것 같다. 요즘 게임들은 AI 패턴이 다양하기 때문이다.

 

기본 개념정도 알아두면 좋을 것 같아서 관련 내용을 찾아서 정리해봤다. 근데 검색해봤는데 설명하는 곳마다 용어가 조금씩 달라서 헷갈린다. 가장 괜찮았던 글을 참고로 정리해본다.

 

#참고 링크

lifeisforu.tistory.com/327

 

#간단 명료 개념 설명, 예시 그림

engineering.linecorp.com/ko/blog/behavior-tree/

 

#행동 트리 관련 링크

ndcreplay.nexon.com/NDC2018/sessions/NDC2018_0082.html#k%5B%5D=behavior+tree

ndcreplay.nexon.com/NDC2016/sessions/NDC2016_0059.html#k%5B%5D=ai

(이해하기 좀 어려움) www.slideshare.net/yonghakim900/2009-ndc

 

#가마수트라 행동트리 링크(상세한 예시 그림)

www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php

 

먼저 행동 트리를 설명하기 전에 FSM, HFSM에 대해 간단하게 정리한다. 그러기 전에 노드에 대한 설명부터 하자.

---

0.노드(node)

• 노드는 컴퓨터 과학에 쓰이는 기초적인 단위
• 데이터를 포함하며 다른 노드와 연결될 수도 있음
• 노드는 하나의 자료 구조에 포함된 정보를 표현함
  - 노드들은 값이나 조건을 포함할 수 있음
  - 다른 독립된 자료 구조의 역할을 할 가능성이 있음
  - 노드는 하나의 부모 노드에 의해 표현된다.  
• 루트 노드(root node): 트리 구조의 가장 높은 지점
  - 이 노드에는 부모 노드가 없으나 해당 트리 아래에 속한 모든 노드의 부모노드나 조부모 노드의 역할을 맡는다. 
• 노드의 높이는 해당 노드에서 가장 거리가 먼 리프 노드(leaf node)까지의 경로 상의 간선의 전체 수에 의해 결정되며 트리의 높이는 루트 노드의 높이와 동등하다.
• 노드의 깊이(depth)는 특정 노드와 루트 노드 간의 거리에 의해 결정된다. 루트 노드는 0의 깊이를 갖는다고 말할 수 있다.
• 데이터는 이러한 네트워크 경로를 따라 탐지할 수 있다.
• 모든 IP 주소는 이러한 종류의 시스템의 노드를 사용하여 네트워크 내의 위치를 정의한다.

---

1.FSM(Finite State Machine)

• FSM은 상태(state)와 전이(transition)으로 구성
• 상태는 동시에 실행되는 행동(action)의 집합(애니메이션, 사운드, 대기 시간 등)
• 전이는 조건(condition)을 포함
• 전이의 조건이 충족되면, 상태는 다른 상태로 이동
• 상태를 직관적으로 확인하기 좋음
• 상태들이 매우 많아지게 되면 노드가 매우 복잡해짐(State 나누기, transition 연결 곤란)
• 서로 다른 문맥을 가진 로직을 재사용할 수 있는 방법을 제공하지 않음 = 낮은 확장성

---

2.HFSM(Heirarchical Finite State Machine)

• FSM의 노드가 복잡해지는 단점을 개선하기 위해서 상태를 계층화(혹은 그룹화)하는 계층적 유한 상태 기계( Hierarchical Finite State Machines) 발생함
• HFSM은 FSM들을 그룹화하고 계층화하여 상태를 파악하기 좋음
  
• HFSM은 어느 정도의 확장성이 있으나 한계 있음
  - 하위 상태를 모듈화하는 기능은 제공하지 않음
  - 같은 상태를 다른 문맥에서 사용 불가
  - 특정 상태에서 전이되어야 한다는 조건이 필요 

---

3.Behavior Tree

#가마수트라 글을 기본으로 하되 다른 곳의 설명이 간단 명료하면 그것을 정리했음

#가마수트라 글을 파파고로 번역한 것 중 이상한 부분은 내가 정리해서(영어실력이 허접하기 때문에) 정확도가 떨어질 수 있음, 영어 독해가 가능하시다면 원문 추천

 

 

• 행동 트리는 AI 엔터티의 의사결정 흐름을 제어하는 계층적 노드의 트리다.
• tree의 범위, leaves은 AI 실체를 제어하는 실제 명령이다.
• branch를 형성하는 것은 AI가 tree 아래를 실행할 때 가장 적합한 명령의 sequence에 도달하도록 제어하는 다양한 유형의 유틸리티 노드들이다.
• 특정 기능을 수행하는 하위 트리를 호출하는 노드로 개발자가 매우 설득력 있는 AI 행동을 제공하기 위해 함께 체인으로 묶을 수 있는 행동 라이브러리를 만들 수 있다.
• 단순한 하부 구조
• 모듈화 = 단순화(이해 좋음), 좋은 유지 보수
• 중요 사항
  - 탐색 순서가 매우 중요함(왼쪽에서 오른쪽으로)
  - 노드는 서로간 의존성이 없어야 한다.
  - 게임 오브젝트나 blackboard에서 정보를 얻어와야함

 

3.1.작동 원리

1.Tree Traversal(Tree Traversal = 가로지르는, 횡단하는, 트리의 노드를 실행하는 의미인 듯?)
행동 트리의 핵심 측면은 코드베이스 내의 방법과 달리, 트리의 특정 노드나 분기가 완료되기까지 많은 시간이 걸릴 수 있다는 것이다. 행동 트리의 기본 구현에서 시스템은 모든 프레임마다 트리의 루트로부터 아래로 이동하며, 어떤 노드가 활성 상태인지 테스트하고, 현재 활성 노드에 도달하여 다시 체크할 때까지 트리의 모든 노드를 재점검한다.

이것은 일을 하는 데 그다지 효율적인 방법이 아니다. 특히, 발달하는 동안(게임을 개발하는 동안?) 행동 트리가 발달하고 확장되면서 행동 트리가 더 깊어질 때 말이다. 당신이 구현하는 행동 트리는 현재 처리 중인 노드를 전체 트리의 틱 통과에 의해서가 아니라 동작 트리 엔진 내에서 바로 체크될 수 있도록 저장해야 한다. 다행히도 JBT(뭔지 모르겠음)는 이 범주에 들어맞는다.

 

2.노드의 3가지 상태

• Success
  - 부모 노드에게 실행 성공 여부를 알려줌
• Failure
  - 부모 노드에게 실행 실패 여부를 알려줌
• Running
  - 성패가 결정되지 않았고 노드가 아직 실행 중인 상태
  - 이 시점에서 체크하여 다음 번에 Running을 반환한 노드를 다시 호출함

이 기능은 노드의 처리가 게임의 많은 틱에 대해 지속되도록 하기 때문에 행동 트리의 핵심이다. 예를 들어, Walk 노드는 경로를 계산하려고 시도하는 시간 동안 Running 상태와 캐릭터가 지정된 위치로 이동하는 데 걸리는 시간을 제공한다.

 

만약 어떤 이유로든 경로 찾기가 실패했거나, 또는 대상 위치에 도달하는 캐릭터를 멈추기 위해 걷는 동안 다른 문제가 발생하면, 노드는 부모에게 실패를 반환한다. 언제든지 문자의 현재 위치가 대상 위치와 같을 경우, Walk 명령이 성공적으로 실행되었음을 나타내는 성공을 반환한다.

 

분리된(in isolation) 이 노드는 성공과 실패를 위해 정의된 a cast iron contract(확실한 계약? 확실하게 정의되었으며?)을 가지고 있으며, 이 노드를 활용하는 모든 트리는 이 노드로부터 받은 결과를 보장받을 수 있다.

 

그런 다음 이러한 상태는 트리의 흐름을 전파하고 정의하여 일련의 이벤트와 AI가 원하는 대로 동작하도록 트리 아래쪽의 다른 실행 경로를 제공한다.

 

3.행동 트리의 주요 노드

Composite

• 복합 노드는 하나 이상의 자식을 가질 수 있는 노드
• 자식 노드 중 하나 이상을 문제의 특정 복합 노드에 따라 첫 번째에서 마지막 순서로 또는 무작위 순서로 처리함
• 어떤 단계에서는 처리 완료를 고려하고 종종 자식 노드의 성패를 부모 노드에게 성공 또는 실패 중 하나를 전달한다.
• 부모 노드가 자식 노드의 결과를 처리하는 동안 자식 노드는 계속해서 부모 Running를 반환한다.
• 일반적으로 사용되는 복합 노드는 Sequence
• Sequence는 각 자식 노드를 순서대로 실행하며, 자식 노드 중 한 명이 실패하는 지점에서 failure를 반환하고 모든 자식 노드가 Success를 반환하면 부모 노드에게 Success을 반환한다.

 

Decorator

• Decorator는 하나의 자식 노드만 가질 수 있음
• Decorator의 기능은 자식 노드의 상태로부터 받은 결과를 변형시키거나, 자식 노드를 종료시키거나, 장식 노드 유형에 따라 자식 노드의 처리를 반복하는 것이다.
• 조건을 만족하면 자식을 실행하고, 조건을 만족하지 못하면 false 를 반환 = 조건문 느낌
• Decorator가 지정하는 조건을 만족했을 경우의 반환 결과는 자식의 반환 결과에 의존함
• 일반적으로 사용되는 invert 노드: 단순히 자식 노드의 결과를 뒤집는다.(!= 인듯) 자식 노드가 실패하면 부모에게 성공을 돌려주거나, 자식 노드가 성공해서 부모에게 실패를 돌려준다.

 

Leaf(다른 글의 = execution, action 노드인듯)

• Leaf 노드는 가장 낮은 수준의 노드 유형이며 어떤 자식 노드도 가질 수 없다.
  
• Leaf 노드는 당신의 게임에 의해 정의되고 구현되어 당신의 tree가 실제로 유용한 일을 하도록 만드는 데 필요한 특정한 게임이나 캐릭터 특정한 테스트나 행동을 하기 위해 실행될 것이기 때문에 가장 강력한 노드 타입이다.
  - 예) Walk leaf 노드는 캐릭터가 지도상의 특정 지점까지 걸어가게 하고, 그 결과에 따라 성패가 반환된다.
• Leaf 노드가 무엇인지 정의할 수 있기 때문에(종종 아주 최소의 코드를 가지고 있음) 
• Leaf 노드는 Composite와 Decorators 아래에 층을 이룰 때 매우 표현력이 뛰어나며, 꽤 복잡하고 지능적으로 우선순위를 매긴 행동을 할 수 있는 꽤 강력한 행동 트리를 만들 수 있게 해준다.
  - 게임 코드에 비유 Composite, Decorators = function
  - leaf 노드 = 당신의 코드 흐름을 정의하기 위한 문장과 루프, AI 캐릭터의 행동, 상태 또는 상황 등 게임의 기능
• Leaf 노드는 Parameter로 정의할 수 있다. 
  - 예) Walk leaf 노드는 캐릭터가 걸어갈 좌표를 가질 수 있다.
• 파라미터는 AI 캐릭터가 트리를 처리하는 컨텍스트 안에서 저장된 변수를 얻을 수 있다.
  - 예)걷기 위한 위치는 변수가 저장된 'GetSafeLocation' 노드에 의해 결정됨
  - Walk 노드는 컨텍스트에 저장된 변수를 사용하여 목적지를 정의할 수 있음
• 다른 유형의 리프 노드는 행동 트리를 호출하는 것으로, 기존 트리의 데이터 컨텍스트를 호출된 트리에 전달한다. 특정한 변수 이름을 사용하여 셀 수 없이 많은 장소에서 재사용될 수 있는 행동 트리를 만들기 위해 모듈화할 수 있게 해주기 때문에 핵심이다.
  - 예) 'Break to Building' 동작은 'TargetBuilding' 변수가 작동될 것으로 예상할 수 있으므로 부모 트리는 이 변수를
     컨텍스트에서 설정한 다음 하위 트리 leaf 노드를 통해 하위 트리를 호출할 수 있다.

 

3.2.행동 트리의 노드 상세 설명

 

1.Composite Nodes

 

Sequence

• 자식 노드를 순서대로 실행하기 위한 노드
• 평가를 시작하면 sequence의 자식 노드를 왼쪽에서 오른쪽(우선도가 높은 쪽에서 낮은 쪽)의 순서로 깊이 우선 탐색 방식으로 평가한다.
• Sequence의 자식 노드 중 하나가 failure나 running을 반환하면 selector는 즉시 failure나 running을 부모 노드에 반환한다.
• Selector의 모든 자식 노드가 success를 반환했을 때는 selector도 부모 노드에 success를 반환한다.
• 강력한 조건부 검사를 가능하게 한다.
• AND 게이트와 유사하다.
• Invert를 이용하여 NOT 게이트를 이용 가능하다.
• Sequence를 이용하여 캐릭터나 게임 월드의 조건을 테스트하는 데 필요한 노드 양을 대폭 줄일 수 있다.

 

Selector

• 자식 노드 가운데 하나를 실행하기 위한 노드
• 평가를 시작하면 selector의 자식 노드를 왼쪽에서 오른쪽(우선도가 높은 쪽에서 낮은 쪽)의 순서로 깊이 우선 탐색 방식으로 평가한다.
• Selector의 자식 노드 중 하나가 success나 running을 반환하면, selector는 즉시 success나 running을 부모 노드에 반환한다.
• Selector의 모든 자식 노드가 failure를 반환했을 때는 selector도 부모 노드에 failure를 반환한다.

 

2.Decorator Nodes

 

Inverter

• 자식 노드의 결과를 뒤집거나 부정한다.
• 성공은 실패가 되고, 실패는 성공이 된다.
• 조건부에서 가장 자주 사용된다.

Succeeder

• Succeeders는 자식 노드가 실제로 무엇을 반환했든 상관없이 항상 성공을 반환한다.
• 이는 고장이 예상되거나 예상되는 트리의 분기를 처리하려는 경우 유용하지만 분기가 배치된 시퀀스의 처리를 포기하지는 않는다.
• 부모에 고장이 필요한 경우 inverter가 succeeder를 'failler'로 만들기 때문에 이 유형의 노드와 정반대가 필요하지 않다.

 

Repeater(Loop)

• repeater는 자식 노드가 결과를 반환할 때마다 자식 노드를 재처리한다.
• 보통 트리의 맨 밑부분에서 사용되는데 반복 실행하기 위해서 사용한다.
• repeater는 부모에게 돌아가기 전에 자식 노드에게 정해진 횟수를 선택적으로 실행할 수 있다.

 

Repeat Until Fail

• 자식 노드가 실패를 반환할 때까지 자식 노드를 반복 실행한다.
• 실패를 반환하면 부모에게 성공을 반환한다.

 

3.Data Context

• 행동 트리가 AI 엔티티에 호출되면 노드에 의해 해석되고 변경되는 임의 변수의 저장소로 작용하는 데이터 컨텍스트도 생성된다.
• 노드는 나중에 처리된 노드에 상황별 데이터를 제공하고 행동 트리가 응집력 있는 단위 역할을 할 수 있도록 변수를 읽거나 쓸 수 있다.