계획을 활용한 퀘스트 및 스토리 (번역)

제7장 계획을 활용한 퀘스트 및 스토리

원문 출처 : https://www.pcgbook.com/

Yun-Gyung Cheong, Mark O. Riedl, Byung-Chull Bae, Mark J. Nelson

 

요약

 

대부분의 게임은 어떤 형태의 서사를 포함한다. 게임 콘텐츠의 다른 측면과 마찬가지로, 스토리도 생성될 수 있다. 이 장에서는 주로 계획 알고리즘을 사용하여 스토리를 생성하는 방법을 논의한다. 플랜 공간에서 탐색하는 알고리즘과 상태 공간에서 탐색하는 알고리즘 모두가 이때 유용할 수 있다. 또한 스토리와 대응하는 게임 세계를 함께 생성하는 방법을 제시한다.

 

7.1 게임 속 스토리

 

게임은 종종 스토리라인을 가진다. 어떤 게임에서는 짧은 배경 이야기를 제공하여 액션을 설정한다. 예를 들어 일인칭 슈팅 게임 둠(Doom)의 스토리는 부적절하게 지옥으로 가는 포털을 열어버린 군사 과학 실험에 관한 것으로, 이 스토리는 게임의 분위기와 일반적인 주제를 설정하고, 플레이어가 레벨을 탐험하고 악마를 쏘는 이유를 동기화하는 데 그 목적이 있다. 게임이 시작된 이후에는 레벨 진행과 게임 메커닉이 스토리와 거의 관련이 없다. 다른 게임에서는 스토리라인이 게임 진행을 더 깊이 구조화하여, 게임 플레이가 이루어지는 내러티브 아크를 제공한다. 파이널 판타지 시리즈는 이 스타일의 게임 스토리라인을 대표하는 예시이다.

 

이 글의 주제는 게임에 들어가는 모든 것을 절차적으로 생성하는 것이므로, 이제 절차적으로 게임 스토리라인을 생성하는 방법을 살펴보는 것은 놀라운 일이 아니다. 앞 장에서 논의한 게임 규칙의 절차적 생성과 마찬가지로, 스토리라인의 절차적 생성은 다른 종류의 절차적 콘텐츠 생성과는 다소 차이가 있다. 스토리라인은 게임과 깊이 얽혀 있으며, 게임의 장르와 메커닉에 크게 의존하기 때문이다.

 

어드벤쳐 게임과 롤플레잉 게임에서 게임의 스토리라인을 게임 플레이와 통합하는 일반적인 방법은 퀘스트이다[23, 1]. 퀘스트에서 플레이어는 게임 세계에서 할 일을 부여받는다. 이 일은 보통 현재 스토리라인의 상태에 의해 동기화되며, 완료하면 스토리를 어떤 방식으로든 전진시킨다. 예를 들어, 플레이어는 물건을 회수하거나, NPC를 돕거나, 몬스터를 물리치거나, 물품을 다른 마을로 운송하는 일을 맡게 될 수 있다. 일부 게임(특히 RPG)은 하나의 거대한 퀘스트로 구성되며, 이를 작은 하위 퀘스트로 나누어 게임플레이와 스토리 진행이 교차하도록 설계된다.

 

제일장에 다룬 일반적인 절차적 콘텐츠 생성 논증을 넘어, 게임 디자이너가 게임 스토리를 절차적으로 생성하려는 여러 가지 이유가 있다. 한 가지 이유는 절차적으로 생성된 게임 세계가 플레이어에게 의미나 동기가 부족할 수 있기 때문이다. 이는 세계와 함께 스토리의 관련 부분을 절차적으로 생성해 게임 스토리와 연결되지 않으면 발생한다. Ashmore와 Nitsche [2]는 '문맥과 목표가 없으면 생성된 행동, 그래픽, 게임 공간이 실질적이거나 지루하게 될 위험이 있다'고 주장한다. 두 번째 이유는 퀘스트를 절차화하면 실제로 플레이할 수 있는 게임이 된다는 점이다. Sullivan 등 [21]은 컴퓨터 RPG는 흔히 퀘스트가 '일반적으로 과제나 마일스톤의 목록으로 구성된다'는 매우 퇴화된 형태를 갖는다고 지적한다. 이는 플레이어가 창의적으로 충족할 수 있는 개방형 목표 대신이다. 테이블탑 RPG는 훨씬 복잡하고 개방형 퀘스트를 가지고 있다. 그 이유는 인간 게임 마스터가 게임 진행 중에 퀘스트를 동적으로 생성하고 조정할 수 있기 때문이다. 즉, 미리 작성되지 않는다. 절차적 퀘스트 생성은 그 유연성을 비디오게임 퀘스트에 다시 가져오는 방법을 제공한다.

 

7.2 계획을 통한 절차적 스토리 생성

 

스토리를 절차적으로 생성하는 한 가지 방법은 그것들을 계획 문제로 보는 것이다. 인공지능에서는 계획 알고리즘이 목표를 만족시키는 행동 시퀀스를 찾는다. 예를 들어, 로봇은 물체를 집어 옮기기 위해 필요한 액추에이터 움직임 시퀀스를 계획한다.

 

스토리의 행동 시퀀스는 무엇이며, 목표는 무엇인가? 이 질문에 답하는 방법은 여러 가지가 있으며, 절차적 스토리 생성 연구자들은 1970대에 이를 살펴보기 시작했다—당시에는 게임 스토리가 아닌 순수 텍스트 기반 단편 소설을 생성했다.

 

우리는 스토리를 이야기 세계(우리 경우에는 게임 세계)에서 일어나는 사건들의 시퀀스로 답할 수 있다—이 시퀀스는 결국 사건 연쇄를 통해 스토리의 끝으로 이끈다. 따라서 우리는 가상의 작품을 시뮬레이션함으로써 스토리를 생성한다: 스토리를 말하기 위해 우리는 먼저 캐릭터가 움직이고 행동하는 것을 시뮬레이션하고, 그 다음에 스토리는 단순히 발생한 사건을 회상하는 것으로 이루어진다. 이 접근 방식을 취한 최초의 영향력 있는 스토리 생성 시스템 중 하나인 Tale-Spin[14]가 있다.

 

