1291.27 게임 AI의 복잡도 증가와 상태 머신의 한계

1291.27 게임 AI의 복잡도 증가와 상태 머신의 한계

1. 게임 AI 복잡도 증가의 기술적 배경

2000년대에 진입하면서 비디오 게임 산업은 하드웨어 성능의 급격한 향상, 3차원 게임 환경의 보편화, 개방형 세계(open world) 설계의 확산에 의하여 NPC(Non-Player Character) 행동 제어의 복잡도가 전례 없이 증가하였다. 이러한 복잡도 증가는 단순한 양적 확대에 그치지 않고, NPC 행동의 질적 변화를 수반하였다.

1990년대까지의 NPC는 제한된 행동 모드(3~8개 상태)로 충분히 표현 가능한 반응적 에이전트(reactive agent)에 해당하였다. 그러나 2000년대의 게임에서 NPC는 다층적 의사 결정, 동적 환경 적응, 다수 에이전트 간 협업, 장기적 목표 추구 등 인지적 복잡성이 현저히 증가한 행동을 요구받게 되었다.

2. NPC 행동 복잡도 증가의 구체적 양상

2.1 행동 모드의 수적 팽창

초기 게임 AI에서 NPC의 행동 상태 수가 4~6개에 불과하였던 반면, 2000년대 후반의 대형 타이틀에서 단일 NPC의 행동 상태 수는 수십 개에 달하게 되었다. 예를 들어, 전투 NPC의 행동은 다음과 같이 세분화되었다:

  • 비활성 계열: 대기, 순찰, 감시, 수면, 자유 행동
  • 경계 계열: 의심, 경계, 수색, 경보 전파
  • 전투 계열: 접근, 사격, 엄폐, 측면 기동, 수류탄 투척, 근접 전투, 화력 지원
  • 후퇴 계열: 후퇴, 재집결, 구호 요청, 항복
  • 상호작용 계열: 대화, 거래, 동행, 명령 수행

이러한 상태들의 단일 FSM 내 배치는 상태 전이 복잡도를 급격히 증가시킨다. n개의 상태를 보유한 FSM에서 가능한 전이의 최대 수는 n(n-1)이며, 위 예시에서 상태 수가 20개라면 가능한 전이의 최대 수는 380에 달한다. 실제로 모든 전이가 의미 있는 것은 아니나, 설계자가 정의하여야 할 실질 전이의 수도 상당하며, 각 전이의 조건을 명시적으로 정의하여야 한다.

2.2 문맥 의존적 행동 분화

동일한 행동 모드라도 게임 환경의 문맥(context)에 따라 상이한 세부 행동을 요구하게 되었다. 예를 들어, “엄폐” 행동은 엄폐물의 유형(낮은 벽, 높은 벽, 기둥), 적의 위치와 수, 잔여 탄약, 주변 아군의 존재에 따라 상이한 실행 양상을 보여야 한다. 이를 FSM으로 모델링하면, 문맥 조합에 비례하는 하위 상태의 증가가 불가피하다.

2.3 행동의 동시성과 층위 구분

현대 게임 NPC는 복수의 행동을 동시에 수행하여야 한다. 이동 행동(걷기, 달리기, 웅크리기)과 상체 행동(사격, 재장전, 수류탄 투척)이 독립적으로 병행 실행되며, 감정 표현(표정, 음성)이 행동과 동시에 관리되어야 한다. FSM은 본질적으로 단일 활성 상태(single active state)만을 허용하므로, 병행 행동의 표현을 위해서는 직교 영역(orthogonal region) 또는 복수 FSM의 병렬 운용이 필요하며, 이는 FSM 간 동기화 복잡도를 가중시킨다.

2.4 팀 단위 조정 행동

현대 전술 게임에서 NPC는 분대(squad) 단위로 협업하여 전술 행동을 수행한다. 분대 수준의 행동(제압 사격, 진지 돌파, 포위 기동)과 개별 NPC 수준의 행동이 조율되어야 하며, 이는 개별 NPC의 FSM에 분대 수준 상태의 투영(projection)이 필요함을 의미한다. 분대 상태와 개별 상태의 직곱(Cartesian product)이 발생하여 상태 공간이 급증한다.

3. 상태 머신의 구조적 한계가 게임 AI에서 발현된 양상

3.1 상태 폭발에 의한 설계 불가능성

