유한 상태 기계

게임 개발 소프트웨어 시뮬레이션 마지막 수정: 2026-07-18 04:57:58

1. 개요[편집]

유한 상태 기계 Finite State Machine
약칭	FSM
분야	게임 AI · 제어 · 계산이론
구성 요소	상태 · 전이 · 이벤트
확장	계층적 FSM(HFSM)
대체 경쟁자	행동 트리, 유틸리티 AI

상태가 셋일 땐 세상에서 제일 쉽고, 스물일 땐 세상에서 제일 무섭다.

유한 상태 기계(Finite State Machine, FSM)는 시스템이 가질 수 있는 유한한 개수의 상태(state)와, 그 상태들 사이를 오가는 전이(transition)로 동작을 기술하는 계산 모델이다. 어느 순간에도 시스템은 정확히 하나의 상태에 있고, 특정 이벤트나 조건이 만족되면 다른 상태로 넘어간다. “지금 무엇을 하고 있는가”를 상태로, “언제 다른 걸 하는가”를 전이로 나눠 생각하는 이 단순한 틀은 게임 AI, 제어 로직, 통신 프로토콜, 컴파일러의 어휘 분석까지 컴퓨터 과학 전반에 스며 있다.

게임 개발자에게 FSM은 가장 먼저 배우는 AI 도구다. 경비병 NPC를 “순찰 → 추격 → 공격 → 도주”라는 네 상태로 그리고, “적을 보면 순찰에서 추격으로” 같은 화살표를 몇 개 긋는 것으로 그럴듯한 행동이 나온다. 애니메이션 상태 기계(Unity의 Animator, Unreal의 AnimGraph)도 걷기·달리기·점프를 상태로 두고 파라미터로 전이시키는 FSM이다.¹

2. 상태, 전이, 그리고 액션[편집]

FSM을 형식적으로 적으면 다섯 요소의 튜플이다.

M = (Q,\; \Sigma,\; \delta,\; q_0,\; F)

여기서 $Q$ 는 상태 집합, $\Sigma$ 는 입력(이벤트) 집합, $\delta: Q \times \Sigma \to Q$ 는 전이 함수, $q_0$ 는 시작 상태, $F$ 는 종료 상태 집합이다. 게임 AI에서는 종료 상태 $F$ 가 별 의미 없고, 대신 각 상태에 무엇을 할지를 붙이는 방식이 중요해진다. 이 “무엇을 하는가”를 어디에 붙이느냐로 두 고전 모델이 갈린다.

무어 기계(Moore machine) — 출력이 현재 상태에만 의존한다. “추격 상태에 있으면 플레이어를 향해 달린다”처럼 상태가 곧 행동이다.
밀리 기계(Mealy machine) — 출력이 상태와 입력의 조합에 의존한다. 전이가 일어나는 그 순간에 행동을 낸다.

게임 실무의 FSM은 대개 상태에 진입 시(enter)·매 프레임(update)·이탈 시(exit) 콜백을 다는 하이브리드 형태다. 문 앞에 도착하면 enter에서 문 열기 애니메이션을 트리거하고, update에서 통과를 감시하고, 다 지나가면 exit에서 정리하는 식이다.

3. 결정적 FSM과 비결정적 FSM[편집]

계산이론 쪽으로 한 발 들어가면 FSM은 두 종류로 갈린다. 결정적 유한 오토마타(DFA)는 어떤 상태에서 어떤 입력을 받아도 갈 곳이 정확히 하나로 정해진다. 비결정적 유한 오토마타(NFA)는 같은 입력에 대해 여러 상태로 동시에 갈 수 있거나, 입력 없이도 전이( $\varepsilon$ -전이)할 수 있다.

직관적으로 NFA가 더 세 보이지만, 유명한 결과 하나가 이 둘을 화해시킨다. 모든 NFA는 그와 동치인 DFA로 변환할 수 있다(부분집합 구성법). 즉 표현력은 같고, 다만 DFA로 펼치면 상태 수가 최악의 경우 지수적으로 불어날 수 있다. FSM이 인식하는 언어의 집합이 곧 정규 언어(regular language)이고, 정규표현식(regex) 엔진 내부가 바로 이 오토마타로 돌아간다.²

이 이론적 한계는 게임 AI에도 그대로 적용된다. FSM은 상태의 “기억”이 현재 상태 하나뿐이라, 카운팅이나 중첩 같은 걸 못한다. 그래서 복잡한 조건을 다루려면 상태를 쪼개 늘리는 수밖에 없고, 여기서 그 악명 높은 상태 폭발이 시작된다.