스토리 세계를 시뮬레이션하여 스토리를 생성하는 것은 몇 가지 단점이 있다. 이는 스토리를 단순히 사건 로그와 차별화시키는 요소—특히 흥미로운 스토리의 요소—를 고려하지 않는다. 스토리는 저자에 의해 일정한 속도, 드라마틱한 긴장감, 예고, 내러티브 아크 등을 갖도록 신중히 구성된다. 반면에 가상 캐릭터의 일상 시뮬레이션은 이러한 좋은 스토리의 특징을 우연히 갖출 가능성은 있지만 반드시 갖는 것은 아니다. 이 문제를 해결하기 위해 우리는 스토리 세계에서 행동을 취하는 주인공의 관점이 아니라, 스토리를 쓰는 저자의 관점에서 스토리 계획 문제를 바라볼 수 있다. 따라서 스토리 계획은 저자의 목표에 맞는 내러티브 시퀀스를 구성하는 문제로 바뀐다[6]. Universe[12]와 Minstrel[25]는 작가 중심 접근 방식을 취하는 두 개의 잘 알려진 스토리 생성기이다.

 

비디오 게임 스토리의 경우, 작가의 관점에서 계획을 세우는 것은 문제를 더 복잡하게 만들 수 있다. 이는 플레이어가 게임의 스토리 세계에서 행동하고, 작가의 머릿속이 아니라 실제 세계에서 상호작용하기 때문이다. Tale-Spin과 같은 접근법을 사용하여 스토리 세계 내에서 일어나는 이야기를 절차적으로 생성하는 것은 더 직관적일 수 있다. 이는 플레이어가 상호작용할 장소와 사건에 대해 동일한 내용을 다루는 장점이 있기 때문이다. 반면에 우리는 여전히 서사 아크와 다른 작가 수준의 목표를 원할 수 있으며, 이는 스토리 세계 사건 위에 작가 수준의 목표를 계획하는 하이브리드 시스템으로 이어질 수 있다 [13, 19]. 많은 질문이 아직 열려 있으므로 게임에서의 절차적 스토리 생성은 활발히 연구되는 분야이다.

 

이 장의 나머지 부분에서는 스토리 계획의 개념과 알고리즘을 소개하고, 계획을 사용해 인터랙티브 스토리를 생성하는 예시를 살펴본다.

 

7.3 계획을 계획 공간을 통한 탐색으로 보기 

 

계획은 문제 영역에 대한 지식이 주어졌을 때, 잠재적 해들의 공간을 탐색하여 주어진 문제에 대한 해를 찾는 과정으로 볼 수 있다. 이 문제를 계획 문제라고 하며, 목표 상태와 초기 상태로 구성된다. 계획 문제의 해는 행동 시퀀스를 포함하는 계획이다. 실행 시 초기 상태에서 시작해 목표 상태에 도달한다면, 그 계획은 타당하다. 도메인 지식은 계획 연산자들의 라이브러리로 표현되며, 각 연산자는 전제 조건 세트와 효과 세트로 구성된다. 전제 조건은 연산자를 실행하기 위해 충족되어야 할 조건이며, 효과는 계획 연산자가 실행되어 업데이트되는 조건이다.

 

잠재적 해의 공간은 두 가지 방식으로 표현될 수 있다: 상태 공간 또는 계획 공간. 상태 공간은 노드와 호(arc)로 구성된 트리로 표현할 수 있다. 노드는 상태를 나타내고, 호는 연산자 적용에 의한 상태 전이를 나타낸다. 알고리즘이 전진 탐색(forward progression search)일 때는 공간의 루트 노드가 초기 상태를 나타내고, 역 회귀 탐색(backward regression search)일 때는 루트 노드가 목표 상태를 나타낸다. 

 

아래는 상태 공간 알고리즘의 의사코드이다: 

 

1: 루트 노드를 초기 상태로 구성 

2: 비종단 노드를 선택한다.

비종단 노드가 없으면 실패를 반환하고 종료한다.

현재 노드가 목표 상태라면, 초기 상태에서 현재 상태까지의 경로를 솔루션으로 반환하고 종료한다. 

3: 적용 가능한 연산자를 선택한다(전진 탐색에서는 전제 조건이 참이고, 역 회귀 탐색에서는 효과가 참).

해당 연산자가 없으면 노드를 종단으로 표시하고 이로 돌아간다. 

4: 연산자를 적용해 자식 노드를 구성한다.

그래프의 노드 수가 사전 정의된 최대 탐색 노드 수를 초과하면 실패를 반환하고 종료한다. 

5: 2단계로 이동. 

 

계획 공간(그림 7.1 참조)은 노드와 아크로 구성된 트리로 표현될 수 있으며, 상태 공간과 달리 트리의 루트 노드가 계획 문제, 초기 상태 및 목표 상태를 명시한다. 각 리프 노드는 실행 시 주어진 초기 상태에서 목표 상태를 달성할 수 있는 완전한 계획(즉, 해결책) 혹은 계획의 불일치로 인해 더 이상 정제할 수 없는 부분 계획을 나타낸다. 내부 노드는 결함이 있는 부분 계획을 나타낸다. 탐색 과정은 부모 노드를 부모 노드의 결함을 수정하는 계획으로 정제하는 과정으로 볼 수 있다. 계획의 결함은 이전 계획 단계에서 설정되지 않은 열린 전제 조건이거나, 이미 확립된 인과 관계를 뒤집을 수 있는 위협일 수 있다.

 

다음은 부분 순서 계획 알고리즘의 의사코드 설명이다: 

 

1: 계획 문제를 루트 노드로 생성한다. 

2: 휴리스틱 값을 기준으로 비말단 노드를 선택한다. 

3: 노드에서 결함을 선택한다.

결함이 없으면 노드를 솔루션으로 반환하고 종료한다. 

4: 결함을 수리하여 자식 노드를 생성한다.

결함이 열려 있는 전제일 경우에는

a) 기존 계획 단계에서 인과 연결을 설정하거나,

b) 전제를 만족하는 효과를 갖는 새로운 계획 단계를 추가한다.

결함이 위협일 경우에는

a) 위협받는 인과 연결이 방해받지 않도록 시계열 순서 제약을 추가하거나,

b) 위협 단계와 위협받는 인과 연결에 참여하는 단계들을 분리하는 바인딩 제약을 추가한다.

