행동 트리

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

1. 개요[편집]

행동 트리 Behavior Tree
약칭	BT
분야	게임 AI, 로보틱스 제어 구조
대중화	Halo 2 (2004)
노드 종류	Composite, Decorator, Leaf
반환 상태	Success / Failure / Running
대체 대상	유한 상태 기계(FSM)

행동 트리(Behavior Tree, BT)는 에이전트의 행동을 트리 구조로 조합하고, 매 갱신마다 루트에서 신호(tick)를 내려보내 지금 무엇을 할지 결정하는 AI 제어 구조다. 각 노드는 틱을 받으면 성공(Success)·실패(Failure)·진행 중(Running) 세 상태 중 하나를 부모에게 돌려주고, 부모는 그 결과를 보고 다음 자식으로 넘어갈지 멈출지를 정한다. 이 단순한 규약만으로 “적을 보면 쫓고, 체력이 낮으면 도망치고, 아무 일 없으면 순찰한다” 같은 우선순위 행동이 조립된다.

게임 AI에서 오랫동안 표준이었던 유한 상태 기계(FSM)를 밀어내고 사실상의 국룰 자리를 차지했으며, 최근에는 게임을 넘어 로보틱스 쪽에서도 널리 쓰인다.¹ Havok Behavior, Unreal Engine의 Behavior Tree, ROS 2 Nav2의 BehaviorTree.CPP 등이 대표적인 구현체다.

2. FSM은 왜 무너졌나[편집]

유한 상태 기계는 상태(순찰·추격·공격·도주)를 노드로, 전이(transition)를 화살표로 그리는 방식이다. 상태가 셋일 때는 세상에서 제일 직관적이다. 문제는 상태 하나를 추가할 때 발생한다.

새 상태 “재장전”을 넣으려면, 기존 모든 상태에서 재장전으로 들어가는 화살표와 재장전에서 나오는 화살표를 다 그려야 한다. 상태 $n$ 개짜리 FSM의 전이 개수는 최악의 경우

|T| = O(n^2)

로 늘어난다. 이걸 실무에서는 스파게티 상태 기계라고 부르며, 상태 20개짜리 FSM 다이어그램을 물려받은 신입이 퇴사를 고민하는 광경은 이 바닥의 전통 행사다.²

행동 트리의 처방은 전이를 없애는 것이다. 노드는 자기 부모 말고는 누구도 모른다. “이 다음에 어디로 가는가”는 노드가 아니라 트리의 구조가 결정한다. 그래서 서브트리를 잘라서 다른 트리에 붙여도 그대로 동작한다. FSM이 goto라면 BT는 함수 호출인 셈이다.

3. 노드 종류[편집]

3.1. Composite (조합 노드)[편집]

자식을 여럿 갖고 순서를 조율하는 노드. 실질적으로 이 둘이 전부다.

Sequence (→) — 자식을 왼쪽부터 실행. 하나라도 실패하면 즉시 Failure, 전부 성공하면 Success. 논리 AND에 대응한다. “문 앞으로 이동 → 문 열기 → 통과”처럼 순서가 있는 절차에 쓴다.
Selector / Fallback (?) — 자식을 왼쪽부터 실행. 하나라도 성공하면 즉시 Success, 전부 실패하면 Failure. 논리 OR에 대응한다. “도망 시도 → 안 되면 엄폐 → 안 되면 그냥 싸운다”처럼 우선순위 대안에 쓴다.
Parallel — 자식을 동시에 틱. 성공 조건은 정책(전부/하나/N개)으로 정한다. 실제로는 진짜 병렬이 아니라 한 틱 안에서 전부 순회하는 것뿐이다.

Selector를 위에 두고 왼쪽에 급한 행동을 배치하는 것이 우선순위 표현의 국룰이다. 왼쪽이 곧 우선순위다.

3.2. Decorator (장식 노드)[편집]

자식 하나를 감싸서 결과나 실행 여부를 바꾸는 노드. Inverter(성공↔실패 뒤집기), Repeater(N번 반복), Succeeder(무조건 성공), Cooldown(쿨타임 동안 실패), Retry, Timeout 등이 있다. Unreal에서는 Decorator가 조건 검사 겸 중단(abort) 트리거 역할까지 맡는다.

3.3. Leaf (말단 노드)[편집]

실제로 뭔가 하는 노드. Action(이동, 발사, 애니메이션 재생)과 Condition(체력 < 30%인가?)으로 나뉜다. 게임 로직이 실제로 사는 곳은 오직 여기이고, 나머지 노드는 전부 배선일 뿐이다.

4. 틱과 Running 상태[편집]

BT를 FSM과 갈라놓는 진짜 핵심은 세 번째 반환값 Running이다.

