게임 AI - Behavior Tree

안녕하세요!
오늘은 게임 클로닝 프로젝트를 설명하기 전에, 개념적 설명이 있는 포스팅이 필요하다고 생각해서, 개념 포스팅을 작성해보려 합니다.

게임 캐릭터나, 몬스터, 하물며 RTS 게임 같은 경우는 스타크래프트의 성큰이나 포톤캐논 등이 AI를 가가지고 알아서 동작하는 것이 필요합니다.
보통 이럴 때, 작성한 대로 움직여 주는 AI를 심어주어야 합니다.

AI 를 구현하는 데에는 여러 방식이 필요합니다만, 오늘은 BehaviorTree(이하, BT) 에 대해서 설명을 조금 해보려고 합니다.

Behavior Tree란 무엇일까?

BT 이전에, 사용하기 더욱 사용하기 쉬운 도구들은 얼마든지 있습니다.
FSM, HFSM, State Pattern 등이 있을 것 같네요.
이것들에 대해선 다음에 알아보도록 하겠습니다.

기본 개념은 "게임에서 Behavior(행동)을 Tree 구조로 만들어서 AI 행동을 제어하는 것" 입니다.
설명을 보면 어려울 수 있겠지만, 그렇지 않습니다.
Tree는 여기서 Node들을 가진 하나의 컨테이너, 그냥 공간이라고 생각하면 됩니다.
그리고 Node는 무엇이냐면 원시적인 자료형을 등록할 수 있고, 사용자가 정의하려고하는 모든 것들이라고 할 수 있습니다.
사용자가 정의하려고 하는 행동 함수라던지, UID 변수라던지 등을 가지고 있는 하나의 클래스나 구조체라고 생각할 수 있습니다.

그리고, 개념에 따른 BT의 기본 컨셉은 아래와 같습니다.

Root 노드를 시작으로 구성한 BT leaf 까지 실행하는 것이 기본 개념니다.
평가를 시작한 트리 노드는 구성에 따라 최하단 leaf 까지 실행되지 않을수도 있다.
트리 노드가 한 개 이상의 자식 노드가 있다면 평가 및 실행할 수 있다.
실행에 대한 순서는 DFS 검색 알고리즘의 순서 기반으로 실행된다.
- 트리 순회에서는 Pre-Order 순서, 이는 DFS의 한 종류라고 한다.
노드는 반드시 평가에 대한 결과 값을 리턴한다.(Success, Failure, Running)

작동 원리는 어떻게 되는가?

작동 원리는 기본적으로 최상위 루트, 자식 중 좌측에서 우측으로, 깊이 우선으로 탐색을 진행합니다.
DFS를 떠올리시면 BT의 작동 순서를 정확하게 이해할 수 있습니다.

원리는 간단하여 아래 첨부 이미지를 보시면 이해가 빠를 것으로 생각됩니다.

이 이미지는 로봇의 탐색 계획을 BT모델로 구성한 것입니다.

보면 Retrieved 가 검색됨이라는 의미를 가지고 있어, 검색하지 않았다면,
1) Search on the Floor : 바닥을 찾아볼 것이고
2) Search in the Drawers : 서랍장을 찾아볼 것이고
3) Search in the Closet : 옷장을 찾아볼 것이다
라는 것으로 이해할 수 있습니다.

그 다음엔 뭔가 잡을려고 하는것 같습니다. 이정도만 하면 원리 이해는 된 것 같습니다.
지금 로봇의 탐색 계획을 정확하게 파악할 필요는 없습니다.

어떤 노드가 존재하는가?

기본적으로 트리를 노드들의 역할을 주어져 있습니다.

Composite Task (복합 태스크)
- Sequence : 자식 노드가 Failure를 반환할 때 까지, 자식 노드를 실행하는 순차적 실행을 지향합니다. Failure 일 경우 자식들을 실행하지 않는다.
- Selector : 자식 노드가 True를 반환할 때 까지, 자식노드를 실행하고, True 일 경우 하위 자식들을 실행하지 않는다.
Decoration Task (조건 태스크)
- Decoration Task는 하나의 자식만을 가질 수 있는데, 조건을 만족하면 자식을 실행, 만족하지 못하면 False를 반환합니다.
- 자주 사용하는 것들에는 TimeOut, Delay 등으로 많이 사용합니다.
Action Task (행동 태스크)
- 실제 행동을 표현하는 단말 노드입니다.