결함이 수리 불가능한 경우에는 노드를 말단으로 표시하고 2번 단계로 돌아간다.

그래프의 노드 수가 미리 정의된 최대 탐색 노드 수를 초과하면 실패를 반환하고 종료한다. 

5: 2번 단계로 이동한다.

 

상태공간 탐색 알고리즘이 생성하는 완전한 계획은 전순서 계획이다. 이는 계획의 모든 단계에 대한 시계열 순서 제약을 지정한다는 의미이다. 반대로 부분 순서 계획은 위협을 해결하기 위해 반드시 설정해야 하는 시계열 순서만 지정한다. 예를 들어, 식료품점에서 우유와 빵을 사는 목표가 주어졌다고 가정해 보자. 목표는 먼저 어떤 것을 사야 할지 걱정하지 않고도 성공적으로 달성할 수 있다. 하지만 전순서 계획은 이 두 구매 행위의 순서를 지정하고, 두 가지 계획을 생성한다: a) 먼저 우유를 사고 그 다음에 빵을 사는 경우, 그리고 b) 먼저 빵을 사고 그 다음에 우유를 사는 경우. 반면에 부분 순서 계획은 순서 제약을 지정하지 않으며, 필요할 때까지 결정이 연기된다.

 

Figure 7.1: 계획 공간 그래프. 루트 노드 #1은 초기 단계와 목표 단계만 있는 빈 계획을 나타낸다. 초기 단계는 효과로 p를 포함하고, 목표 단계는 전제로 g를 포함한다. 노드 #2와 #3은 각각 다른 계획 단계 S1, S2를 추가하여 열린 전제 g를 수정한 부분 계획이다. 노드 #4는 초기 단계와 인과 연결을 만들어서 열린 전제 p를 수정한 완전한 계획이다. 한 개의 해만 필요하다면 여기서 탐색을 끝낼 수 있다. 모든 해를 찾으려면 #3에서부터 정제 탐색이 계속돼서 더 많은 자식 노드 (#5, #6, #7)를 만든다. 노드 #7은 열린 전제 c를 고칠 수 있는 연산자가 없으므로 터미널로 표시된다. 추가 해를 찾는 탐색은 #6(보여지지 않음)에서 계속된다.

 

계획 공간 탐색에서는 현재 계획에 포함된 단계 수와 결함 수를 바탕으로 최적 완전 계획의 길이를 추정하는 휴리스틱 함수를 사용해 탐색 과정을 안내할 수 있다. 

 

상태 공간 탐색과 계획 공간 탐색 모두 장점이 있지만, 계획 공간 탐색 플래너는 인간이 이야기를 읽을 때 만드는 정신 구조와 비슷한 표현을 가지고 있고, 탐색 과정이 인간이 해결책을 찾으려 할 때의 추론 방식과 닮아 있어 스토리 제작에 선호된다 [24]. 또한 계획 구조에 인코딩된 인과 관계는 스토리 요약이나 정서 생성 같은 서사 컴퓨터 모델을 더 깊이 탐구할 수 있게 한다 [3, 5]. 그러나 부분 순서 계획(POP)은 계획이 길어질수록 공간이 기하급수적으로 증가해 계산 비용이 많이 들기 때문에 많은 실용적인 응용에서는 사용되지 않는다.

 

계층적 작업 네트워크(HTN)[20, 22]는 복합 비원시 행동을 더 작은 원시 행동으로 재귀적으로 분할하여 계획을 계층적으로 표현한다. 그림 7.2는 추상 작업을 원시 작업으로 분해하는 HTN 행동 스키마를 보여준다. HTN은 캐릭터 행동을 생성함으로써 이야기를 만드는 데 활용할 수 있다.

 

Fig. 7.2: HTN 동작 스키마. 타원은 추상 연산자이며, 직사각형은 기본 연산자이다. 이 예시는 게임 세계에서 한 시간 동안 진행되는 NPC 활동을 인코딩한다. NPC는 피곤하면 잠을 자거나 무작위 작업을 수행할 수 있다. 배고플 때는 음식 획득(“Get Food”)을 시도할 수도 있다. 음식 획득은 추상 작업이며, 사냥(Hunt)과 사냥 배우기(Learn Hunting) 같은 기본 작업으로 분해된다 [11].

 

HTN 계획은 계획 공간에서 적절한 계획을 탐색한다. 간단한 HTN 알고리즘은 다음과 같다. 

 

1. 추상 연산자를 사용해 루트 노드를 생성한다. 

2. 확장할 추상 연산자를 선택한다.

추상 연산자가 없고

모든 전제 조건이 만족되면,

네트워크를 해결책으로 반환하고 종료한다. 

3. 전제 조건이 참인 동작 스키마를 선택한다.

해당 방법이 없으면 실패를 반환한다. 

4. 추상 연산자를 하위 작업으로 분해한다. 

동작 스키마에 인코딩된 형식으로

5. 2단계로 돌아간다. 

 

7.4 도메인 모델

 

도메인 모델은 특정 도메인(이 장에서는 스토리 월드)의 지식을 인코딩한 계획 연산자 템플릿 라이브러리이다. 상태, 동작, 목표를 통해 계획 문제를 기술하기 위해 다양한 형식 언어가 제안되었다. 이 절에서는 고전 플래너에서 널리 사용되는 STRIPS와 ADL 두 가지 계획 언어에 초점을 맞춘다.

 

형식론으로 넘어가기 전에 예를 들어 보겠다. 이야기 속 캐릭터인 알렉스가 건물 옥상에 있다고 상상해 보자. 그의 목표는 부상 없이 건물의 바닥층에 도착하는 것이다. 알렉스는 즉시 여러 계획을 생각할 수 있다. 예를 들어, 엘리베이터를 타는 것(계획 1), 계단을 내려가는 것(계획 2), 혹은 옥상에서 뛰어내리는 것(계획 3)을 할 수 있다. 결정을 내리려면 그의 능력(예: 노인이거나 이동성에 문제가 있는 경우), 건물의 시설(예: 엘리베이터), 그리고 그의 선호(예: 알렉스는 운동을 위해 계단을 내려가는 것을 항상 선호함) 등과 같은 제약을 고려해야 한다. 건물에 엘리베이터가 있고 알렉스가 빠르게 바닥층으로 가고 싶다면 계획 1이 가장 적합하다. 알렉스는 건물에 엘리베이터가 없으면 Plan 2를 선택할 수 있다. 알렉스가 낙하산을 가지고 있고 칼을 든 연쇄 살인자가 그에게 달려오는 경우 Plan 3을 선택할 수 있다.

 

