엘든 링(Elden Ring)의 로우테크(Low-Tech) AI

FROMSOFT는 Soulsborne 확장 시리즈 전반에 걸쳐 다양하고 가혹한 NPC 조우(encounter)를 제공하는 것으로 명성이 높지만, AI 의사결정(decision making) 자체의 구현 방식은 아마도 예상외로 로우테크(low-tech)일 것입니다. 코드의 대부분이 Havok Script(Havok에서 만든 게임 지향적 Lua 구현체)로 구현되어 있기 때문에, 안개 벽 너머를 들여다보며 이들이 어떻게 구현되었는지 확인하는 것은 꽤 쉽습니다.

다음에 이어지는 내용은 독창적인 연구가 아니며, 저는 다른 사람들이 추출(extracting), 디컴파일(decompiling), 역공학(reversing)하는 힘든 작업을 수행해 놓은 코드를 읽고 있을 뿐이라는 점을 참고해 주세요.

목표 (Goals)

FROMSOFT AI 방식의 주요 도구는 Goal(목표)이며, 이는 AI가 가질 수 있는 고유한 상태(state)를 지칭하는 그들만의 용어입니다. Goal은 인스턴스화(instantiated)될 때 매개변수화(parametrized)될 수 있으며, 액터(Actor) 자체에 저장된 데이터에 접근할 수 있지만, 그 외에는 단순히 함수들의 불변 테이블(immutable table)에 불과합니다.

가장 간단한 옵션은 상태들을 유한 상태 머신(Finite State Machine, FSM)이나 계층적 유한 상태 머신(Hierarchical Finite State Machine)으로 구성하는 것이겠지만, FROMSOFT는 한 단계 더 나아가 시스템에 상태 스택(stack of states)을 부여합니다. 이를 통해 시스템은 FSM에서 푸시다운 오토마타(Pushdown Automaton, PDA)로 전환됩니다.

이는 완전히 추상적인 정의이므로, 위키피디아에서 돌아온 후에는 위에서 아래로 구체적으로 이야기해 보겠습니다.

매 프레임마다 액터(Actor)들은 자신의 Goal 스택 최상단에 있는 Goal을 업데이트합니다. Goal이 업데이트될 때, 스택에 더 많은 Goal을 하위 목표(Sub-Goals)로서 푸시(push)할 수 있으며, 그중 최상단에 있는 것이 다음 프레임에 실행됩니다. Goal의 업데이트 함수는 Continue(계속), Success(성공), 또는 Failure(실패)를 나타내는 값을 반환합니다. Continue는 스택을 변경하지 않은 채로 남겨두고, 나머지 두 가지는 해당 Goal이 스택에서 팝(pop)되도록 만듭니다. Failure는 추가적으로 실행되지 않은 다른 모든 Goal들을 부모 Goal(이 하위 목표를 푸시한 Goal)까지 스택에서 팝(pop)시킵니다.

예를 들어, 우리는 CoolBossBattle이라는 Goal을 정의할 수 있으며, 실행 과정 중에 일련의 Attack을 푸시할 수 있습니다.

하위 목표 (Sub-Goals). 해당 공격들.

목표 (Goals)는 다양한 수단으로 매개변수화 (parameterized)될 수 있지만, 가장 주요한 수단은 애니메이션 ID (animation id)입니다.

[ GOAL STACK ]
3: Attack (R2, Combo) <<<<-- 현재 업데이트 중
2: Attack (R2, Repeat)
...

몇 초 후 첫 번째 공격이 명중하면, 해당 목표는 성공적으로 완료되어 스택 (stack)에서 팝 (pop) 됩니다. 하지만 다음 공격이 실패하면, 스택은 부모(parent)로 언와인드 (unwind) 됩니다.

[ GOAL STACK ]
2: Attack (R2, Repeat) <<<<-- 실패함, 스택에서 팝 될 예정.
1: Attack (R2, Finisher) <<<<-- 이 또한 제거될 예정.
...

시도했던 공격 콤보가 종료되었으므로, 이제 다음 행동을 선택할 준비를 합니다.

[ GOAL STACK ]
2: Attack(L1)
1: Attack(L1)
...

그리 복잡하지는 않습니다!

그들의 API에서는 이 스택의 루트 (root)를 “최상위 목표 (Top Level Goal)”라고 부르는데, 제가 현재 실행 중인 목표를 스택의 “top”이라고 지칭함으로써 혼란을 드렸습니다. 따라서 이 둘은 서로 다른 것이라는 점을 유념해 주세요.

활성화 (Activate)

목표 (Goals)는 콜백 (callback)으로 사용되는 몇 가지 함수로 정의되며, 가장 많은 AI 로직을 포함하는 함수는 대개 activate입니다. 이 함수는 목표가 처음 업데이트될 때, 그리고 목표가 자신의 하위 목표 (Sub-Goals)를 모두 소진하고 다시 실행을 시작할 때마다 호출됩니다.

