1291.26 초기 게임 AI의 유한 상태 머신 기반 설계

1. 초기 비디오 게임에서의 NPC 행동 제어 요구

초기 비디오 게임에서 비플레이어 캐릭터(Non-Player Character, NPC)의 행동 제어는 게임의 오락적 가치를 결정하는 핵심 요소로 인식되었다. 1970년대 후반에서 1980년대의 아케이드 게임에서 NPC는 플레이어에게 도전 과제를 제공하는 적대적 에이전트(adversarial agent) 또는 환경적 장애물로 기능하였으며, NPC의 행동이 예측 가능하면서도 적절한 수준의 난이도를 제공하여야 한다는 설계 요구사항이 존재하였다.

이 시기의 하드웨어 제약—제한된 프로세서 성능, 극소량의 메모리—은 NPC 행동 제어 기법의 선택에 결정적 영향을 미쳤다. 계산량이 적고 메모리 효율이 높은 결정론적(deterministic) 행동 제어 기법이 필수적이었으며, 유한 상태 머신(Finite State Machine, FSM)은 이러한 제약 조건에 부합하는 최적의 기법으로 자연스럽게 채택되었다.

2. 유한 상태 머신의 게임 AI 최초 적용 사례

2.1 Pac-Man (1980)의 유령 행동 제어

Namco의 Pac-Man(1980)은 FSM 기반 NPC 행동 제어의 초기 대표 사례로 학술적으로 빈번히 인용된다. 4개의 유령(Blinky, Pinky, Inky, Clyde) 에이전트는 각각 고유한 추적 전략을 보유하되, 다음의 공통 상태 집합으로 행동을 관리한다:

추적 상태(Chase): 유령이 고유 알고리즘에 의하여 플레이어를 추적하는 상태
배회 상태(Scatter): 유령이 맵의 지정된 코너로 이동하는 상태
공포 상태(Frightened): 플레이어가 파워 펠릿(power pellet)을 획득하면 진입하는 도주 상태
포식 상태(Eaten): 유령이 플레이어에게 포식된 후 소환 지점으로 복귀하는 상태

이 FSM은 형식적으로 5-튜플 $M = (Q, \Sigma, \delta, q_0, F)$ 로 정의된다:

$Q = \{\text{Chase}, \text{Scatter}, \text{Frightened}, \text{Eaten}\}$

$\Sigma = \{\text{타이머 만료}, \text{파워 펠릿 획득}, \text{플레이어 접촉}\}$

상태 전이 함수 $\delta$ 는 다음의 규칙을 따른다:

$\delta(\text{Chase}, \text{타이머 만료}) = \text{Scatter}$
$\delta(\text{Scatter}, \text{타이머 만료}) = \text{Chase}$
$\delta(\text{Chase}, \text{파워 펠릿 획득}) = \text{Frightened}$
$\delta(\text{Scatter}, \text{파워 펠릿 획득}) = \text{Frightened}$
$\delta(\text{Frightened}, \text{타이머 만료}) = \text{Chase}$
$\delta(\text{Frightened}, \text{플레이어 접촉}) = \text{Eaten}$
$\delta(\text{Eaten}, \text{소환 지점 도달}) = \text{Chase}$

이 설계에서 주목할 점은/Chase와 Scatter 간의 주기적 전환이 타이머에 의하여 결정론적으로 제어되며, 전체 게임 세션에서 이 주기가 사전 정의된 시간표에 따라 점진적으로 Chase의 비중이 증가하도록 설계되었다는 것이다. 4개의 상태와 제한된 전이 규칙으로 구현 가능한 이 FSM은 극히 적은 계산 자원으로 플레이어에게 다양한 게임 경험을 제공하였다.

2.2 Galaga (1981) 및 고정 패턴 기반 FSM

Galaga(1981) 등의 고정 스크롤 슈팅 게임에서 적 유닛의 행동은 편대 상태(Formation), 공격 상태(Attack), **복귀 상태(Return)**의 3상태 FSM으로 제어되었다. 편대 상태에서 적 유닛은 화면 상단에서 정렬된 대형을 유지하고, 공격 상태에서는 사전 정의된 곡선 궤적을 따라 플레이어를 향하여 돌진하며, 복귀 상태에서는 편대 위치로 되돌아간다. 이 FSM은 상태 수가 3개에 불과하여 구현이 극도로 간결하며, 적 유닛의 공격 궤적은 사전 정의된 조회 테이블(lookup table)에 저장되어 실시간 계산 없이 참조되었다.