계획 알고리즘의 목표는 이러한 종류의 결정을 형식화하는 것이다: 다양한 조건, 제약 및 선호도에 직면해 목표를 극대화하는 계획을 찾는 것이다. 따라서 문제 도메인을 가장 잘 표현하는 형식 언어를 선택하는 것이 중요하다.

 

7.4.1 STRIPS 스타일 계획 표현

 

STRIPS는 1971년 Fikes와 Nilson에 의해 도입되었으며 [7], 계획 분야의 많은 현대 형식 언어의 선구자이다. STRIPS 스타일 계획에서 상태는 프로포지션적 리터럴(propositional literal) 또는 첫 번째 순서의 리터럴(first-order literal) 중 하나로 표현된다. 이때 리터럴은 그라운드(즉, 변수와 함수가 없는) 상태이다. 프로포지션적 리터럴은 참 또는 거짓이 될 수 있는 명제를 나타내며(예: p, q, PoorButler), 첫 번째 순서의 논리 리터럴은 객체 간의 관계를 나타내며 이 관계도 참 또는 거짓이 될 수 있다(예: At(Butler,House), Lord(Higginbotham)).

 

STRIPS 스타일 표현에서는 닫힌 세계 가정(closed-world assumption)을 한다—명시적으로 지정되지 않은 조건은 모두 거짓으로 간주된다. 따라서 초기 상태, 목표 상태, 전제 조건을 묘사할 때는 양수 리터럴만 사용된다. 동작의 효과에는 특정 조건을 부정하기 위해 음수 리터럴이 포함될 수 있다. 위에서 논의한 알렉스가 건물을 떠나는 방법을 선택하는 시나리오를 STRIPS 스타일로 공식화하면 다음과 같다:

 

• 초기 상태 표현: 

  At(Alex,Rooftop) ∧ Alive(Alex) ∧ Walkable(Rooftop,Ground) ∧ Person(Alex) ∧ Place(Rooftop) ∧ Place(Ground)

 

• 목표 상태 표현: 

  At(Alex,Ground) ∧ Alive(Alex)

 

• 동작 표현: 

  Action(WalkStairs(p,from,to)) 

  PRECONDITION: At(p,from) ∧ Walkable(from,to) ∧ Person(p) ∧ Place(from) ∧ Place(to) 

  EFFECT: ¬At(p,from) ∧ At(p,to)

 

위 예에서 초기 상태는 여섯 개의 첫 번째 순서 논리 술어를 합성한 것으로 표현된다. 목표 상태는 같은 방식으로 두 개의 술어를 합성한 것이다. 동작 표현에서 WalkStairs라는 동작은 세 개의 변수 매개변수(p, from, to)를 가지며, 동작의 전제 조건은 다섯 개의 술어를 합성한 것으로 표현되고, 동작의 효과는 음수 리터럴을 포함한 두 개의 술어를 합성한 것으로 표시된다. WalkStairs 동작은 그 전제 조건이 만족될 때에만 적용되고 실행된다. 실행 후, At(p, from) 조건은 현재 세계 상태에서 삭제되고 At(p, to) 조건은 현재 세계 상태에 추가된다.

 

7.4.2 ADL, 액션 디스크립션 언어

 

STRIPS는 세계의 상태를 모델링하기 위한 효율적인 표현 언어이다. 상대적으로 단순한 논리 서술(예: 양수와 함수가 없는 리터럴의 결합)을 사용해 현실 세계의 특정 도메인에서의 상태와 행동을 해당 추상 계획 문제로 변환할 수 있다. 그러나 이 단순성은 복잡한 계획 문제에서 한계가 될 수 있다. 따라서 많은 후속 계획 표현은 더 많은 기능으로 확장된다. 대표적인 확장 언어 중 하나가 액션 디스크립션 언어(ADL)이며, 다음과 같은 추가 기능을 제공한다[16]:

 

• 양수와 음수 리터럴이 모두 허용되며, 오픈 월드 의미론(명시되지 않은 조건은 기본적으로 거짓이 아니라 알 수 없음으로 간주)을 따른다. 

• 목표 상태 묘사에 양화 변수와 결합(및)과 분리(또는)의 조합이 허용된다. 

• 조건부 효과가 허용된다. 

• 동등성 및 비동등성 술어(예: (from is not to))와 타입이 지정된 변수(예: (p: Person), (from: Location))를 지원한다. 

 

이전 예시의 ADL 스타일 표현은 아래와 같다: 

 

• 초기 상태 표현 

At(Alex, Rooftop) ∧ ¬Dead(Alex) ∧ Walkable(Rooftop, Ground) ∧ Person(Alex) ∧ Place(Rooftop) ∧ Place(Ground) ∧ Wearing(Alex, Parachute) ∧ ¬Injured(Alex) ∧ Thing(Parachute) 

• 목표 상태 표현 

At(Alex, Ground) ∧ ¬(Dead(Alex) ∨ Injured(Alex)) 

• 동작 표현 

Action(WalkStairs(p: Person, from: Place, to: Place)) 

PRECONDITION: At(p, from) ∧ (from 육= to) ∧ (Walkable(from, to)) 

EFFECT: ¬At(p, from) ∧ At(p, to) 

Action(JumpFromRooftop(p: Person, from: Place, to: Place, sth:Thing)) 

PRECONDITION: At(p, from) ∧ (from 육= to) ∧ Emergent(p) 

EFFECT: ¬At(p, from) ∧ At(p, to) ∧ (when Wearing(p, Parachute): ¬Dead(p))

 

7.5 스토리 계획

 

스토리는 부분 순서 계획으로 표현될 수 있는데, 이는 <S, O, C> 튜플로 나타내며, 여기서

• S는 일련의 사건(즉, 인스턴스화된 계획 연산자)을,

• O는 시점 순서를 (s₁ → s₂) 형태로 표시하며, s₁이 s₂보다 앞서 있음을 의미하고,

• C는 인과 연결 목록으로, 인과 연결은 (s, t; c) 형태로 표시되어 계획 단계 s가 c를 설정하고, 이는 단계 t의 전제 조건임을 나타낸다.

 