행동은 대개 한 프레임에 안 끝난다. “문까지 걸어간다”는 3초짜리다. Leaf는 이럴 때 Running을 돌려주고, 부모는 Running을 그대로 위로 전파하며, 루트는 이번 틱을 여기서 끝낸다. 다음 프레임에 루트가 다시 틱을 내려보내면 그 노드가 이어서 실행된다.

여기서 두 가지 스타일이 갈린다.

완전 재순회(stateless) 방식 — 매 틱 루트부터 조건을 다시 다 검사한다. 그래서 “체력 낮음”이 참이 되는 순간 왼쪽 가지가 잡아채면서 진행 중이던 행동이 자동으로 취소된다. 반응성이 공짜로 따라온다는 게 BT의 최대 미덕.
메모리(memory) 방식 — Running이던 자식을 기억했다가 거기서 재개한다. 조건 재검사를 안 하니 싸지만, 반응성을 잃는다. Unreal은 여기에 이벤트 기반 갱신 + Decorator의 observer abort를 얹어 두 마리 토끼를 잡는 절충안을 택했다.³

노드 $n$ 개짜리 트리를 매 틱 완전 재순회하면 최악 $O(n)$ 이다. 에이전트가 수백 마리라면 이 상수가 꽤 아프기 때문에, 실무에서는 틱 주기를 프레임보다 느리게(예: 초당 5회) 잡거나 거리 기반으로 LOD를 거는 게 일반적이다. 군중 시뮬레이션에서는 아예 개체별 BT를 포기하고 통계적 모델로 내려가기도 한다.

5. 블랙보드[편집]

노드끼리는 서로를 모르는데, 그러면 “아까 본 적의 위치”는 어떻게 공유할까. 답은 블랙보드(blackboard)다. 에이전트마다 하나씩 붙는 키-값 저장소로, Condition 노드는 여기서 읽고 Action 노드는 여기에 쓴다.

블랙보드는 BT의 모듈성을 지탱하는 축이자 동시에 그 모듈성을 좀먹는 구멍이기도 하다. 사실상 전역 변수이기 때문에, TargetActor가 언제 누가 지웠는지 추적하다 보면 결국 스파게티가 트리 밖으로 새어 나온 것에 불과하다는 걸 깨닫게 된다.⁴

6. 게임 밖의 행동 트리[편집]

BT는 이제 게임 전용 기술이 아니다. 로보틱스에서 BT는 모듈성 있는 반응형 제어 구조로 정식 연구 대상이 되었고, BT가 서브섬션 아키텍처·결정 트리·순차 행동 조합 같은 기존 제어 구조들을 일반화한다는 것이 이론적으로 정리되었다.¹ ROS 2의 내비게이션 스택 Nav2는 경로 계획·복구 행동 전체를 BT로 기술하며, 드론·매니퓰레이터 작업 계획에서도 흔하다.

이유는 게임과 똑같다. 실패했을 때 복구 행동으로 자연스럽게 흘러가는 구조가 필요하고, 그걸 코드 수정 없이 XML 한 줄로 갈아 끼우고 싶기 때문이다. 로봇이 문을 못 열면 다른 경로를 찾고, 그것도 안 되면 사람을 부른다 — 그냥 Selector다.

7. 관련 문서[편집]

Colledanchise, M. & Ögren, P. (2018). Behavior Trees in Robotics and AI: An Introduction. 게임 업계가 현장에서 굴리며 다듬어온 물건을 학계가 뒤늦게 형식화한 사례다. 이런 방향의 지식 이동은 생각보다 드물지 않다. ↩ ↩²
게임 AI에서 BT를 널리 알린 것은 Bungie의 데미언 이슬라(Damian Isla)가 Halo 2의 AI 구조를 GDC 2005에서 발표하면서였다. 정확히는 BT라는 이름을 붙여 대중화한 쪽에 가깝고, 계층적 제어 구조라는 발상 자체는 그 전부터 여러 스튜디오에 있었다. ↩
“매 틱 전부 재검사”는 개념적으로 아름답지만 CPU 입장에서는 낭비다. Unreal의 이벤트 기반 BT는 블랙보드 값이 바뀔 때만 관련 Decorator를 깨우는 방식으로 이를 회피한다. 아름다움과 프레임 예산이 싸우면 늘 프레임 예산이 이긴다. ↩
그래서 요즘은 BT의 대안으로 유틸리티 AI(Utility AI)나 GOAP(Goal-Oriented Action Planning)를 섞는 하이브리드가 늘고 있다. 다만 어느 쪽을 고르든, 결국 마지막에는 누군가가 “이 NPC가 왜 벽을 보고 서 있죠?”라는 질문에 답해야 한다는 사실은 변하지 않는다. ↩