상태 수가 20~30개를 초과하면, 상태 전이도(state transition diagram)의 시각적 표현이 가독 불가능한 수준에 도달한다. Champandard(2007)는 산업 현장에서 100개 이상의 상태를 보유한 NPC FSM이 “스파게티 전이도(spaghetti transition diagram)“로 변질되어, 원 설계자조차 전이 경로를 추적할 수 없는 상태에 이른 사례를 보고하였다.

상태 전이도의 간선(edge) 밀도가 증가하면, 시각적 교차(visual crossing)가 빈번하게 발생하여 도표의 정보 전달 기능이 실질적으로 상실된다. 이는 FSM의 핵심 이점이었던 “설계의 직관성“이 규모 증가에 의하여 스스로 파괴되는 역설적 상황이다.

3.2 전역 전이의 중복 정의 부담

긴급 이벤트(사망, 경보 발령, 스크립트 행동 트리거 등)에 대한 전이는 모든 상태에서 동일하게 발생하여야 한다. n개의 상태에 대하여 k종의 전역 이벤트가 존재하면, n \times k개의 전역 전이를 일일이 정의하여야 한다. 상태가 추가될 때마다 k개의 전역 전이가 추가로 정의되어야 하며, 하나라도 누락되면 해당 상태에서 긴급 이벤트에 대한 반응이 실종되는 오류가 발생한다.

Harel(1987)의 Statecharts는 이 문제를 슈퍼스테이트(superstate)에 의한 전이 상속으로 완화하였으나, Statecharts의 도입은 계층 간 전이 관리, 히스토리 상태(history state) 처리, 직교 영역 동기화 등 새로운 복잡도를 추가적으로 발생시킨다.

3.3 행동 재사용의 구조적 불가능성

특정 행동 패턴(예: “위험 감지 시 엄폐 후 사격”)이 여러 NPC 유형에서 공유되어야 할 경우, FSM에서 이 패턴은 상태와 전이의 부분 집합으로 표현된다. 그러나 FSM의 상태 간 전이가 전역적으로 정의되므로, 특정 상태-전이 부분 집합을 추출하여 다른 FSM에 이식하면, 이식 대상 FSM의 기존 상태와 전이 규칙과의 충돌이 발생한다. 이는 FSM이 행동의 모듈적 캡슐화(modular encapsulation)를 구조적으로 지원하지 않기 때문이다.

게임 산업에서 이 문제는 실질적 비용 증가를 초래하였다. NPC 유형의 수가 증가할수록 각 유형에 대한 FSM을 독립적으로 설계·유지하여야 하며, 유형 간 공통 행동의 일관성을 수동으로 보장하여야 하는 반복적 노동이 발생하였다.

3.4 행동 추가의 비국소적 파급 효과

기존 FSM에 새로운 행동 상태를 추가하면, 기존의 모든 상태에서 새 상태로의 전이 가능성을 검토하고, 적절한 전이 조건을 정의하여야 한다. n개의 기존 상태에 1개의 상태를 추가하면, 최대 2n개의 새로운 전이(기존 상태에서 새 상태로의 n개, 새 상태에서 기존 상태로의 n개)를 검토하여야 한다. 이는 행동 추가의 비용이 기존 상태 수에 비례하여 증가함을 의미하며, 대규모 FSM에서의 점진적 기능 확장을 비실용적으로 만든다.

3.5 디버깅과 행동 예측의 어려움

대규모 FSM에서 NPC가 예기치 않은 행동을 보일 때, 해당 행동의 원인을 추적하기 위해서는 현재 상태에 도달하기까지의 상태 전이 이력(state transition history)을 분석하여야 한다. 상태 전이 이력의 가능한 경로 수는 상태 수와 전이 수에 대하여 지수적으로 증가하므로, 특정 시점의 NPC 행동이 의도된 것인지 판별하는 작업 자체가 조합적 탐색 문제로 귀결된다.

Isla(2005)는 Bungie Studios에서 Halo 2 개발 과정에서 대규모 FSM 기반 NPC의 비정상 행동 원인 추적에 소요되는 디버깅 시간이 개발 전체의 상당한 비중을 차지하였다고 보고하면서, 이러한 디버깅 비용이 FSM에서 행동 트리로의 전환을 결정한 주요 동기 중 하나임을 밝혔다.

4. 게임 산업에서의 FSM 한계 대응 시도

4.1 계층적 FSM (HFSM)의 도입