그림 7.3은 초기 상태 have(Butler, Wine) ∧ have(Butler, Poison) ∧ serving(Butler, Lord)에서 시작하여 목표 dead(Lord)를 달성하는 네 개의 사건으로 구성된 스토리를 보여준다. 계획의 텍스트 설명은 다음과 같이 읽을 수 있다: (1) Butler가 독을 와인에 넣는다. (2) Butler가 와인을 Lord Higginbotham에게 옮긴다. (3) Lord Higginbotham이 와인을 마신다. (4) Lord Higginbotham이 넘어져 죽는다. (원본 스토리는 [4]에서 가져온 것이다.)

 

이 계획은 스토리로서 합리적으로 보인다. 그러나 이것이 최소 단계 수를 갖는 최적 계획인가? Butler가 대신 Poison을 Lord에게 건네주었다면 어떨까? 그 경우 계획은 세 단계로 구성된다: 1) Butler가 Poison을 운반한다. 2) Lord가 Poison을 마신다. 3) Lord가 넘어진다.

 

이미 알았겠지만, 새로운 계획은 논리적으로 타당하지만 좋은 스토리를 만들지는 않는다. 왜 Lord가 이 계획에 동의할까? 이는 작가 중심 스토리 생성이 개별 인물의 합리적 의도를 무시할 수 있다는 문제점 중 하나다. 대안으로, 인물 중심 스토리 생성은 각 인물이 자신의 행동을 계획하도록 한다. 이는 논리적으로 일관된 행동 집합을 생산할 가능성이 높지만, 순수 인물 중심 계획만으로는 흥미로운 스토리가 나올 것이라 단정할 수 없다. 말할 수 있는 상황은 거의 작가의 목표 없이 발생하지 않는다. 이 문제를 해결하기 위해 Riedl과 Young은 작가 중심 접근과 인물 중심 접근의 균형을 맞추는 의도 기반 계획 알고리즘을 제안했다 [19].

 

7.6 게임 세계와 스토리 함께 생성하기

 

많은 컴퓨터 게임은 스토리 플레이와 개방형 플레이가 교차되는 기간을 통해 플레이어를 끌어들인다. 스토리 플레이는 플레이어가 게임 세계를 원하는 결말로 이끄는 서사적 순서에 따라 진행하도록 촉진하는 활동을 포함한다. 이 장에서 제시한 바와 같이, 스토리는 실행될 때 세계를 점진적으로 원하는 결말에 가까워지게 하는 부분적으로 순서가 있는 행동 계획으로 표현될 수 있으며, 이는 목표 상황으로 대표된다. 개방형 플레이는 스토리 계획을 진행시키지 않으며(또는 억제하지도 않으며) 플레이어의 활동을 포함한다. 개방형 플레이 활동의 예로는 공간 환경 탐험, 무작위 적과의 만남, 보물이나 아이템을 찾는 것이 있다.

 

그림 7.3: 버틀러 이야기. 사각형은 이벤트를 나타내고 화살표는 소스 이벤트가 대상 이벤트에 대한 조건을 설정하는 인과 연결을 나타낸다. 시간 순서는 위에서 아래로 진행한다. 원본 스토리는 [4]에서 가져왔다. 

 

이 섹션은 스토리 플레이와 오픈 엔디드 플레이를 포함한 게임 플레이 경험을 생성하는 것에 관한 것이다. 플레이어는 스토리 플레이와 오픈 엔디드 플레이에 관련된 모든 위치를 포함하는 공간 환경인 게임 세계에 몰입하고, 게임 캐릭터와 다른 모든 NPC가 거주하는 세계를 기대한다. 스토리 플레이와 오픈 엔디드 플레이는 종종 공간 환경과 연결된다. 불행히도, 스토리 플랜 생성기를 사용한다고 해도 공간 환경과 연결되지 않으면 플레이 가능한 경험이 반드시 생기지는 않는다. 자동으로 생성된 스토리 플랜의 목적에 맞는 게임 세계가 존재하지 않는 경우, 게임 세계를 자동으로 생성할 수 있다.

 

게임 세계 생성을 동기화하기 위해, 표 7.1의 완전 정렬 플랜을 생각해 보자. 이 플랜은 플레이어 캐릭터인 팔라딘이 왕의 신뢰를 얻고, 보물 동굴에 대해 배우고, 덫을 탈출하기 위해 일련의 작업을 수행한다. 플랜의 각 행동은 이후 행동이 발생하기 위해 필요한 여러 세계 조건을 설정한다. 예를 들어, 마녀는 죽은 뒤에만 신발을 떨어뜨리고, 왕은 마녀의 신발을 받으면 팔라딘을 신뢰한다. 스토리 플랜은 목표 상황으로 진행하기 위한 필수 단계만 제공하고, 스토리 진행에 영향을 주지 않는 플레이어 활동에 대해서는 추론하지 않는다.

 

표 7.1: 이벤트 위치가 포함된 예시 계획

 

1. 팔라딘이 물통을 왕궁에서 가져옵니다. 

2. 팔라딘이 바바 야가를 물통과 함께 무덤일에서 죽입니다. 

3. 바바 야가가 루비 슬리퍼를 무덤일에서 떨어뜨립니다. 

4. 팔라딘이 신발을 무덤일에서 가져옵니다. 

5. 팔라딘이 신발을 사용해 알프레드 왕에게 신뢰를 얻습니다. 

6. 알프레드 왕이 보물에 대해 보물 동굴에서 팔라딘에게 말합니다. 

7. 팔라딘이 보물을 보물 동굴에서 가져옵니다. 

8. 팔라딘이 보물 동굴에서 덫을 닫습니다. 

9. 팔라딘이 보물 동굴에서 퍼즐을 해결합니다. 

10. 팔라딘이 보물 동굴에서 덫을 엽니다. 

 