3. FSM 기반 게임 AI 설계의 기본 구조

3.1 상태의 정의

초기 게임 AI에서 FSM의 각 상태는 NPC가 수행하는 하나의 행동 모드(behavioral mode)에 대응한다. 상태 내부에서 NPC는 해당 행동 모드에 고유한 갱신 논리(update logic)를 매 프레임(frame) 실행한다. 예를 들어, “순찰” 상태에서는 사전 정의된 경유점(waypoint)을 따라 이동하는 논리가 실행되고, “추적” 상태에서는 플레이어의 현재 위치를 향하여 경로를 계산하는 논리가 실행된다.

3.2 전이 조건의 정의

상태 간 전이는 환경 조건의 평가에 의하여 발생한다. 전이 조건은 다음의 유형으로 분류된다:

감지 기반 전이: 플레이어의 가시성(line-of-sight), 근접 거리, 청각 자극 등 NPC의 센서 입력에 기반한 전이
타이머 기반 전이: 특정 상태에서 일정 시간이 경과하면 발생하는 시간 구동(time-driven) 전이
이벤트 기반 전이: 체력 감소, 아이템 획득, 외부 명령 등 게임 내 이벤트에 의한 비동기 전이
확률 기반 전이: 비결정론적 행동을 도입하기 위한 난수(random number) 기반 전이

3.3 구현 패턴

초기 게임 AI에서 FSM은 일반적으로 다음의 두 가지 구현 패턴을 따랐다.

열거형 기반 switch-case 구현. 상태를 정수 또는 열거형(enumeration)으로 표현하고, 매 프레임의 갱신 루프에서 switch-case 분기를 통하여 현재 상태에 해당하는 행동 논리를 실행한다. 이 방식은 구현이 간결하고 실행 속도가 빠르나, 상태 수 증가 시 switch-case 블록의 크기가 비례하여 증가하며, 전이 논리가 행동 논리와 혼재되어 가독성이 저하된다.

enum State { PATROL, CHASE, ATTACK, FLEE };
State currentState = PATROL;

void update() {
    switch(currentState) {
        case PATROL:
            patrol();
            if (playerVisible()) currentState = CHASE;
            break;
        case CHASE:
            chase();
            if (inAttackRange()) currentState = ATTACK;
            if (!playerVisible()) currentState = PATROL;
            break;
        case ATTACK:
            attack();
            if (healthLow()) currentState = FLEE;
            break;
        case FLEE:
            flee();
            if (reachedSafePoint()) currentState = PATROL;
            break;
    }
}

상태 전이 테이블 기반 구현. 상태와 입력의 조합에 대한 전이 결과를 2차원 배열(transition table)로 사전 정의하고, 현재 상태와 입력 이벤트로 테이블을 색인하여 다음 상태를 결정한다. 이 방식은 전이 논리와 행동 논리의 분리를 달성하며, 전이 규칙의 일괄 수정이 용이하나, 복합 조건에 의한 전이를 단일 입력으로 사상(mapping)하는 전처리가 필요하다.

4. 년대 FSM 기반 게임 AI의 발전

4.1 Doom (1993)과 Quake (1996)의 NPC 행동 제어

id Software의 Doom(1993)에서 적 NPC는 대기(Idle), 각성(Alert), 추적(Chase), 공격(Attack), 고통(Pain), **사망(Death)**의 상태로 행동을 관리하였다. 각 상태의 갱신 논리와 전이 조건은 게임 엔진 내부에 직접 구현되었으며, 적 유형별로 상이한 전이 조건 임계값(예: 공격 거리, 공격 주기)이 데이터 테이블로 분리되어 다양한 적 행동 패턴을 생성하였다.

Quake(1996)에서는 QuakeC 스크립팅 언어가 도입되어, NPC의 FSM 논리를 엔진 외부의 스크립트로 정의할 수 있게 되었다. 이는 FSM 기반 게임 AI 설계에서 행동 논리의 데이터 구동(data-driven) 분리가 산업적으로 실현된 초기 사례이다.

4.2 Half-Life (1998)의 복합 행동 FSM