보스 및 일반 NPC 목표의 경우, Activate 내의 코드는 월드 (world)와 액터 (Actor)의 컨텍스트 (context) 및 무작위성 (randomness, 이 또한 액터 자체에서 발생)을 혼합하여 액터가 취할 다음 행동을 선택하는 역할을 담당합니다.

가장 널리 사용되는 방식은 공통 코드를 사용하여 여러 행동 (Actions, 이는 단순한 함수임) 사이에서 가중치 기반 무작위 선택 (weighted random selection)을 수행하고, 당첨된 행동을 호출하는 방식입니다.

우리의 CoolBossBattle로 돌아가서,

이번에는 약간의 Rusty 의사코드 (pseudocode)로 살펴보겠습니다...

fn action_giga_death_ray(goals: &Goals, actor: &Actor) {
todo!();
}
...

가중치를 동적으로 수정하는 것은 다양한 방식으로 처리되지만, 가장 일반적인 방법은 액터로부터의 단순한 RNG 굴리기 (rng rolls)와 HP 임계값 (hp thresholding) 설정입니다.

최상위 전투 목표 (battle Goal)보다 더 단순한 다른 목표 (Goals)들은 아마도 목표 파라미터 (Goal parameters)에서 일부 데이터를 읽어오는 방식으로 몇 가지 하위 목표 (sub-goals)를 밀어넣을 수 있습니다. 이러한 중첩 (nesting) 구조는 단순한 빌딩 블록 (building blocks)으로부터 상당히 복잡한 행동을 구성하는 것이 가능하다는 것을 의미합니다.

인터럽트 (Interrupts)

목표 (goals)를 위해 정의된 또 다른 주요 콜백 (callback)은 인터럽트 (Interrupt)입니다. 이름에서 알 수 있듯이, 이는 목표 (Goals)가 주로 액터 (Actor) 자체에 설정된 외부 이벤트에 즉각적으로 반응할 수 있도록 합니다.

제가 이해하기로는 인터럽트는 버블 업 (bubble up) 됩니다. 즉, 현재 실행 중인 목표 (Goal)에서 인터럽트를 실행한 다음, 목표 (Goals)가 더 이상 없거나 인터럽트 콜백 중 하나가 인터럽트를 소비했음을 나타내기 위해 true를 반환할 때까지 부모 목표들로 재귀적으로 실행됩니다.

예를 들어, 만약 제가 CoolBoss에게 불이 붙자마자 격렬한 공격 상태로 전환되기를 원한다면, 다음과 같은 것을 구현할 수 있습니다.