도메인 모델은 스토리 진행에 가장 중요한 세계의 측면에 집중하기 위해 플레이어와 NPC의 순간순간 활동을 많이 추상화한다. 하지만 게임 플레이는 항상 분리된 연산의 순서가 아니다. 예를 들어 퍼즐을 해결하려면 여러 개의 레버를 올바른 순서로 작동시켜야 할 수도 있다. 이 장에서는 스토리 계획의 연산을 그 추상적 특성을 강조하기 위해 이벤트라고 부르겠다. 이벤트는 시간적으로 연장된다; 각 이벤트는 연속적인 기간을 가질 수 있고 이벤트 사이에 긴 시간 간격이 있을 수 있다. 계획은 이벤트 사이의 개방형 플레이 기회를 고려하지 않는다. 예를 들어, 묘지는 성에 비해 어디에 있고, 그 거리를 이동하는 데 얼마나 걸리며, 플레이어가 그 과정에서 직접적으로 스토리 계획과 관련이 없는 무엇을 볼 수 있을지 등을 말한다.

 

게임 세계가 정해져 있다면(즉, 여러 위치와 NPC가 있는 고정된 세계라면) 계획의 스토리 이벤트가 게임 세계의 가상 위치와 매핑된다. 예를 들어, 표 7.1의 게임 세계는 묘지, 성, 보물 동굴이 필요하다. 그러나 자동 생성된 스토리 계획의 특성상, 스토리 계획의 요구 사항을 충족하는 하나의 고정된 게임 세계를 갖는 것이 항상 가능하지는 않다: 위치가 누락될 수 있고, 관련 없는 위치가 너무 많을 수 있으며, 위치를 재배치해야 보다 일관되고 의미 있는 흐름을 만들 수 있다. 다음 절에서는 스토리 계획을 기반으로 플레이 가능한 게임 세계를 자동으로 생성하는 기술을 설명한다.

 

7.6.1 스토리에서 공간으로: 게임 세계 생성

 

게임은 종종 플롯 포인트와 열린 게임 플레이를 교차하므로, 생성되는 게임 세계는 세계에서 일어나는 일련의 사건이 일관되게 진행되도록 보장해야 한다. 문제는 다음과 같이 정의할 수 있다: 알려진 유형의 위치를 참조하는 이벤트 목록이 주어지면, 이벤트를 선형으로 진행할 수 있는 게임 세계를 생성한다. 스토리를 공간에 매핑하기 위해 우리는 섬과 다리의 비유를 사용할 것이다. 섬은 사건이 발생하는 공간 영역이다. 다리는 섬 사이에 있는 영역으로, 열린 게임 플레이가 진행되는 곳이다. 다리는 분기할 수 있어, 플레이어가 스토리 진행 중에 반드시 방문해야 할 필요가 없는 영역이 있을 수 있다. 다리의 길이와 다리의 분기 인수는 디자이너가 설정하거나 플레이어 모델에 의해 결정될 수 있는 매개변수이다. 게임 세계는 세 단계 파이프라인에서 생성된다: (1) 스토리 계획을 파싱하여 이벤트가 참조하는 위치 정보를 추출한다. (2) 탐색 가능한 공간의 중간 추상 표현을 생성한다. (3) 탐색 가능한 공간의 그래픽 시각화를 구현한다.

 

표 7.2: 기획 도메인에 대한 초기 상태 선언 일부

 

영웅 (팔라딘)  물건 (물병)  타입 (궁전, 성) 

NPC (바바야가)  물건 (보물)  타입 (묘지일, 묘지) 

NPC (킹 알프레드)  물건 (루비 슬리퍼)  타입 (보물 동굴, 동굴) 

장소 (궁전)  악 (바바야가)  타입 (물병, 버킷) 

장소 (묘지일)  타입 (바바야가, 마녀)  타입 (루비 슬리퍼, 신발) 

장소 (보물 동굴)  타입 (킹 알프레드, 왕)  타입 (보물, 금)

 

먼저, 생성된 스토리 플랜을 파싱하여 각 위치가 섬이 되는 일련의 위치를 추출한다. 스토리 플랜은 완전히 순서가 정해져 있어야 이러한 순서를 생성할 수 있다(부분적으로 순서가 지정된 플랜은 완전한 순서가 지정된 플랜으로 변환될 수 있다). 스토리 플랜의 각 이벤트는 반드시 위치와 연관되어야 한다. 예를 들어 Table 7.1의 스토리 플랜에서는 palace, graveyard일, treasure‑cave라는 기호가 나타내는 장소에서 이벤트가 발생한다. 각 참조된 위치는 타입이 있어야 한다. 이 정보는 보통 계획 도메인의 초기 상태 선언에서 찾을 수 있다. Table 7.2는 예시 스토리 플랜을 생성할 때 사용된 도메인의 초기 상태 일부를 보여준다. 따라서 예시 스토리 플랜은 세 장소에서 진행된다: 성(이벤트 1, 5, 6), 무덤(이벤트 2~4), 동굴(이벤트 7~10). 

 

다음 단계는 게임 세계를 위치 타입 그래프인 공간 트리(space tree)로 중간 표현을 생성하는 것이다. 공간 트리는 게임 세계가 얼마나 크고, 고유 위치가 몇 개인지, 어떤 위치가 서로 인접해 있는지를 나타내는 이산 데이터 구조이다. Figure 7.4는 예시 공간 트리를 보여준다. 이 트리에서 섬 위치에 해당하는 노드(스토리 플랜 이벤트가 발생하는 위치)는 굵게 표시되고, 나머지 노드는 다리(bridges)를 구성한다.

 

계획 도메인은 다리로 사용할 위치 타입에 대한 충분한 정보를 제공하지 않는다. 따라서 환경 전이 그래프(environment transition graph)라는 추가 지식 구조가 필요하다. 환경 전이 그래프는 게임 디자이너가 생각하는 좋은 환경 타입 전이를 캡처하는 데이터 구조이다. 환경 전이 그래프의 각 노드는 가능한 위치 타입이며, 엣지는 한 위치 타입에서 다른 위치 타입으로 전이될 확률이 이 아닌 경우를 나타낸다. Figure 7.5는 환경 전이 그래프 예시를 보여준다.

 

그림 7.4: 예시 공간 트리. 섬들은 굵은 선으로 표시된다. 출처: [8] 

그림 7.5: 환경 전이 그래프. 출처: [8] 

 

공간 트리 생성을 위해 평가 기준을 충족하는 공간 트리를 찾는 데는 어떤 최적화 알고리즘이든 활용할 수 있다. 절차적 콘텐츠 생성에 대한 일반적인 탐색 기반 접근 방식은 2장을 참고하고, 구체적인 구현 세부 사항은 [8]을 참고하자. 평가 기준은 다음과 같다.

 