4. 상태 폭발과 계층적 FSM[편집]

FSM의 아킬레스건은 전이의 폭발이다. 새 상태 하나(“재장전”)를 넣으려면 원칙적으로 기존 모든 상태에서 그리로 들어가고 나오는 전이를 다 그려야 한다. 상태 $n$ 개짜리 완전 연결 FSM의 전이 수는 최악의 경우

|T| = O(n^2)

로 늘어난다. 상태 스물을 넘긴 다이어그램은 스파게티가 되고, 유지보수하던 사람이 조용히 이직을 알아보는 광경은 이 바닥의 전통이다.³

첫 번째 처방이 계층적 유한 상태 기계(Hierarchical FSM, HFSM)다. 상태를 묶어 상위 상태(superstate)를 만들고, 공통 전이를 그 상위 레벨에 한 번만 그린다. 예컨대 “전투” 상위 상태 안에 추격·공격·엄폐를 넣고, “체력 0이면 사망으로” 전이를 전투 전체에 딱 하나 걸면, 하위 상태마다 사망 화살표를 그릴 필요가 없다. UML의 상태차트(statechart)가 이 계층·이력(history)·직교 영역을 형식화한 대표적 확장이다.

5. 행동 트리·유틸리티 AI와의 비교[편집]

HFSM으로도 감당이 안 될 만큼 행동이 많아지면, 업계는 행동 트리(Behavior Tree)로 넘어갔다. 행동 트리는 상태 간 전이를 아예 없애고 트리 구조가 우선순위를 결정하게 만들어, FSM의 $O(n^2)$ 전이 지옥을 회피한다. 반응성이 공짜로 따라오고 서브트리를 재사용하기 좋다는 것이 강점이다.

또 다른 대안이 유틸리티 AI로, 상태를 명시적으로 전이시키는 대신 각 행동에 점수(효용)를 매겨 가장 높은 걸 고른다. FSM이 “규칙으로 정한 전이”라면 유틸리티 AI는 “매 순간 저울질”이다. 셋의 성격을 거칠게 대비하면 다음과 같다.

모델	결정 방식	강점	약점
FSM	상태·전이 규칙	단순·직관·디버그 쉬움	상태 폭발
행동 트리	트리 우선순위	모듈성·반응성	블랙보드 남용
유틸리티 AI	효용 점수	부드러운 선택	튜닝·설명성

그렇다고 FSM이 퇴물이 된 건 아니다. 상태가 적고 명확한 문제라면 FSM만큼 짜기 쉽고 버그 잡기 좋은 것도 없다. 실제로 현대 게임은 상위 판단은 행동 트리로, 애니메이션이나 캐릭터의 국소 상태는 FSM으로 굴리는 식으로 둘을 섞어 쓴다. 내비게이션 메시로 길을 찾고, 그 위에서 FSM이 이동 상태를 관리하는 조합도 흔하다.⁴

6. 관련 문서[편집]

애니메이션 상태 기계는 게임 프로그래머가 가장 자주 만지는 FSM이다. Blend Tree까지 얹으면 “달리기 상태” 안에서 속도에 따라 걷기·조깅·전력질주를 섞는 이중 구조가 된다. 상태 안에 또 상태가 있는 셈이라 사실상 소형 HFSM이다. ↩
정규표현식을 컴파일하면 보통 NFA를 먼저 만들고(톰슨 구성), 성능을 위해 DFA로 변환한다. 즉 우리가 매일 쓰는 grep과 검색창 뒤에는 유한 상태 기계가 돌고 있다. 다만 백레퍼런스 같은 일부 기능은 정규 언어를 넘어서서 순수 FSM으로는 처리되지 않는다. ↩
이 $O(n^2)$ 스파게티가 바로 행동 트리가 등장하게 된 직접적 동기다. 상태를 늘릴 때마다 전이를 제곱으로 그려야 하는 고통을, 트리 구조가 전이를 없애는 방식으로 풀어냈다. ↩
“이 NPC가 왜 벽 보고 서 있죠?”는 FSM이든 행동 트리든 유틸리티 AI든 결국 누군가는 답해야 하는 질문이다. 도구를 바꿔도 디버깅의 숙명은 남는다. 다만 FSM은 현재 상태 하나만 찍어보면 되니, 적어도 “어디서 멈췄는지”는 제일 알아내기 쉽다. ↩