FSM - HFSM - BT 구조

오늘 친구들과 이야기를 하면서 FSM과 BT(Behavior Tree)에 대해 이야기를 나누었습니다. 생각난 김에 해당 구조들에 대해 글을 작성해 보려고 합니다. 각 구조들은 AI 행동 패턴을 설계하는등 다양한 일에 사용됩니다.

 

기획자가 꼭 알 필요가 있을까? 하면 그렇다고 말할 수 있습니다.

 

알고리즘 위주의 설명이 아닌 구조 이해를 위한 글입니다.

 

---

FSM (Finite State Machines)

 

유한 상태 기계라고도 합니다. 보통 단순한 AI 구조에 사용됩니다. 해당 구조가 사용된 AI는 한 번에 한 가지의 상태를 보유하게 됩니다.

 

심플하게 두 가지 행동을 하는 AI가 있다고 합시다. FSM은 한 번에 한 가지 상태를 지니며 상태를 바꾸기 위해서는 전이가 필요합니다. 전이를 위해서는 해당 상태에서 이벤트를 인식하는 로직이 필요합니다.

 

대기에서 걷기로 전이하기 위해서는 대기에 걷기로 전환하는 이벤트가 포함되어 있어야 합니다. 걷기 역시 마찬가지입니다. 걷기에서 대기로 전환하려면 걷기에 대기로 전환하는 이벤트가 포함되어 있어야 합니다. 그림에서는 이를 화살표로 표현하겠습니다.

 

조건이 충족되면 AI는 대기 상태에서 걷기 상태로 전이됩니다. 간단히 위 상태로 NPC의 AI를 구상한다면 A 지점과 B 지점을 왕복하는 FSM을 만들 수도 있습니다. 보통은 그러한 행동을 순찰(Patrol)이라고 부릅니다.

 

심플하고 직관적인 모습이 FSM의 장점이지만 상태가 증가할수록 FSM은 장점을 잃어버리게 됩니다.

 

AI에 달리기가 추가되었다고 합시다. 그림에서 달리기는 항상 걷기 상태를 거쳐야만 도달할 수 있습니다. 반대로 해도 같습니다. 달리기가 대기 상태로 도달하기 위해서는 항상 걷기 상태를 거쳐야 합니다.

 

하지만 바로 달리게 만들고 싶은 사람도 있을 겁니다.

 

 

그럼 대기에서 바로 달리기로 전이가 되는 로직이 필요합니다. 반대 조건도 마찬가지입니다. 달리기에서 대기로 전이되는 로직이 필요합니다. 그럼 이해를 위해 간단히 비유를 들어 봅시다. 어디에 이런 AI가 필요할까요.

 

마을을 돌아다니는 NPC가 필요한데 적대적인 대상이 접근하면 맞서 싸우는 컨셉이 적당할 것 같습니다. 대충 유저를 돕는 마을의 경비원 NPC라고 합시다.

- 보통은 걷기, 달리기를 나누지 않고 추적(Chase)이나 순찰(Patrol)을 사용합니다. 목적지가 설정되지 않은 이동 로직은 어디로 튈지 모르기 때문입니다.-

 

마을의 경비원 NPC라면 마을을 순찰하며 발견된 적들을 공격해야 합니다. 대기 상태에서만 공격이 가능할까요? 아니면 걷기나 달리기에서 공격이 가능할까요? 대기 상태에서 공격이 가능하다고 하면 어떻게 될까요?

 

적을 발견하고 적을 향해 달리기(추적)를 한 다음 다시 대기 상태로 돌아와서 공격을 할까요?

 

FSM의 문제점에 대해 이야기를 하니 모든 상태에서 즉각 공격이 가능하다고 합시다.

 

 

점점 화살표가 늘어나기 시작합니다. 아직까지는 괜찮습니다. 하지만 생각해봅시다. AI는 이걸로 끝이 아닙니다. 체력이 부족해지면 자가 회복도 해야 하고 할당된 스킬도 사용해 줘야 합니다. 사망 상태도 있을 것이고 머리가 좀 더 좋다면 상황이 불리해졌을 때 도주할 수도 있습니다. 자신의 동료와 협공을 할 수도 있고 반대로 플레이어를 기다려주며 한명 한명 싸울수도 있습니다. 이러한 구조를 보는데 어려움을 느끼더라도 익숙해져야 합니다.