• 다리(섬 사이의 공간 트리 노드)가 선호되는 길이를 갖는지. 

• 다리가 선호되는 가지수(분기 계수)를 갖는지. 

• 측면 경로(두 섬 사이에 직접 연결되지 않은 가지 노드)의 길이가 선호되는 측면 경로 길이와 일치하는지. 

• 인접한 노드 간의 환경 유형 전이가 환경 전이 그래프 확률과 얼마나 잘 일치하는지. 

 

이 평가 기준은 디자이너가 설정한 매개변수를 사용한다. 다른 평가 기준도 사용할 수 있다.

 

공간 트리가 탐색 기반 최적화 과정을 통해 생성되면, 세 번째 단계는 게임 세계를 시각적으로 구현하는 것이다. 공간 트리는 이 게임 세계의 추상적 표현을 제공하지만 각 위치가 어떻게 보여야 하는지는 알려주지 않는다. 예를 들어 숲, 마을, 묘지 등과 같은 외관을 만들기 위해 아트 에셋을 공간적으로 어디에 배치해야 할까? 

 

그림 7.6: 그리드에 매핑된 공간 트리. 출처: [8] 

 

우리는 공간 트리로 설명된 게임 세계의 2D, 탑다운, 타일 기반 그래픽 시각화를 생성하는 그래픽 실현 과정을 설명한다. 빈 타일의 격자부터 시작하여 먼저 공간 트리를 2D 격자에 매핑한 뒤, 격자의 각 셀에 타일을 선택한다. 격자가 mworld × nworld 타일이라면, mscreen × nscreen 타일은 화면에 동시에 표시될 수 있는 타일 수이다. 공간 트리의 각 노드는 mlocation × nlocation 화면 그리드에 매핑된다. 그림 7.6에서는 세계가 340×160 타일이며, 각 화면이 34×16 타일이고, 각 위치가 3×3 화면 격리를 포함한다(일부만 표시). 공간 트리를 격자에 매핑하는 방법은 다음과 같다. 공간 트리를 깊이 우선 탐색으로 사용하여 각 자식을 그리드에서 부모 옆에 배치한다. 특정 방향(예: 왼쪽에서 오른쪽으로)으로 세계가 성장하는 알고리즘 편향을 방지하기 위해 각 자식을 배치하려는 방위 방향의 순서를 무작위화할 수 있다. 노드가 같은 격자 영역에 매핑될 가능성을 최소화하려면, 공간 트리를 노드가 최대 두 개의 자식만 가지도록 제한하여 총 세 개의 인접 노드만 있도록 할 수 있다. 필요하면 백트래킹한다. 매핑 솔루션이 없으면 공간 트리를 폐기하고 다음 최선의 공간 트리를 찾아 검색을 재개한다.

 

공간 트리의 각 노드가 격자상의 영역에 할당되면, 모듈은 세계의 그래픽 인스턴스화를 시작한다. 공간 트리의 각 노드는 환경 유형을 가지며, 이 환경 유형은 배치될 장식물을 결정한다. 장식물은 타일 위에 오버레이되는 그래픽 자산이며, 환경 유형을 시각적으로 나타낸다. 2D 타일 기반 게임 세계의 실현에서는 장식물은 서로 다른 환경 유형에서 찾을 수 있는 풍경을 묘사하는 스프라이트이다. 숲 환경은 풀, 나무, 덤불로 구성된 장식물을 가지고 있고, 마을은 건물, 성벽, 거리 포장석처럼 보이는 장식물을 가진다.

 

하지만 시스템이 각 장식물의 배치 위치를 어떻게 알 수 있을까? 이 지식 역시 도메인 모델에 존재하지 않으므로, 세 번째 유형의 외부 지식이 필요하다. 각 환경 유형에는 장식물들을 XY 타일 좌표에 대한 확률 분포로 매핑하는 함수가 연결되어 있다. 우리는 두 종류의 매핑 함수를 확인했다.

 

가우시안 분포는 위치의 중심점을 기준으로 장식물의 분산을 정의하며, 그 결과 각 위치의 중심점 주변에 장식물이 더 촘촘히 배치된다. 가우시안 분포의 장점은 장식물들이 인접한 위치에 배치될 수 있어 하나의 위치가 다음 위치와 자연스럽게 이어지는 듯한 모습을 만들어낸다는 점이다 (그림 7.7 참조).

 

Fig. 7.7: 습지와 인접한 숲, 두 지역 모두 가우시안 분포를 가지며 부드러운 전환을 이룬다. 출처: [8] 

 

사용자 정의 분포(custom distribution)는 장식물을 XY 좌표상의 어느 곳에 배치할 확률을 반환하는 임의의, 설계자가 지정한 함수이다. 그림 7.8은 도시 지역 유형에 대한 사용자 정의 분포를 보여준다. 이 분포에 따르면 건물은 그리드형 도시 블록으로 배치될 가능성이 높고, 포장 돌은 도시 블록 사이의 거리로 사용되며, 방패탑은 도시 외곽을 둘러싸는 고리 형태로 배열된다.

 

그림 7.8는 표 7.1의 세 개 섬을 추출한 완전한 게임 세계 예시를 보여준다.

 

7.6.2 스토리에서 시간으로: 스토리 계획 실행

 

스토리가 전개될 공간이 생성된 후, 두 가지 추가 문제가 해결되어야 한다: (a) 세계를 NPC로 채워야 하고, (b) NPC가 스토리를 수행해야 한다. 스토리 실행 전에 이 행동은 미리 알 수 없다. NPC로 세계를 채우는 과정은 스토리 계획에서 NPC 참조를 파싱하고, NPC 유형에 따라 스프라이트를 인스턴스화하여 이벤트에 처음 참여해야 할 위치에 배치하는 단순한 과정이다. 이벤트의 시간 연장으로 인해 NPC는 전투를 수행하고, 대화를 나누며, 덫을 설치하고 트리거하는 등 이벤트를 상세히 설명해야 한다(세계 자체가 NPC가 될 수 있다). 스토리와 세계 지오메트리가 사전에 알려져 있지 않으므로, NPC는 현재 시점 이전에 발생한 이벤트와 세계 배치에 따라 다양한 상황에서 이벤트를 구체화할 수 있을 만큼 유연해야 한다. 

 