상태 폭발을 완화하기 위하여 상태 내부에 하위 FSM을 내포하는 계층적 FSM(Hierarchical FSM, HFSM)이 광범위하게 도입되었다. 상위 수준 FSM이 “전투”, “탐색”, “비활성” 등 추상적 행동 모드를 관리하고, 각 추상 상태 내부에 세부 행동의 하위 FSM이 배치되는 구조이다.

HFSM은 상태의 계층적 그룹화에 의하여 각 계층의 상태 수를 감소시키나, 다음의 잔존 한계를 가진다:

  • 계층 관통 전이: 하위 FSM의 상태에서 상위 계층의 다른 상태로 직접 전이가 필요한 경우, 계층 구조의 캡슐화가 깨진다.
  • 재진입 정책의 복잡성: 상위 상태에서 이탈 후 재진입 시, 하위 FSM의 초기 상태로 복귀할 것인지 이전 활성 상태로 복귀할 것인지(히스토리 상태)의 정책 결정이 필요하다.
  • 설계 부담의 이전: 상태 폭발이 해소된 것이 아니라 계층 간으로 분산된 것이므로, 전체 복잡도는 유지된다.

4.2 스택 기반 FSM (Pushdown Automaton)

일부 게임에서는 현재 상태를 스택에 저장하고 새로운 상태를 푸시(push)하여 일시적 행동 전환을 구현한 후, 완료 시 팝(pop)하여 이전 상태로 복귀하는 스택 기반 FSM이 활용되었다. 이 방식은 일시적 중단/재개 패턴을 자연스럽게 표현하나, 스택 깊이가 증가하면 상태 복원의 일관성 보장이 어려우며, 스택에 저장된 상태 간의 문맥 전달(context passing) 메커니즘이 별도로 필요하다.

4.3 병렬 FSM 합성

이동, 전투, 감정 등 독립적 행동 축에 대하여 별도의 FSM을 병렬로 운용하고, 각 FSM의 출력을 합성(composition)하는 방식이 시도되었다. 그러나 독립 FSM 간의 행동 충돌(conflict)—예를 들어, 이동 FSM이 “달리기“를 선택한 반면 전투 FSM이 “사격“을 선택하여 달리며 사격하는 비현실적 행동이 발생—의 해소를 위한 중재 논리(arbitration logic)가 추가적으로 필요하며, 이 중재 논리 자체가 또 다른 복잡도 원천이 된다.

5. FSM 한계의 산업적 결과: 대안 기법에 대한 수요

전술한 FSM의 구조적 한계가 산업적 규모에서 현실적 문제로 발현됨에 따라, 게임 AI 분야에서 FSM을 대체할 수 있는 행동 제어 기법에 대한 수요가 급증하였다. 이 수요의 핵심 요구사항은 다음과 같이 정리된다:

  1. 모듈적 행동 정의: 행동을 독립적 모듈로 정의하고, 모듈 간 영향 없이 조합 가능할 것
  2. 반응적 행동의 자연스러운 표현: 전역 전이의 중복 정의 없이 긴급 이벤트에 대한 즉각적 반응이 가능할 것
  3. 점진적 확장 용이성: 행동 추가의 비용이 기존 시스템 규모에 비례하지 않을 것
  4. 시각적 설계 및 디버깅: 비프로그래머 인력(게임 디자이너)이 행동 논리를 시각적으로 설계·수정·디버깅할 수 있을 것
  5. 재사용성: 동일 행동 모듈을 다수의 NPC 유형에서 재사용 가능할 것

이러한 요구사항의 총합을 충족하는 기법으로서 행동 트리(Behavior Tree)가 2000년대 중반에 게임 산업에서 독립적으로 고안되었으며, FSM의 구조적 한계에 대한 산업적 대응이 행동 트리 기법의 발명을 촉발한 직접적 원인이 되었다.

6. 참고 문헌

  • Champandard, A. J. (2007). “Understanding Behavior Trees.” AiGameDev.com.
  • Isla, D. (2005). “Handling Complexity in the Halo 2 AI.” Proceedings of the Game Developers Conference (GDC).
  • Harel, D. (1987). “Statecharts: A Visual Formalism for Complex Systems.” Science of Computer Programming, 8(3), 231–274.
  • Millington, I., & Funge, J. (2009). Artificial Intelligence for Games (2nd ed.). Morgan Kaufmann.
  • Buckland, M. (2005). Programming Game AI by Example. Wordware Publishing.
  • Rabin, S. (Ed.). (2002). AI Game Programming Wisdom. Charles River Media.

v0.2.0