- 해당 글은 UNSEEN 2기 코딩 테스트를 대비하여 정리 목적으로 적은 글입니다. 잘못된 부분이 있다면 지적해 주시면 감사하겠습니다.
3. FSM
FSM(Finite-state machine), 우리말로 유한 상태 머신은 상태(state)를 기반으로 동작을 제어하는 방식 중 하나이다. 일반적으로 게임 AI를 구현하기 위해 사용된다.
유한한 개수의 상태를 가질 수 있는 오토마타이다. FSM은 한 번에 오로지 하나의 상태만을 가지며, 현재 상태에서 어떠한 사건(Event)이 발생하면 다른 상태로 전이된다.
게임으로 비유하면 이렇다.
몬스터가 Idle, Run, Attack라는 상태를 가질 수 있다. 단, 몬스터는 한 번에 하나의 상태만을 갖는다. 달리면서 공격할 수는 없다.
몬스터는 플레이어를 발견하면 Run 상태가 되어 달리기 시작한다. 플레이어가 사거리 안으로 들어오면 Attack 상태가 되어 공격한다. 이렇듯, FSM은 전이 조건이 만족되면 다른 상태로 바뀌어 적합한 행동을 취한다.
if, switch로 상태를 하나하나 검사하거나 상태전환표를 만들 수도 있지만 너무 복잡해서 상태(State) 패턴을 주로 사용한다.
FSM의 실제 구현은 다음 글을 참고하면 좋을 것 같다.
유한 상태 기계 (Finite State Machine) : 네이버 블로그 (naver.com)
FSM은 상태가 많아질수록 전이 조건도 많아져서 구조가 복잡해지기 쉽다. 이를 해결하기 위해 계층적 유한 상태 머신(Hierarchical finite-state machine, HFSM)이 나타났다.
HFSM은 FSM을 항목별로 분류하여 정리한 것이다. 대기, 이동, 공격 각각의 상태로 전이 후 조건에 맞는 하위 상태를 선택하는 구조이다. 보다 복잡한 행동 패턴을 직관적이고 깔끔하게 그릴 수 있다.
하지만 전체적인 틀은 FSM과 동일하기 때문에, 상태가 많아질수록 복잡한 구조를 띄게 되고 가독성도 떨어지며 유지 보수하기도 어려워진다.
3. 비헤이비어트리(Behavior tree)
3-1. 비헤이비어 트리란?
해당 파트는 위키백과와 LINE Engineer overlast님의 글을 참고하였다(Behavior Tree를 알아봅시다 (linecorp.com)).
비헤이비어 트리는 FSM의 복잡성을 해결하는 의사결정 모델이다. 일반적으로 컴퓨터 과학, 로봇, 제어 시스템, 비디오 게임에서 사용된다.
비헤이비어 트리의 장점은 복잡한 작업을 작은 작업의 조합으로 만들어낼 수 있다는 것이다. 이때 중요한 점은 작은 작업들이 어떻게 구현되어 있는지는 신경 쓰지 않고 다만 결과만 받아올 뿐이라는 점이다. 따라서 FSM과 달리 복잡성이 훨씬 낮다.
계층적 유한 상태 머신(Hierarchical finite state machine, HFSM)처럼 유사하지만 메인 구성 블럭이 상태 대신 태스크(Task)로 구성된다는 결정적인 차이가 있다. 사람이 이해하기 쉽다는 점에서 에러도 덜 생기는 경향이 있고, 그래서 게임업계에서 유용하게 사용된다고 한다.
비헤이비어 트리는 반응적 계획(Reactive planning)이라 부르는 분야에서 시작되었는데, 2004년에 출시된 Halo 2가 Reactive planning을 도입한 게임 중 하나이다.
비헤이비어 트리(Behavior tree)는 행동(Behavior)을 트리(tree) 구조로 기술한다.
트리는 서브트리가 모여서 이루어진다. 비헤이비어 트리에서는 한 덩어리의 태스크가 서브트리(sub tree)를 이룬다. 이때, 부분이 되는 서브트리는 서브 태스크, 서브 트리, 블록이라고도 부른다.
비헤이비어 트리의 구성요소는 셋으로 나뉜다.
- root 노드: 루트 노드
- control flow 노드: 루트도 리프(leaf)도 아닌 노드들.
- execution 노드: 리프 노드. 태스크라고도 부르며, 실제로 일을 해낸다.
평가 시 각 노드는 깊이 우선 탐색을 하는데, 자식 노드에서 부모 노드로 상태가 반환된다.
- Success: 실행 성공
- Failure: 실행 실패
- Running: 실행 중. 다음번에 running을 반환한 노드가 다시 호출됨
모든 노드는 상황에 따라 평가 가능할 수도 있고 아닐 수도 있다. 그에 따라 active/inactive 상태를 설정할 수 있다.
여기서 실제로 비헤이비어 트리는 어떻게 구성되는지 이해하는 데에는 control flow 노드, execution 노드의 역할을 아는 것이 도움이 된다.
3-2. Control flow 노드
Control flow 노드는 루트와 리프 그 사이를 잇는 노드이다. 역할은 그 노드 아래에 있는 서브 트리(혹은 브랜치)를 통해 표현되는 행동(서브 태스크)을 제어하는 것이다.
Composite 유형이나 Decorator 유형에 대해서도 알아보겠지만, 이들 안에는 공통적으로 Selector 노드와 Sequence 노드가 존재한다.
- Selector 노드
자식 노드 가운데 하나를 실행하기 위한 노드.
여러 노드 중에 가장 적절한 노드 딱 하나를 선택하는 것이라 생각하면 좋을 것 같다. 따라서 하나가 선택되면 즉시 종료된다.
평가를 시작하면 selector의 자식 노드를 왼쪽에서 오른쪽(우선도 높은 쪽에서 낮은 쪽)의 순서로 깊이 우선 탐색 방식으로 평가한다.
Selector의 자식 노드 중 하나가 success나 running을 반환하면, selector는 즉시 success나 running을 부모 노드에 반환한다.
Selector의 모든 자식 노드가 failure를 반환했을 때 selector도 부모 노드에 failure를 반환한다.
- Sequence 노드
자식 노드를 순서대로 실행하기 위한 노드.
평가를 시작하면 sequence의 자식 노드를 왼쪽에서 오른쪽(우선도가 높은 쪽에서 낮은 쪽)의 순서로 깊이 우선 탐색으로 평가한다.
순서대로 모두 실행하기 위한 것이므로, 하나가 실패하면 모두가 실패한다.
Sequence의 자식 노드 중 하나가 failure나 running을 반환하면 selector는 즉시 failure나 running을 부모 노드에 반환한다. Selector의 모든 자식 노드가 success를 반환했을 때 selector도 부모 노드에 success를 반환한다.
3-3. Composite 노드(Control flow)
위 두 노드는 공통적으로 브랜치(서브트리)의 root가 된다.
Selector나 Sequence는 자식 노드와 트리 형태로 이루면서 부분-전체 계층을 표현한다. 그 점에서 디자인 패턴의 composite 패턴과 같은 동작을 하므로 composite 유형으로 분류하기도 한다.
실제 사용 시에는 무작위로 이러한 노드를 실행할 수 있도록 하거나, 아예 병렬로 처리할 수 있게 하는 노드 등도 추가될 수 있겠다.
하지만 composite 노드만으로는 if문, while문 같은 프로그래밍 언어에서 필수적으로 사용되는 제어문을 표현할 수 없다.
3-4. Decorator 노드(Control flow)
제어문을 실현하는 노드는 기존 노드에 제어문이라는 새로운 기능을 덧붙인다. 그 점에서 디자인 패턴의 decorator 패턴과 같은 동작을 하므로 decorator 유형으로 분류하기도 한다. 혹은 조건을 추가한다 하여 condition으로 분류한다.
예를 들면, 기존의 Selector, Sequence 같은 Composite 노드에 If문을 추가하여 조건을 만족할 때만 호출하도록 할 수 있다.
Decorator 노드로 구현되는 조건식에는 다음과 같은 것이 있다.
- While(Conditional Loop): 조건 충족을 평가하는 함수가 true를 반환하는 한 자식 노드의 평가를 반복한다. 조건 함수가 failure를 반환하면 부모 노드에 failure를 반환한다.
- If: 조건 충족을 평가하는 함수가 true를 반환한 경우, 현재 유효한 자식 노드를 호출해서 결과를 반환한다. 그 밖의 경우에는 자식 노드 호출 없이 부모 노드에 failure를 반환한다.
- Repeat(Loop): 미리 설정해 둔 횟수만큼 자식 노드의 평가가 완료됐다면 부모 노드에 success를 반환한다. 그 밖의 경우에는 부모 노드에 running을 반환한다.
이렇게 if문, while문, for문을 구현했는데 이밖에도 처리 중단, 인터럽트용 노드도 필요하고, 각 노드의 실행 결과를 저장하고 공유할 수 있는 메모리 영역, 메모리 영역에 저장된 데이터를 이용하여 제어를 구현하는 노드도 필요하다.
예를 들어, 언리얼 엔진에는 비헤이비어 트리 내의 메모리 영역 역할을 하는 블랙보드(Blackboard)라는 에셋이 존재한다.
3-5. Execution 노드
Execution 노드는 액션(action)이라고도 하며 실제 태스크를 수행한다. 액션은 리프(leaf) 노드로 작성되며 비헤이비어 트리 외부에 구현된 구체적인 함수를 호출한다.
그 함수의 결과에 따라 success, failure, running 같은 실행 결과 상태를 판단하여 부모 노드에 반환한다.
3-6. 실제 적용 시 고려할 점과 상용 엔진에서의 적용
게임 AI에 적용 시에는 매 틱(tick) 업데이트 처리가 이뤄질 때마다 비헤이비어 트리가 평가되어야 한다. 하지만 대화 시스템처럼 꼭 주기적으로 업데이트될 필요가 없을 때도 있고, 매 tick 업데이트하면 불필요하게 자원이 낭비될 때도 있다.
유니티 엔진, 언리얼 엔진과 같은 상용 엔진에서는 비헤이비어 트리를 별도로 구현할 필요 없이 활용할 수 있다.
유니티 엔진에서는 Behavior Designer라는 이름으로 유료 에셋이 많이 사용되는 반면, 언리얼 엔진에서는 무료로 비헤이비어 트리 기능이 제공된다.
튜토리얼에 따르면, 언리얼 엔진의 비헤이비어 트리에는 다음과 같은 특징이 있다.
- 전통적인 비헤이비어 트리와 달리 이벤트 기반(Event-driven)으로 동작한다. 이벤트가 생겨 다른 브랜치로 넘어가야 하는 게 아니면 틱마다 업데이트하지 않는다.
- 조건문을 데코레이터로 구현하여, 리프 노드가 아니라 서브트리의 루트에 있다.
- 병렬 처리를 위해 자손을 두 개만 갖는 단순 병렬 노드를 제공한다.
- Composite 노드를 주기적으로 실행하는 서비스 기능이 있다.
참고
- FSM
유한 상태 기계 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)
소년코딩 - 유니티 FSM: 유한 상태 머신 (tistory.com)
- BT
Behavior tree (artificial intelligence, robotics and control) - Wikipedia
'UNSEEN' 카테고리의 다른 글
| UNSEEN 5. 게임 알고리즘 (1): A*, 쿼드트리 (0) | 2024.01.30 |
|---|---|
| UNSEEN 대비 4. C++ 주요 컨테이너 (2) (map, unordered_map) (1) | 2024.01.28 |
| UNSEEN 대비 4. C++ 주요 컨테이너 (1) (array, vector, list) (1) | 2024.01.28 |
| UNSEEN 대비 3. 메모리 영역 (1) | 2024.01.25 |
| UNSEEN 대비 2. C++ 언어의 특징 (0) | 2024.01.25 |
댓글