Fig. 7.8: 도시용 사용자 정의 분포(위)와 결과 예시(아래). 밝은 색일수록 장식물의 확률이 높으며, 빨간색은 건물, 녹색은 포장 돌, 파란색은 탑을 나타낸다. 출처: [8]

 

한 가지 해결책은 각 이벤트를 반응형 스크립트와 짝지어, 이벤트를 여러 개의 기본 NPC 행동으로 분해하는 것이다. 대략적으로 반응형 스크립트는 내부 노드가 추상 행동을 나타내는 AND‑OR 트리 구조이며, 내부 노드는 여러 캐릭터가 함께 수행하는 행동일 수도 있고, 리프 노드는 애니메이션 같은 실행 가능한 기본 행동을 나타낸다. 반응형 스크립트 실행은 트리를 따라가면서 이벤트를 구현하는 것으로, AND‑노드는 하위 행동을 순서대로 연결하고 OR‑노드는 행동을 달성하는 대안적인 방식을 표현하며, if‑then‑else 의사결정 논리를 구현한다. 내부 노드는 실행 시점에 가상 세계의 상태에 맞지 않는 하위 트리를 잘라내는 데 사용되는 적용 가능성 기준(전제와 유사)을 구현할 수 있다. 반응형 스크립트 기술의 예로는 행동 트리 [9], 계층적 유한 상태 기계 [20], SHOP 2 [15] 같은 계층적 작업 네트워크, ABL 반응형 행동 플래너 [13] 등이 있다.

 

자동으로 생성된 스토리를 개방형 게임 세계에서 실행하려면 두 종류의 반응형 스크립트가 필요하다 [18]: 내러티브 지시 행동과 로컬 자율 행동. 내러티브 지시 행동은 도메인 모델의 이벤트 템플릿과 연결된 반응형 스크립트이며, 위와 같이 이벤트를 기본 행동으로 분해한다. 내러티브 지시 행동은 연극의 무대 관리자처럼 이벤트를 수행한다. 이는 특정 캐릭터와 직접 연결되지 않으며, 여러 캐릭터를 동시에 제어할 수 있다. 로컬 자율 행동은 NPC 유형과 연결되어 있으며, NPC가 세계에 인스턴스화될 때마다 실행되지만 이벤트에서 다른 역할을 수행하지 않는다. 로컬 자율 행동은 플레이어가 개방형 플레이 중에 NPC를 만났을 때, NPC가 풍부한 내부 삶을 가지고 있는 것처럼 보이게 만든다.

 

Fig. 7.9: 표 7.1의 계획에 있는 섬에서 생성된 게임 세계 예시. [8]에서 가져온 것이다.

 

7.7 실습: 이야기 도메인 모델 작성 

 

이 실습의 목적은 이야기 도메인 모델을 작성하고 다양한 계획 알고리즘을 특징짓는 것이다.

 

1. JSHOP2에 익숙해지기 – JSHOP2는 SHOP2 HTN 플래너(원래는 Lisp로 작성)의 상용 Java 구현체이다.

   • JSHOP2 를 다운로드하고 설치한다 (http://www.cs.umd.edu/projects/shop/). 

   • 패키지에 포함된 샘플 예제를 체크아웃하고 테스트한다.

 

2. 초기 상태, 목표 상태, 그리고 행동을 정의하여 두 개의 이야기 도메인(빨간 모자와 마그리의 선물)을 STRIPS 스타일 또는 ADL 스타일 표현으로 계획 문제를 작성한다. 두 이야기 세계 도메인에 더 적합한 표현을 논의하고 그 이유를 설명한다.

 

3. 위의 계획 문제를 JSHOP2에 적합한 HTN 표현으로 변환하고 실행합니다. HTN 계획(또는 SHOP2 플래너)의 이야기 생성 수단/도구로서의 강점과 약점을 논의한다.

 

4. 섹션 7.5에 서술된 버틀러(Butler) 이야기에 대해, 주인이 와인이 독이 든 것을 알고 있고 단지 죽은 척만 할 뿐이며 버틀러는 주인이 그것을 알고 있다는 사실을 모른다고 가정한다. 새로운 저자 목표는 이제 ¬dead(Lord) ∧ arrested(Butler)로 표현된다. 추가 행동(예: Call -911(Lord), Arrest(Police, Butler)), 상태, 인과 연결을 추가하여 완전한 이야기 계획을 만든다. 이로 인해 이야기가 더 흥미롭게 될 것이라고 생각하는가? 왜 그런지 혹은 아닌지 그 이유를 설명한다.

 

5. 계획 기반 이야기 생성의 전반적인 장점과 한계를 논의한다.

 

6. 계획 기반 이야기 생성 기법이 인터랙티브 스토리텔링 시스템 및 게임에서 효과적으로 사용될 수 있는 방법을 논의한다.

 

7.8 요약

 

대부분의 게임은 이야기(전형적인 슈터에서의 배경 이야기, RPG에서의 게임 경험을 구조화하는 이야기 등)를 가지고 있다. 이야기도 콘텐츠로 볼 수 있으며 생성될 수 있다. 가장 흔한 이야기 생성 접근 방식은 어떤 형태의 계획 알고리즘을 사용하는 것이다. 계획 알고리즘은 초기 상태에서 목표 상태까지의 경로를 찾으며, 이 경로를 구성하는 행동 시퀀스는 이야기로 해석될 수 있다. 계획 알고리즘 중에서는 알고리즘이 가능한 계획의 공간을 탐색하는 계획 공간 탐색(plan‑space search)과 새로운 부분을 순차적으로 추가해가며 계획을 구축하는 상태 공간 탐색(state‑space search) 사이의 구분이 있다. 도메인 모델은 게임 세계에 대한 사실과 그 안에서 취할 수 있는 가능한 행동들의 모음이며, 이 모델은 플래너가 계획을 세우는 데 사용된다. 도메인 모델을 표현하는 방법에는 STRIPS와 ADL 언어 등이 있다. 게임 플레이에 영향을 미치는 이야기의 경우, 이야기와 동시에 맵을 생성하거나 이야기를 따르는 맵을 만드는 방법이 있다. 마지막으로, 탐색 및 최적화 기법을 사용해 플롯 포인트를 물리적 위치에 매핑할 수 있다.