-개인적으로 가장 빠르게 해당 구조들을 이해하는 방법으로는 Unity나 Unreal 엔진에서 각 상태들을 가볍게 만들어보는게 좋다고 생각합니다.-

 

FSM 구조에서 상태가 계속해서 늘어나면 나중에는 이런 구조가 됩니다.

 

 

---

HFSM (Hierachical Finite State Machines)

 

계층적 유한 상태 기계입니다. 앞선 FSM의 복잡한 구조를 개선한 버전입니다. 간단히 이야기하자면 항목별로 분류하여 정리된 FSM라 할 수 있습니다.

 

 

HFSM 방식으로 왼쪽 구조를 오른쪽으로 변형시켰습니다. 여기서 대기 상태에서는 회복을 추가하고 이동 상태에서는 추적을 추가했습니다. 공격은 기본 공격과 스킬 공격으로 분할했습니다.

 

FSM이 단순 AI에 최적화되어 있다면 HFSM은 보다 더 복잡한 행동 패턴을 직관적이고 깔끔하게 그릴 수 있습니다. 대기, 이동, 공격 각각의 상태로 전이 후 조건에 맞는 하위 상태를 선택하는 구조입니다.

 

하지만 전체적인 틀은 FSM과 동일합니다. 이 역시 그 수가 괄목할만큼 늘어난다면 복잡한 구조를 띄게 되고 가독성과 유지 보수가 어려워집니다.

 

---

BT (Behavior Tree)

비헤이비어 트리 구조입니다. 개념은 크게 어렵지 않습니다. HFSM을 개선시킨 구조입니다. HFSM 구조는 각 상태마다 지닌 로직을 통해 다음 상태로 전이했다고 하면 BT 구조는 상위 노드에서 매 틱마다 우선순위를 평가하고 상태를 결정합니다.

 

그림으로 쉽게 이야기하자면 서로 엇갈리는 화살표가 필요 없습니다.

 

 

BT에서는 상태를 정해주는 건 Root 노드라고 생각하시면 됩니다. 그 때문에 각각의 상태 노드들은 자신들이 맡은 독립적인 행동 노드들만 컨트롤하면 됩니다.

 

쉽게 적을 추적하고 공격하는 행동을 한다고 합시다. FSM에서는 이동 상태에서 로직을 통해 판단 후 공격 상태로 전이 후 공격을 하면 되지만 BT에서는 전이를 담당하는 노드에서 우선순위를 재판단한 뒤 즉각 상태를 바꿔 버립니다.

-엄밀히 따지자면 상태와 상태를 점프하는 것이 아닌 이어달리기처럼 진행 중인 상태의 서브 트리로 다음 상태를 연결하는 방식입니다.-

 

또한 우선순위를 미리 결정할 수 있기에 먼저 처리해야 하는 일들이 있으면 우선순위를 조정해서 처리가 가능합니다. 복잡한 화살표도 없고 트리 구조를 띄고 있기 때문에 높은 가독성과 유지 보수가 장점입니다.

 

앞서 이야기했듯이 FSM 구조는 상태가 추가될수록 점점 복잡한 구조를 띄게 됩니다. 하지만 BT 구조는 말 그대로 나무가 뿌리를 내리듯 위에서부터 아래로 각 상태가 쉽게 확인이 가능합니다. 뭐든지 일단 잘 읽히면 최고입니다.

 

추가, 삭제 역시 편리합니다. 어떤 행동을 추가하고 싶으면 새로운 상태 노드를 끌어다가 추가한 다음 행동을 결정하는 상위 노드를 수정해 주면 됩니다. 제거 역시 해당 노드를 제거하고 상위 노드를 수정해 주면 됩니다. FSM의 경우 서로 연결되어 있는 모든 상태 노드를 수정해 줘야 합니다.

 

그래도 HFSM과 BT가 뭐가 다른 건지 잘 이해가 안 되시는 분들도 있으실 겁니다. 회사로 비유를 한다고 했을 때 HFSM이 수평 구조라면 BT는 수직 구조입니다. HFSM은 각 상태들이 스스로 다음 행동을 결정하지만 BT는 상위 상태가 할 일을 결정해 줍니다. 각 하위 상태들은 자신이 맡은 일만 하면 됩니다.

 

FSM, HFSM, BT는 이렇습니다.

 

 

아래는 참고자료입니다. 알고리즘에 대한 설명이 있습니다.

www.slideshare.net/yonghakim900/2009-ndc

[NDC 2009] 행동 트리로 구현하는 인공지능