fn interrupt(&self, goals: &Goals, actor: &Actor, interrupt: Interrupt) {
match interrupt {
// 만약 내가 불타기 시작하면, 공격하라!
...

이것은 정말 사악한 기능들을 구현하는 데 사용됩니다. 예를 들어, 황금 나무의 그림자 (Bell Bearing Hunter)는 플레이어가 주문을 시전하거나 아이템을 사용하는 것을 감지하며, 그 시점부터 현재 행동을 즉시 중단하고 공격을 개시할 확률이 85%에 달합니다.

그들은 또한 액터 (Actors)에 설정된 동적 공간 감시 영역 (dynamic spatial watch regions)을 활용하며, 이는 인터럽트 (interrupts)를 트리거합니다. 예를 들어, 보스의 뒤쪽이나 아래쪽 영역에 대한 감시를 추가하여, 플레이어가 영리하게 행동하려 할 때 보스의 행동을 즉시 적응하도록 사용할 수 있습니다.

타임아웃 (Timeouts)

목표 (Goals)는 개별 상태 외에도 초 단위의 수명 (lifetime) 값을 가집니다. 이는 어떤 이유로든 갇혀버린 상태에서 벗어나는 데 사용되며, 수명 (lifetime)은 주로 버그 억제 메커니즘 (bug containment mechanism)으로 사용되는 것으로 보입니다.

또한 실행 중에 부모 목표 (parent goal)의 수명을 수정하여 지속적인 전진 진행 (forward progress)을 나타내는 것도 가능합니다.

액터 데이터 액세스 (Actor Data Access)

많은 AI 의사결정 시스템에서 여러분은 "블랙보드 (blackboards)"와 같은 화려한 데이터 저장 시스템에 대해 들어보셨을 것입니다. Souls 게임에서는 각 액터 (Actor)에 부동 소수점 (float) 배열이 있으며, 이는 인덱스에 따라 목표 (Goals)에 의해 임의로 설정되고 읽힙니다. 제 생각에 이 정도면 충분해 보입니다!

앞서 언급하지 않은 콜백 (callback)인 Initialise는 액터 (Actor)에 새로운 최상위 목표 (Top Level Goal)가 할당될 때 이 데이터를 초기화하는 데 흔히 사용됩니다.

목표 (Goals)는 액터 (Actor)를 통해 세계에 대한 다양한 쿼리 (queries)에 접근할 수 있습니다. 제가 파악한 바로는 성능 관점에서 이들 대부분은 꽤 "저비용 (low cost)"입니다. 어그로 (Aggro)와 타겟팅 (Targeting)은 외부에서 처리되는 것으로 보이므로, 모든 것이 인터프리터 방식의 루아 (Lua)로 실행된다는 점을 고려하더라도 목표 (Goals)를 매우 가볍게 유지하는 것이 가능할 것입니다.

실제 수행 작업 (Actual Doing Stuff)

제가 완전히 건너뛴 부분은 목표 (Goals)가 실제로 어떻게 일을 "수행 (Do)"하는가 하는 점입니다. 대부분의 경우 FROMSOFT 게임의 모든 것은 애니메이션 주도 (animation driven) 방식입니다.

목표 (Goal)가 "이 공격 애니메이션을 재생하라"고 명령하면, 애니메이션 이벤트 (animation events)가 히트박스 (hitbox) 정보와 타이밍, 특수 효과 트리거 (special effect triggers), 투사체 생성 이벤트 (projectile creation events) 등을 전달합니다. 또한 다양한 "콤보 (combo)" 기능도 있는데, 이는 콤보 공격 중에 체인 애니메이션 (chained animation)을 더 빠르게 연결할 수 있도록 애니메이션 내에서 다른 이벤트 세트를 선택하는 것으로 요약되는 것 같습니다.

어느 시점에 그들은 Havok 미들웨어 (middleware)에 전적으로 의존하게 되었습니다. 애니메이션은 Havok Animation Studio (단종)로 제작됩니다. 앞서 AI 스크립트가 Havok Script (역시 단종)를 사용한다고 언급했습니다. 물리 (Physics)는 Havok의 물리 엔진에 의해 처리되며, 경로 탐색 (pathfinding)은 Havok AI (단종되지는 않았으나 Havok Navigation으로 이름이 변경됨)에 위임됩니다.

기타 사항 (Misc Stuff)

그들은 AI 스크립팅을 "로직 (logic)" 스크립트와 "전투 (battle)" 스크립트로 나누는 것으로 보입니다. 여기서 로직 스크립트는 훨씬 더 공유 가능하며, 전투 스크립트는 종종 맞춤형 (bespoke)으로 제작됩니다. 이는 매우 영리한 방식으로 보입니다. 이 두 가지를 하나의 계층 구조 (hierarchies)에 억지로 밀어 넣으려 할 때 문제가 발생하는 경우가 흔하기 때문입니다.

레벨 디자이너들은 레벨 자체에서 액터(Actor)의 최상위 목표(Top Level Goal)를 설정할 수 있습니다. 따라서 일부 적들을 일반적인 전투 목표(combat Goal) 대신 수동적인 목표(passive Goal)를 가진 상태로 배치할 수 있으며, 이들은 다른 기능은 정상적으로 작동하면서 그저 쉬고 있게 할 수 있습니다.

대부분의 일반적인 코드는 비교적 컴팩트한 Lua 조각들로 이루어져 있지만, 제가 믿기로는 Attack 및 MoveToSomewhere와 같이 핵심적인 역할을 하는 목표(Goals)들은 C++로 구현되어 있습니다. 이는 스크립트 작성 가능성(scriptability)과 성능의 안정성(performance sanity) 사이에서 꽤 괜찮은 균형을 제공합니다. 업데이트(update) 함수 자체는 때때로 조건을 확인하는 데 사용되는데, 이로 인해 가끔 문제가 발생했을 것으로 예상됩니다. 하지만 스크립팅에서 액터(Actors)를 위한 인터페이스가 얇게(thin) 유지되는 한, 제어 가능한 수준을 유지할 수 있을 것입니다. (경로 탐색(pathfind) 함수 호출을 추가하지 마세요...)

저는 높은 수준의 조우 로직(encounter logic)과 레벨 스크립팅에 사용되는 이벤트 스크립팅 시스템은 완전히 건너뛰었습니다. AI와 달리 이 시스템은 매우 제한적인 가상 머신(VM)을 사용하는 완전히 커스텀된 방식인 것으로 보입니다. 그렇기는 하지만, Lua가 아니기 때문에 실제로 어떻게 작성되는지 파악하기는 어렵습니다. 혹시 그들의 툴링(tooling)에 관한 정보를 얻을 수 있는 1차 자료를 아시는 분이 있다면 정말 멋질 것 같습니다!

결론

복잡한 AI 시스템(GOAP가 떠오르네요)에 대한 지속적인 열광이 많지만, 디자이너와 애니메이터의 손에 많은 제어권을 넘겨주는 방식의 성공은 그 자체로 많은 것을 말해준다고 생각합니다.

푸시다운 오토마타(Pushdown Automaton)는 행동 트리(Behavior Trees)나 플래너(planners)와 비교했을 때 근본적으로 상당히 빠릅니다. 행동 트리(Behavior Trees)는 종종 스크립트된 노드들의 복잡한 트리를 하향식(top-down)으로 재평가해야 하는 반면, 이 방식은 거의 항상 스택의 최상단에 있는 단일 목표(Goal)를 실행합니다. STRIPS, GOAP, HTN과 같은 플래너(Planners)는 모든 과정의 중간에 비용이 많이 드는 탐색(search) 과정을 추가합니다.

유한 상태 기계(FSMs)와 비교했을 때, 동적 전이(dynamic transitions)의 유연성은 상태(states)와 전이(transitions)의 수가 폭발적으로 증가하는 것을 피하기 쉽게 만들어 줍니다. 이는 또한 명령형(imperative) 방식으로 AI 기능을 구성하는 것을 훨씬 더 합리적으로 만들어 줍니다.

물론, 이는 개별 행동이 전투 디자이너의 손을 벗어나는 플래너 기반 솔루션보다 훨씬 더 가독성이 높다는 장점이 있습니다.

일반적인 Soulsborne NPC나 보스전보다 더 복잡한 시나리오를 처리할 수 있을까요? 저는 실제로 충분히 멀리 갈 수 있다고 생각합니다.

업데이트

일부 hackernews 댓글 작성자들은 BT(Behavior Tree)와의 비교에 혼란을 느꼈고, 이 방식이 활성 노드 스택을 유지하는 이벤트 기반 BT와 매우 유사하다고 지적하며 '정상적인' 게임 AI와 비교했을 때의 복잡성에 대해 의문을 제기했습니다. 제가 그 모든 것을 설명할 때 다소 건성으로 처리했기 때문에 조금 더 자세히 설명해 보겠습니다.

첫째, 이벤트 기반 BT가 전체 트리를 탑다운(top-down) 재실행해야 하는 요구 사항을 피하는 것은 사실이지만, 모든 BT 구현이 실제로 그렇게 작동하는 것은 아닙니다! 특히 학술적이고 초기 사용자들의 사례는 좀 더 순진한(naive) 구현과 비슷합니다. 저는 실행 구조를 명시적으로 표현하고 이를 명령형 코드(imperative code)로 구축하는 여기의 접근 방식이 BT 위에 일종의 실행 경로 캐시를 덧붙이려는 것보다 훨씬 더 간단하다고 생각합니다.

둘째, 복잡성에 대한 더 넓은 질문과 관련하여, BT는 노드 내부에 제어 흐름 구조(control flow structures)를 구현합니다 (다시 말해, 특히 학술적 구현에서). 이것이 바로 '조건(Conditions)', '순서(Sequences)', '선택자(Selectors)', '병렬(Parallels)'과 같은 BT 용어가 존재하는 이유입니다. 이는 트리의 크기를 상당히 부풀리며, 저의 (제한적인! 저는 AI 프로그래머가 아닙니다) 경험상 이를 작성하는 복잡성을 높입니다. 비교하자면, FROMSOFT 스타일은 오늘날에도 극도로 낮은 상태 카운트(state count)를 가지며, 제어 흐름의 대부분을 구현하기 위해 해당 상태 내부의 명령형 코드에 의존합니다. 이는 성능 관점에서 볼 때, 너무 많은 로직이 작성 및 실행 중에 관리하기 어려운 복잡한 트리 구조에 갇히는 '천 개의 칼날로 인한 죽음(death-by-a-thousand-cuts)' 스타일의 문제를 피하는 데 엄청나게 중요합니다.

마지막으로, 대규모 게임의 경우 이곳의 코드 양은 그저 적은 수준입니다. FROMSOFT는 (사실상 각 보스당 하나 이상씩) 상대적으로 많은 수의 맞춤형 행동 (bespoke behaviors)에 의존하지만, 이러한 행동들은 다른 대형 AAA 게임에서 기대할 수 있는 그 어떤 것과 비교해도 상당히 작습니다. 다른 곳의 실제 제작 환경(production)에서 사용되는 행동 트리 (BTs)라면, 제어 흐름 (control flow)과 액션 (actions)을 구현하는 수백 개의 개별 노드 외에도 수만 개의 노드로 구성된 트리 구조를 보더라도 놀랍지 않을 것입니다. 마찬가지로, 액터 (Actors) 상의 데이터 모델 (data model) 측면 또한