Valve Corporation의 Half-Life(1998)는 FSM 기반 게임 AI의 산업적 정점으로 평가된다. 전투원(HECU Marine) NPC는 다음의 상태 집합을 보유하였다:

순찰(Patrol): 지정된 경로를 따라 이동
경보(Alert): 의심스러운 자극을 감지하여 경계 상태로 진입
탐색(Search): 플레이어의 마지막 알려진 위치를 향하여 탐색
전투(Combat): 플레이어와 교전, 엄폐·측면 공격·수류탄 등 전술 행동 포함
후퇴(Retreat): 체력 저하 시 후퇴 및 재집결

Half-Life의 FSM 설계에서 주목할 점은, 전투 상태 내부에 엄폐(cover), 측면 기동(flank), 수류탄 투척(grenade) 등의 하위 행동이 내포됨으로써, 사실상 계층적 FSM(HFSM)의 초기 형태가 비형식적으로 구현되었다는 것이다. 이는 단일 수준 FSM의 표현력 한계를 인식하고 계층적 분해를 시도한 산업적 사례이다.

5. FSM이 초기 게임 AI에 적합했던 요인

FSM이 초기 게임 AI의 지배적 행동 제어 기법으로 채택된 요인은 다음과 같이 정리된다.

계산 효율성. FSM의 상태 전이 연산은 조건 평가와 상태 변수 갱신으로 구성되며, $O(1)$ 의 시간 복잡도를 가진다. 이는 프레임당 수 밀리초의 AI 예산(AI budget)만 허용되는 실시간 게임 환경에서 결정적 이점이었다.

직관적 설계 모델. NPC의 행동을 “상태“와 “상태 간 전환“으로 개념화하는 것은 인간의 직관과 부합하며, 게임 디자이너가 NPC의 행동 패턴을 상태 전이도(state transition diagram)로 시각적으로 설계할 수 있었다.

결정론적 행동 보장. FSM은 동일 입력에 대하여 동일 전이를 수행하므로, NPC 행동의 재현성(reproducibility)이 보장된다. 이는 게임 테스트와 디버깅에 있어 필수적 요소이다.

제한된 행동 복잡도와의 부합. 초기 게임의 NPC 행동은 소수의 이산적 행동 모드(3~6개 상태)로 충분히 표현 가능하였으며, 이 규모에서 FSM의 구조적 한계는 아직 발현되지 않았다.

6. 초기 게임 AI FSM 설계의 구조적 특징과 제약

초기 게임 AI의 FSM 설계는 다음의 구조적 특징을 공통적으로 보유한다.

단일 수준 평면 구조. 대부분의 초기 구현은 계층적 분해 없이 모든 상태를 단일 수준에 배치하였다. 이는 구현의 단순성을 보장하였으나, NPC 행동의 정교화에 대한 확장성을 원천적으로 제한하였다.

전역 전이 규칙의 부재. 모든 상태에 공통적으로 적용되어야 하는 전이(예: 사망 처리)가 각 상태에서 개별적으로 중복 정의되었다. 이는 상태 수 증가 시 유지보수 부담을 가중시키는 요인이 된다.

행동 논리와 전이 논리의 혼재. switch-case 구현 패턴에서 상태 내부의 행동 실행 코드와 전이 조건 평가 코드가 동일 코드 블록에 혼재됨으로써, 관심사의 분리(separation of concerns)가 달성되지 않았다.

이러한 특징은 행동 복잡도가 낮은 초기 게임에서는 문제가 되지 않았으나, 2000년대 이후 NPC 행동의 복잡도가 급증함에 따라 FSM 기반 설계의 구조적 한계가 본격적으로 노출되는 원인이 되었다.

7. 참고 문헌

Millington, I., & Funge, J. (2009). Artificial Intelligence for Games (2nd ed.). Morgan Kaufmann.
Buckland, M. (2005). Programming Game AI by Example. Wordware Publishing.
Champandard, A. J. (2003). AI Game Development: Synthetic Creatures with Learning and Reactive Behaviors. New Riders.
Pittman, J. (2009). “The Pac-Man Dossier.” Gamasutra.
Harel, D. (1987). “Statecharts: A Visual Formalism for Complex Systems.” Science of Computer Programming, 8(3), 231–274.

v0.2.0