지하 던전 및 레벨을 위한 구조적 생성 방법 (번역)

제3장: 지하 던전 및 레벨을 위한 구조적 생성 방법

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

 

Noor Shaker, Antonios Liapis, Julian Togelius, Ricardo Lopes, Rafael Bidarra 

 

요약

 

이 장은 게임 콘텐츠의 한 종류인 던전과 이러한 콘텐츠를 생성하는 데 일반적으로 사용되는 여러 방법을 다룬다. 이들 방법은 모두 ‘구조적(constructive)’이며, 고정된(보통 짧은) 시간 안에 실행되고, 출력물을 재생성하기 위해 평가하지 않는다. 대부분의 방법은 구현이 비교적 간단하다. 던전 혹은 던전과 유사한 환경은 매우 많은 게임에서 등장하지만, 이 방법들은 다른 유형의 콘텐츠에도 적용될 수 있다. 마지막으로, 슈퍼 마리오 브라더스 레벨에 적용되는 몇 가지 구조적 생성 방법에 대해 논의하며 장을 마무리한다. 

 

3.1 던전과 레벨 

 

현실 세계에서 던전은 죄수들이 가두어져 있는 차갑고 어두우며 끔찍한 장소이다. 반면 컴퓨터 게임에서 던전은 모험가가 한 지점에서 입장해 보물을 모으고, 몬스터를 피해 또는 처치하며, 귀족 인물을 구출하고, 함정에 빠지며 궁극적으로 다른 지점에서 탈출하는 미로 같은 환경이다. 이러한 던전에 대한 개념은 아마도 롤플레잉 보드게임 『던전 & 드래곤스』에서 비롯되었으며, 거의 모든 컴퓨터 롤플레잉 게임(RPG)의 핵심 특성이 되었고, 장르를 정의한 게임들인 『젤다의 전설』 시리즈와 『파이널 판타지』 시리즈, 최근의 대성공작인 『엘더 스크롤 V: 스카이림』까지 적용되어 왔다. 특히 원래 1980년의 『로그』를 따라 프로시저적 런타임 던전 생성 기능을 갖춘 ‘로그라이크’ 장르가 주목할 만하다; 이 전통의 고프로필 시리즈가 바로 『디아블로』 시리즈다. 이러한 성공적인 게임들과의 밀접한 관계와 설계상의 독특한 제어 도전 때문에 던전은 특히 활발하고 매력적인 PCG(Procedural Content Generation) 주제이다.

 

본 장의 목적을 위해 우리는 어드벤쳐와 RPG 던전 레벨을 상호 연결된 도전, 보상 및 퍼즐로 구성된 미로 같은 환경으로 정의하며, 이는 시간과 공간에서 밀접하게 짜여져 고도로 구조화된 게임 플레이 진행을 제공한다[9]. 던전을 다른 유형의 레벨과 구분 짓는 측면은 정교한 게임 플레이 속도와 진행 개념이다. 던전 레벨은 플레이어가 자유롭게 탐험할 수 있지만(예를 들어 플랫폼 레벨보다), 이 탐험은 게임 디자이너가 설계한 도전, 보상, 퍼즐의 진행과 견고하게 연결된다. 그리고 플랫폼 레벨이나 레이스 트랙과 달리 던전 레벨은 자유 탐험을 장려하면서도 게임 경험, 진행 및 속도에 대한 엄격한 통제를 유지한다(오픈 월드와 달리, 플레이어가 더 독립적이다). 예를 들어, 플레이어는 여러 가능한 던전 경로 중에서 자유롭게 선택할 수 있지만, 현재의 기술 수준에 비해 불가능한 도전은 만나지 못하도록 설계된다 (예를 들어, 샌드박스 도시처럼 뒤로 돌아갈 수 있는 공간이 열려 있지 않기 때문에). 던전을 디자인하는 것은 정해진 게임플레이에서 복잡한 게임 공간을 부상시키는 정교한 연습이며, 그 반대가 아니다.

 

대부분의 어드벤처 게임과 RPG에서 던전은 여러 방이 복도로 연결된 구조를 이루고 있다. 원래 '던전'이라는 용어는 감옥 셀의 미로를 가리키지만, 게임에서는 동굴, 굴, 인간이 만든 구조물도 포함된다. 기하학과 위상학을 넘어 던전은 플레이어를 사냥할 몬스터, 구할 공주와 같은 NPC, 장식(보통 판타지 기반), 그리고 보물 같은 오브젝트를 포함한다.

 

던전의 절차적 생성은 이 유형의 레벨의 토폴로지, 기하학 및 게임플레이 관련 오브젝트를 생성하는 것을 말한다. 일반적인 던전 생성 방법은 세 가지 요소로 구성된다:

 

1. 표현 모델: 던전의 추상적이고 단순화된 표현으로, 최종 던전 구조를 간단히 개관할 수 있다.

2. 그 표현 모델을 구축하는 방법.

3. 표현 모델에서 실제 던전 기하학을 만드는 방법.

 

위에서는 던전을 플랫폼 레벨과 구분했지만, 두 가지 유형의 게임 레벨 사이에는 명확한 유사점도 있다. 플랫폼 게임 레벨의 대표적인 예는 Super Mario Bros.와 Sonic the Hedgehog이며, 이 전통에서 절차적 레벨 생성을 특징으로 하는 현대 게임 예로는 Spelunky가 있다. 던전과 마찬가지로 플랫폼 게임 레벨은 일반적으로 자유 공간, 벽, 보물 또는 다른 수집품, 적과 함정이 있다. 그러나 플랫폼 게임의 게임 메커닉에서는 플레이어 에이전트가 중력에 의해 제한된다: 에이전트는 좌우로 움직이고 떨어질 수 있지만, 보통은 작게 위쪽으로 점프할 수 있다. 결과적으로, 플랫폼과 갭의 상호작용은 플랫폼 게임 레벨 어휘에서 필수적인 요소이다.

 

본 장에서는 던전과 플랫폼 게임 레벨을 프로시저적으로 생성하는 다양한 방법을 연구할 것이다. 이러한 방법들은 매우 다양할 수 있지만 공통점이 하나 있다: 이들은 모두 생성적이며, 실행마다 하나의 출력 인스턴스만 생성한다. 이는 예를 들어 검색 기반 방법과 대조된다. 또한 이들은 빠르다는 공통점이 있다. 일부는 런타임에 레벨을 생성하는 데에도 성공한다. 일반적으로 이러한 방법들은 출력과 그 속성에 대해 (대체로) 제한된 제어를 제공한다. 제공되는 제어의 정도는 현재 어떤 프로시저 방법에서도 매우 중요한 특성이다. '제어'라는 말은 디자이너(또는 프로그래머)가 갖는 옵션 집합을 의미하며 레벨 생성 과정을 의도적으로 조정하기 위해, 그리고 그 조정에 필요한 노력을 조절하기 위해 필요한 컨트롤을 갖추고 있다. 컨트롤은 또한 옵션과 매개변수를 편집했을 때 출력이 합리적으로 변하는지를 결정한다, 즉 생성기가 직관적으로 반응하는 정도를 말한다. 적절한 컨트롤은 생성기가 일관된 결과(예: 플레이 가능한 레벨)를 만들어 내도록 보장하면서, 원하는 특성 집합과 변동성을 모두 유지한다.

 

우리는 여러 종류의 절차적 기법을 논의할 것이다. 단순화를 위해, 이들 기법은 각각 던전 또는 플랫폼 게임 레벨이라는 하나의 콘텐츠 유형의 맥락에서 제시된다. 이 장에서 먼저 논의할 알고리즘 집단은 공간 분할이다. 던전을 공간 분할로 생성하는 두 가지 다른 예시가 제시되며, 핵심 아이디어는 사용 가능한 공간을 재귀적으로 조각으로 나눈 다음 이 조각들을 연결해 던전을 형성하는 것이다. 이어서, 에이전트 기반 방법에 대한 논의가 이어지며, 이 방법의 핵심 아이디어는 에이전트가 원시 물질의 덩어리에 경로를 파는 것이다. 다음으로 소개될 알고리즘 집단은 셀룰러 오토마타이며, 이는 동굴 같은 던전 구조를 생성하는 간단하고 빠른 수단임을 보여준다. 또 다른 절차적 방법인 생성 문법은 다음에 논의되며, 이는 높은 수준의 던전 설계 측면을 자연스럽게 포착할 수 있다. 이후에는 플랫폼 레벨 생성을 위해 개발된 몇 가지 방법에 주목한다. 이들 중 일부는 던전에도 적용 가능하다. 이 장은 상업용 게임 Spelunky와 오픈 소스 프레임워크 Infinite Mario Bros. 그리고 그 최근 파생물인 InfiniTux에 구현된 플랫폼 레벨 생성 방법에 대한 논의로 끝난다. 실습에서는 InfiniTux API를 사용해 이 장의 최소한 하나의 방법을 구현하게 된다.

 

3.2 던전 생성을 위한 공간 분할

 

이름 그대로, 공간 분할 알고리즘은 공간 분할(space partition)을 생성한다. 즉 2D 또는 3D 공간을 서로 겹치지 않는 부분집합으로 분할하여, 공간 안의 모든 점이 정확히 하나의 부분집합(셀이라고도 함)에 속하도록 하는 것이다. 공간 분할 알고리즘은 보통 계층적으로 동작한다: 공간 분할의 각 셀은 같은 알고리즘을 재귀적으로 적용하여 더 세분화된다. 이를 통해 공간 분할을 “공간 분할 트리”라고 불리는 트리 구조로 배치할 수 있다. 또한, 이러한 트리 데이터 구조는 공간 안의 임의의 점에 대해 빠른 기하학적 질의를 가능하게 하여, 예를 들어 효율적인 광선 추적(raycasting), 프러스텀 절단(frustum culling) 및 충돌 감지 같은 컴퓨터 그래픽스 작업에 특히 중요하다.

 

공간 분할의 가장 인기 있는 방법은 이진 공간 분할(binary space partitioning, BSP)이며, 이는 공간을 재귀적으로 두 개의 부분집합으로 나눈다. 이진 공간 분할을 통해 공간은 BSP 트리라고 불리는 이진 트리로 표현된다.

 

BSP의 다양한 변형은 특정 규칙에 따라 서로 다른 분할 초평면을 선택한다. 이러한 알고리즘에는 쿼드트리(quadtree)와 옥트트리(octree)가 포함된다: 쿼드트리는 이차원 공간을 네 개의 사분면으로 분할하고, 옥트트리는 삼차원 공간을 여덟 개의 팔분면으로 분할한다. 여기서는 가장 단순한 예로 이차원 이미지에 쿼드트리를 사용한다. 쿼드트리의 사분면은 임의의 직사각형 형태일 수 있지만, 일반적으로 같은 크기의 정사각형이다. 깊이가 n인 쿼드트리는 2^n × 2^n 픽셀의 이진 이미지를 모두 표현할 수 있으며, 트리 노드의 총 수와 깊이는 이미지의 구조에 따라 달라진다. 루트 노드는 전체 이미지를 나타내고, 그 네 개의 자식 노드는 이미지의 좌상단, 우상단, 좌하단, 우하단 사분면을 나타낸다. 사분면 내부의 픽셀 색이 서로 다르면 그 사분면을 세분화한다; 이 과정은 각 리프 사분면(크기와 상관없이)이 같은 색의 픽셀만 포함할 때까지 재귀적으로 적용된다 (그림 3.1 참조).

 

(a) 이미지 및 분할 (b) 쿼드트리 

Fig. 3.1: 이진 이미지의 예시 쿼드트리 분할 (0은 빨간색, 1은 검은색으로 표시). 이미지의 오른쪽 가장자리에 있는 것처럼 한 색상으로 이루어진 대규모 영역은 추가로 분할되지 않는다. 이미지의 크기는 16×16 픽셀이므로 쿼드트리의 깊이는 4이다. 완전히 확장된 쿼드트리(리프 노드가 단일 픽셀에 대한 정보를 포함하는 경우)라면 256개의 리프 노드가 생길 것이지만, 한 색상으로 된 대규모 영역은 리프 노드가 구십사개인 쿼드트리를 만든다. 트리의 첫 번째 계층은 (b)에서 보여지는데, 루트 노드는 전체 이미지를 포함하고 네 개의 자식은 다음 순서대로 배치된다: 상단 왼쪽 사분면, 상단 오른쪽 사분면, 하단 왼쪽 사분면, 하단 오른쪽 사분면(다른 순서도 가능하다).

 

2D 또는 3D 그래픽에서 공간 분할 알고리즘이 사용될 때, 그 목적은 일반적으로 폴리곤이나 픽셀과 같은 기존 요소를 나타내는 것이며, 새로운 요소를 생성하는 것이 아니다. 그러나 공간 분할이 겹치지 않는 이산적인 하위 집합을 만들어 내는 원리는 던전의 방을 만들거나 일반적으로 게임 레벨에서 구분된 영역을 만들 때 특히 적합하다. BSP를 이용한 던전 생성은 매크로 접근 방식을 따르며, 알고리즘은 종종 섹션 3.3에 제시된 에이전트 기반 접근 방식에서처럼 “눈먼 채굴기”가 아니라 전부를 보는 던전 설계자 역할을 한다. 전체 던전 영역은 BSP 트리의 루트 노드로 표현되며, 방의 최소 크기와 같은 종료 조건이 만족될 때까지 재귀적으로 분할된다. BSP 알고리즘은 두 방이 겹치지 않도록 보장하며, 던전이 매우 구조화된 모습을 갖도록 허용한다.

 

생성 알고리즘이 전통적 분할 알고리즘의 원칙을 얼마나 엄격하게 따르느냐가 만들어지는 던전의 외관에 영향을 미친다. 예를 들어, 쿼드트리를 사용해 무작위로 사분면을 선택하고 분할함으로써 던전을 만들 수 있다. 완성되면 각 사분면에 0 (빈 공간) 또는 1 (방) 값을 할당하고, 모든 방이 연결되도록 한다. 이 방법은 Figure 3.2a에 보이는 것처럼 매우 대칭적이고 “정사각형” 모양의 던전을 생성한다. 또한, 리프 사분면이 균일한 요소(이미지의 경우 같은 색상 픽셀)로 구성되어야 한다는 원칙은 던전 생성을 위해 완화될 수 있다. 각 리프 사분면에 단일 방이 포함되어도 빈 영역도 가질 수 있다면, 사분면 경계보다 작은 방이라면 서로 다른 크기의 방을 만들 수 있다. 이후 이러한 방들을 무작위 또는 규칙 기반 프로세스를 사용해 서로 연결할 수 있으며, 쿼드트리를 전혀 고려하지 않아도 된다. 이러한 추가적인 확률성을 갖더라도 던전은 여전히 매우 깔끔하게 정돈될 가능성이 높다(그림 3.2b 참조).

 

그림 3.2: (a) 사분 트리를 이용해 생성한 던전으로, 각 셀이 전부 빈 공간(검정) 혹은 방(흰색)으로만 이루어져 있다. (b) 사분 트리를 이용해 생성한 던전이지만, 각 사분면에 하나의 방(무작위로 배치)과 빈 공간이 함께 있다. 구획 과정이 끝난 뒤 복도를 추가한다.

 

이제 우리는 BSP 기법을 느슨하게 기반으로 한 보다 확률적인 접근 방식을 설명한다. 우리는 던전의 영역을 너비 w와 높이 h인 영역으로 간주하며, 이는 BSP 트리의 루트 노드에 저장된다. 공간은 수직선이나 수평선에 따라 분할될 수 있으며, 결과적으로 생기는 분할 셀은 같은 크기가 아닐 수 있다. 트리를 생성하는 동안, 매 반복마다 리프 노드를 무작위로 선택하고 무작위로 선택된 수직선 또는 수평선을 따라 분할한다. 리프 노드는 최소 크기(이 예에서는 최소 너비 w/4 및 최소 높이 h/4)를 밑돌면 더 이상 분할되지 않는다. 결국 각 분할 셀에는 하나의 방이 포함된다. 방의 모서리는 확률적으로 선택되어 방이 해당 분할 안에 위치하고 허용 가능한 크기(즉, 너무 작지 않음)를 갖도록 한다. 트리가 생성되면, 동굴은 같은 부모 노드의 자식들을 서로 연결함으로써 생성된다. 아래는 생성 알고리즘의 고수준 의사 코드이며, 그림 3.3과 3.4는 샘플 던전을 생성하는 과정을 보여준다.

 

1: 전체 던전 영역(트리의 루트 노드)으로 시작 

2: 영역을 수평선 또는 수직선에 따라 나눔 

3: 새로 생긴 두 개의 분할 셀 중 하나를 선택 

4: 이 셀이 최소 허용 크기보다 크면 

5: 단계 이로 이동(이 셀을 분할 영역으로 사용) 

6: 다른 분할 셀을 선택하고 단계 4로 이동 

7: 모든 분할 셀에 대해 

8: 셀 내부에 방을 생성, 경계 안에서 무작위로 두 점(좌상단과 우하단)을 선택 

9: 가장 낮은 층부터 시작하여 BSP 트리에서 같은 부모의 자식에 해당하는 방들을 연결하는 복도 그리기 

10: 루트 노드의 자식들이 연결될 때까지 9번 반복 

 

그림 3.3: BSP 트리의 루트 노드에 포함된 던전 영역 A를 확률적으로 분할하는 과정. 처음에는 공간이 수직선으로 B와 C로 나뉘는데, 이 수직선의 x좌표는 무작위로 결정된다. 더 작은 영역 B는 추가적으로 수직선을 그려 D와 E로 분할된다. D와 E는 너비 기준으로 분할할 만큼 충분히 크지 않으므로 리프 노드로 남게 된다. 반면, 더 큰 영역 C는 수평선을 따라 F와 G로 나뉘며, F와 G는 분할이 가능한 충분한 크기를 갖고 있어서 각각 수직선과 수평선을 따라 분할된다. 이 시점에서 G의 분할 셀 J와 K는 더 이상 분할할 만큼 작으며, F의 분할 셀 I 역시 마찬가지다. 셀 H는 아직 충분히 커서 수평선을 따라 L과 M으로 분할된다. 이때 모든 분할 영역은 더 이상 분할할 수 없게 되고, 던전 분할은 BSP 트리에 7개의 리프 노드가 남는 것으로 종료된다. 그림 3.4는 이 던전에서 방과 복도 배치를 보여준다.

 

그림 3.4: 그림 3.3의 분할 던전에서 방과 복도의 배치. (a) BSP 트리의 각 리프 노드에 대해, 방은 해당 분할 셀의 경계 안에서 상단 왼쪽과 하단 오른쪽 코너의 좌표를 무작위로 선택하여 배치된다. (b) 가장 낮은 층(리프)인 L과 M의 리프 노드를 연결하는 복도가 추가된다. 이 시점부터 알고리즘은 방 L과 M을 연결된 것으로 간주하고, 이를 부모 H로 묶는다. (c) 트리를 위쪽으로 올라가며, H(방 L과 M의 그룹)는 복도를 통해 방 I와 연결되고, 방 J와 K는 복도를 통해 부모 G로 그룹화된다. (d) 더 위쪽에서는 같은 부모를 가진 방 D와 E가 복도로 연결되고, 방 L, M, I의 그룹이 방 J와 K의 그룹과 연결된다. (e) 마지막으로, 루트 노드의 두 서브트리가 서로 연결되고 (f) 던전이 완전히 연결된다.

 

바이너리 공간 분할(BSP)은 주로 여기에서 겹치지 않는 방을 만들기 위해 사용되었지만, BSP 트리의 계층 구조는 던전 생성의 다른 측면에도 활용될 수 있다. 그림 3.4의 예시는 방 연결성이 BSP 트리로 어떻게 결정되는지를 보여준다: 같은 부모의 자식에 해당하는 방들을 연결하는 복도를 사용하면 복도끼리 겹치거나 교차할 확률이 줄어든다. 또한, 리프가 아닌 분할 셀은 동일한 테마를 따르는 방 그룹을 정의하는 데 사용될 수 있다. 예를 들어, 던전의 한 구간은 높은 레벨의 몬스터나 마법에 더 취약한 몬스터를 포함할 수 있다. BSP 트리 계층 구조를 기반으로 한 복도 연결과 결합하면, 이러한 방 그룹은 던전의 나머지 부분과 단일 입구를 가질 수 있다. 이는 그러한 방을 감옥이나 어두운 조명 영역으로 장식하도록 허용하며, 은밀한 플레이에 능숙한 플레이어에게 유리하다. 테마가 있는 던전 분할 예시는 그림 3.5에 표시되어 있다.

 

Figure 3.5: Figure 3.4에서 예시 던전을 사용하여 파티션을 활용해 방의 내용을 테마화한 예입니다. 파티션 셀 B와 C는 하나의 복도만으로 연결되어 있어, B 파티션의 방은 잠겨 있을 수 있습니다(녹색 자물쇠). 이 방에 접근하려면 C 셀에서 열쇠가 필요합니다(방 L). 비슷하게, B 셀의 방은 오로지 보물과 보상만을 포함하고, C 파티션의 방은 주로 몬스터로 채워집니다. 또한, C 셀의 몬스터 난이도는 자식 노드에 따라 나뉘어집니다: 파티션 G에는 약한 고블린이, 셀 F에는 마법 능력을 가진 도전적인 몬스터가 있습니다. 추가적인 향상은 G 셀을 어둡게 만들고(조명 소스를 적게 배치) B 셀의 바닥과 벽에 다른 질감을 사용하거나, C 셀의 방 모양을 원형으로 바꾸는 등의 방법으로 G 셀의 난이도를 높일 수 있습니다.

  

3.3 에이전트 기반 던전 성장

 

던전 생성을 위한 에이전트 기반 접근법은 보통 하나의 에이전트를 사용해 터널을 파고 방을 순차적으로 만드는 방식이다. 섹션 3.2의 공간 분할 방식과는 달리, 이와 같은 에이전트 기반 접근법은 미시적 접근 방식을 따르며, 섹션 3.2의 깔끔하게 정돈된 던전 대신 유기적이고 다소 혼란스러운 던전을 만들 가능성이 높다. 던전의 외관은 에이전트의 행동에 크게 좌우된다: 높은 확률적 특성을 가진 에이전트는 매우 혼란스러운 던전을 만들어내고, 일정 부분 "전진 예측" 기능이 있는 에이전트는 교차되는 복도나 방을 피할 수 있다. AI 행동 매개변수가 생성되는 던전의 외관에 미치는 영향은 광범위한 시행착오 없이는 예측하기 어렵다; 따라서 에이전트 기반 접근법은 공간 분할 방식보다 훨씬 예측 불가능하다. 또한, 에이전트 기반 접근법이 방이 서로 겹치거나 던전 영역의 한쪽 모서리만을 차지하는 던전을 생성하지 않을 것이라고 보장할 수 없다. 다음 단락에서는 던전을 생성하기 위한 두 가지 에이전트 기반 접근법을 소개한다.

 

던전을 만들 때 드라이버 에이전트에 적용될 수 있는 AI 행동은 무한히 많으며, 그 결과는 매우 다를 수 있다. 예시로, 우리는 먼저 매우 확률적이고 '눈먼' 방식을 고려할 것이다. 에이전트는 던전의 어느 지점에서 시작하며 무작위 방향(위, 아래, 왼쪽, 오른쪽)을 선택한다. 그 후 에이전트는 그 방향으로 파기를 시작하며, 파낸 던전 타일마다 '복도' 타일로 교체된다. 첫 번째 파기를 마친 뒤, 에이전트가 방향을 바꿀 확률이 5%이며(새로운 무작위 방향을 선택), 또 다른 5%의 확률로 무작위 크기의 방(예시에서는 가로·세로 3~7 타일)을 배치한다. 전전의 방향과 동일한 방향으로 움직인 타일마다 방향을 바꿀 확률이 5%씩 증가한다. 각 타일을 이동할 때 방이 추가되지 않으면 방을 추가할 확률이 5%씩 증가한다. 에이전트가 방향을 바꾸면 방향을 다시 바꿀 확률은 0%로 감소한다. 에이전트가 방을 추가하면 방을 다시 추가할 확률은 0%로 감소한다. Figure 3.6은 알고리즘의 예시 실행을 보여 주며, 그 의사 코드가 아래와 같다. 

1: 방향을 바꿀 확률 Pc를 5로 초기화 

2: 방을 추가할 확률 Pr을 5로 초기화 

3: 굴착기를 던전 타일에 배치하고 방향을 무작위화 

4: 해당 방향으로 파쇄

5: 0~100 사이의 난수 Nc를 생성 

6: Nc가 Pc보다 작으면 

7:  에이전트의 방향을 무작위화 

8:  Pc를 0으로 설정 

9: 아니면 

10:  Pc를 Pc + 5로 설정 

11: 0~100 사이의 난수 Nr를 생성 

12: Nr가 Pr보다 작으면 

13:  방의 너비와 길이를 3~7 사이로 무작위화 

14:  현재 에이전트 위치 주변에 방 배치 

14:   Pr를 0으로 설정 

15: 아니면 

16:  Pr를 Pr + 5로 설정 

17: 던전이 충분히 크지 않다면 

18:  4번 단계로 이동 

 

이전 확률적 접근 방식의 제어 부족을 방지하기 위해, 이는 방과 방 또는 방과 통로의 교차를 초래할 수 있는 겹치는 방과 막다른 통로를 만들 수 있다. 에이전트는 던전의 전체적인 모습을 조금 더 잘 파악하고 방을 추가할 때 방–방 또는 방–통로 교차가 발생하는지 미리 확인하도록 할 수 있다. 또한 방향을 바꾸는 것을 매 단계마다 무작위화할 필요는 없으며, 이는 꼬인 경로를 방지한다.

 

그림 3.6: 확률적 "블라인드" 굴착기의 짧은 실행 시퀀스. 굴착기는 지도상의 임의의 타일에서 시작(첫 번째 이미지)하고 아래쪽으로 굴착을 시작한다. 5개의 타일을 굴착한 후(세 번째 이미지) 방을 추가할 확률이 25%이며, 주사위를 굴려서 네 번째 이미지와 같이 방이 추가된다. 에이전트는 아래쪽으로 이동을 계속(네 번째 이미지)하며 방을 추가할 확률은 5%, 방향을 바꿀 확률은 30%이다. 주사위를 굴리면 새 방향이 오른쪽이 되어(여섯 번째 이미지) 이동을 시작한다. 또 다른 6개의 타일을 이동한 후(일곱 번째 이미지) 방을 추가할 확률은 30%, 방향을 바꿀 확률은 25%가 된다. 방향 전환이 발생하면(여덟 번째 이미지) 에이전트는 왼쪽으로 이동한다. 또 한 번 타일을 굴착한 뒤(아홉 번째 이미지) 방을 추가할 확률이 40%이며, 주사위 결과에 따라 새로운 방이 추가된다(열 번째 이미지). 이 매우 짧은 실행 시퀀스에서도 이미 에이전트는 골목과 겹치는 두 개의 방을 만들었다.

 

우리는 앞을 내다보는 불확실성이 적은 에이전트를 두 번째 예시로 고려할 것이다. 앞서와 같이, 에이전트는 던전의 무작위 지점에서 시작한다. 에이전트는 현재 위치에 방을 추가하면 기존 방과 교차하는지 여부를 확인한다. 모든 가능한 방이 교차를 초래한다면, 에이전트는 잠재적인 복도가 기존 방이나 복도와 교차하지 않도록 방향과 파쇄 거리를 선택한다. 알고리즘은 방이나 복도를 추가해도 교차가 발생하지 않는 위치에서 더 이상 진행할 수 없을 때 멈추며 종료된다. 그림 3.7은 알고리즘의 실행 예를 보여 주며, 아래에는 그 의사코드가 제공된다.

 

1: 굴착기를 던전 타일에 배치한다 

2: 보조 변수 Fr=0, Fc=0을 설정한다 

3: 가능한 모든 방 크기에 대해: 

 3: 잠재적 방이 기존 방과 교차하지 않으면: 

  4: 방을 배치한다 

  5: Fr=1 

  6: for 루프를 종료한다 

7: 방향과 길이(3~7) 범위의 모든 잠재적 복도로에 대해: 

 8: 잠재적 복도가 기존 방과 교차하지 않으면: 

  9: 복도를 배치한다 

  10: Fc=1 

  11: for 루프를 종료한다 

12: Fr=1 또는 Fc=1이면: 

13: 2번으로 이동한다 

 

Fig. 3.7: 정보에 기반한 "look ahead" 굴착기의 짧은 실행 과정. 굴착기는 맵의 랜덤 타일(첫번째 이미지)에서 시작하여 방(두번째 이미지)과 복도(세번째 이미지)를 배치한다. 빈 던전에서는 겹침이 허용되지 않기 때문이다. 첫 번째 복도를 배치한 뒤, 이전 방과 겹치지 않는 3x3 이상의 방이 들어갈 공간이 없으므로 굴착기는 아래쪽으로 다른 복도를 만든다(네번째 이미지). 이 시점에서 겹치지 않는 작은 방이 들어갈 공간이 있으므로 굴착기는 다섯번째 이미지의 방을 배치하고 이어서 복도(여섯번째 이미지 및 여덟번째 이미지)와 방(일곱번째 이미지 및 아홉번째 이미지)을 차례로 배치한다. 아홉번째 이미지 이후에는 기존 방 및 복도와 교차하지 않는 방이나 복도를 추가할 수 없으므로 던전 생성이 중단된다. 비록 던전 영역의 상당 부분이 비어 있음에도 불구하고이다.

 

“블라인드”와 “룩어헤드” 굴착기 에이전트와 함께 제공된 예시들은 순진하고 단순한 접근 방식을 보여 준다다. 그림 3.6과 3.7은 알고리즘이 실행될 때 발생할 수 있는 최악의 시나리오를 대부분 보여 주며, 그 결과 던전이 겹치거나 조기에 종료되는 경우가 나타난다. 제공된 굴착기 행동에 단순하거나 더 복잡한 코드 추가를 통해 이러한 문제 중 다수를 회피할 수 있지만, 에이전트의 알고리즘을 광범위한 실험 없이 이러한 문제를 예측하기는 어렵다는 사실은 변함이 없다. 이는 바람직한 특성이 될 수도 있다. 알고리즘의 비제어성은 유기적이고 현실적인 동굴(인간 광부가 금맥을 향해 터널을 파는 것을 시뮬레이션)을 만들 수 있으며, 던전의 예측 가능성을 플레이어에게 낮출 수 있기 때문이다. 그러나 동시에 게임이 불가능하거나 재미없어지는 지도도 만들어질 수 있다. 이 장에 제시된 대부분의 접근 방식보다 굴착기 에이전트의 매개변수가 생성된 유물의 플레이 가능성 및 엔터테인먼트 가치에 매우 강력한 영향을 미칠 수 있으며, 이러한 매개변수를 최적화하는 일은 직관적이거나 쉬운 과제가 아니다.

 

(a) 무어 이웃 (b) 폰 노이만 이웃 

그림 3.8: 셀룰러 오토마타의 두 가지 이웃 유형. Wikipedia에서 가져옴 

 

3.4 셀룰러 오토마타

 

셀룰러 오토마톤 (복수형: 셀룰러 오토마타)는 이산적 계산 모델이다. 셀룰러 오토마타는 컴퓨터 과학, 물리학, 심지어 일부 생물학 분야에서도 널리 연구되며, 계산, 성장, 발달, 물리 현상 등을 모델링하는 수단으로 활용된다. 셀룰러 오토마타는 많은 논문에서 다뤄졌지만, 기본 개념은 매우 단순하며 몇 문단과 그림 한 두 장으로 설명할 수 있다.

 

셀룰러 오토마타는 n차원 격자, 상태 집합, 전이 규칙 집합으로 구성된다. 대부분의 셀룰러 오토마타는 일차원(벡터) 또는 이차원(행렬)이다. 각 셀은 여러 상태 중 하나일 수 있으며, 가장 단순한 경우에는 셀이 켜져있거나 꺼져있는 상태일 수 있다. 실험 시작 시(시간 t0)의 셀 상태 분포가 셀룰러 오토마타의 초기 상태이다. 그 이후 오토마타는 해당 오토마타의 규칙에 따라 이산 단계로 진화한다. 각 시간 t에서 각 셀은 이전 시간 t-1의 자신과 그 이웃에 있는 모든 셀의 상태를 기반으로 새로운 상태를 결정한다.

 

이웃은 특정 셀 c 주변의 어느 셀이 c의 미래 상태에 영향을 미치는지를 정의한다. 일차원 셀룰러 오토마타의 경우, 이웃은 크기에 의해 정의된다. 즉, 이웃이 왼쪽과 오른쪽으로 몇 개의 셀까지 퍼지는지를 말한다. 이차원 오토마타에서는 가장 흔한 이웃 유형이 무어 이웃과 폰 노이만 이웃이다. 두 이웃 모두 크기가 1 이상의 정수일 수 있다. 무어 이웃은 정사각형이며, 크기가 1인 무어 이웃은 대각선 포함하여 c를 즉시 둘러싼 여덟 개의 셀로 구성된다. 폰 노이만 이웃은 c를 중심으로 교차 형태이며, 크기가 1인 폰 노이만 이웃은 위, 아래, 왼쪽, 오른쪽에 있는 네 개의 셀로 구성된다 (그림 3.8 참조).

 

주변 영역의 가능한 구성 수는 셀 한 개가 가질 수 있는 상태 수를 그 주변 영역에 있는 셀 수만큼 거듭제곱한 것과 같다. 이 수치는 매우 크게 성장할 수 있으며, 예를 들어 두 상태를 가진 오토마타에 무어(Moore) 주변 영역의 크기가 이인 경우 2^25 = 33,554,432가지의 구성이 존재한다. 주변 영역이 작을 때는 전이 규칙을 표 형태로 정의하는 것이 일반적이며, 이 표에서는 주변 영역의 각 가능한 구성이 한 개의 미래 상태와 대응된다. 반면 주변 영역이 클 경우 전이 규칙은 보통 각 상태에 해당하는 셀의 비율을 기준으로 한다.

 

셀룰러 오토마타는 매우 다재다능하며, 몇몇 유형이 튜링 완전임이 입증되었다. 실제로 이러한 시스템이 하향식 모델링을 통해 자연을 이해하는 새로운 방법의 기반이 될 수 있다는 주장이 제기되기도 했다 [28]. 그러나 본 장에서는 주로 셀룰러 오토마타가 정차적 콘텐츠 생성에 어떻게 활용될 수 있는지에 대해 다룰 것이다.

 

Johnson 등은 셀룰러 오토마타를 이용해 무한히 확장되는 동굴 같은 던전을 생성하는 시스템을 제시한다 [4]. 그 동기는 모든 방향으로 끊임없이 이어지는 무한 동굴 탐험 게임을 만들고자 하는 것이었다. 추가적인 설계 제약은 동굴이 직선 가장자리와 각도 대신 유기적이거나 부식된 외관을 가져야 한다는 점이다. 진정으로 무한한 동굴을 저장할 수 있는 저장 매체는 없으므로, 플레이어가 새로운 영역을 탐험할 때마다 실행 시점에 콘텐츠가 생성되어야 한다. 게임은 스크롤이 아니라 한 번에 한 화면씩 환경을 표시하며, 플레이어가 방을 벗어날 때마다 새 방을 생성할 수 있는 몇 백 밀리초의 시간 창을 제공한다.

 

이 방법은 지도 생성 과정을 제어하기 위해 다음 네 가지 매개변수를 사용한다:

• 암석 셀 비율 (접근 불가능한 영역);

• 셀룰러 오토마타 세대 수;

• 암석을 정의하는 이웃 임계값 (T=5);

• 이웃 셀 수.

 

각 방은 50×50 격자로 구성되며, 각 셀은 빈 상태(empty) 또는 암석(rock) 중 하나의 상태를 가질 수 있다. 초기에는 격자가 모두 빈 상태로 시작한다. 하나의 방을 생성하는 과정은 다음과 같다:

• 격자에 "뿌려져" 암석이 배치된다: 각 셀마다 확률 r (예: 0.5)로 암석이 되도록 변한다. 이는 암석 셀의 비교적 균일한 분포를 초래한다.

• 셀룰러 오토마타가 격자에 n (예: 2) 단계 동안 적용된다. 이 셀룰러 오토마타의 단일 규칙은, 한 셀이 다음 시간 단계에서 암석이 되는 조건은 이웃 셀 중 최소 T (예: 5) 개가 암석일 때이며, 그렇지 않으면 빈 공간이 된다.

• 미적 이유로, 빈 공간과 접한 암석 셀은 "벽" 셀로 지정된다. 기능적으로는 암석 셀이지만 외관은 다르게 보인다.

 

이 간단한 절차는 놀랍도록 생동감 있는 동굴 방을 생성한다. 그림 3.9는 무작위 지도(암석이 뿌려진 상태)와 셀룰러 오토마타의 몇 단계 이후 결과를 비교한 것이다.

 

그러나 이는 단일 방만을 생성하는 것이며, 게임에서는 여러 개의 연결된 방이 필요하다. 생성된 방은 제한 암석 안에 개구부가 없을 수 있고, 출구가 인접 방의 입구와 정렬될 것이라는 보장이 없다. 따라서 방이 생성될 때마다 그 즉각적인 이웃 방들도 함께 생성된다. 두 방의 가장 큰 빈 공간 사이에 연결이 없으면, 그 공간들 사이에서 가장 거리가 짧은 지점에 터널이 파집된다. 이후 이웃 방 아홉 개를 한 번에 두 번 더 셀룰러 오토마타를 실행하여 날카로운 가장자리를 부드럽게 한다. 그림 3.10은 이 과정을 통해 아홉 방이 매끄럽게 연결된 결과를 보여준다. 이 생성 과정은 매우 빠르며, 최신 컴퓨터에서는 한 밀리초 이내에 모든 아홉 방을 생성할 수 있습니다. 

 

(a) 랜덤 맵 (b) CA 맵 

Fig. 3.9: 동굴 생성: CA와 랜덤 생성 맵의 비교 (두 맵 모두 r = 0.5); CA 파라미터: n = 4, M = 1, T = 5. 바위와 벽 셀은 각각 흰색과 빨간색으로 표시된다. 색깔 영역은 서로 다른 터널(바닥 클러스터)을 나타낸다. [4]에서 가져옴 

 

우리는 작은 수의 파라미터와 그들이 비교적 직관적이라는 점이 Johnson 등 사람들의 CA 접근 방식의 장점이라고 결론지을 수 있다. 그러나 이 또한 이 방법의 단점 중 하나이다: 디자이너와 프로그래머 모두에게 단일 파라미터가 생성 과정에 미치는 영향을 완전히 이해하기 어렵다. 각 파라미터는 생성된 맵의 여러 특징에 영향을 주기 때문이다. 특정한 요구사항, 예를 들어 일정 수의 방과 특정 연결성을 갖는 맵을 만드는 것은 불가능하다. 따라서 게임플레이 기능은 이러한 제어 파라미터와 어느 정도 분리되어 있다. 이 생성 방법과 게임플레이 기능 사이의 연결은 시행착오 과정을 통해 만들어져야 할 것이다.

 

Fig. 3.10: 동굴 생성: CA로 생성된 3×3 기본 격자 맵. 바위와 벽 셀은 각각 흰색과 빨간색으로 표시된다. 회색 영역은 바닥을 나타낸다. (M = 2; T = 13; n = 4; r = 50%). [4]에서 가져옴

 

3. 5 문법 기반 던전 생성

 

생성 문법은 원래 자연어의 구조를 형식적으로 기술하기 위해 개발되었다. 이 구조들—구문, 문장 등—은 더 큰 규모의 구조가 더 작은 규모의 구조로부터 어떻게 만들어지는지를 설명하는 재귀 규칙의 유한 집합으로 모델링되며, 개별 단어가 말미(terminal) 기호가 된다. 이들은 생성적이기 때문에 언어 구조를 설명하면서 동시에 그것을 생성하는 방법도 함께 제시한다. 우리는 생성 문법에서 샘플링하여 그 문법이 묘사하는 구조를 갖는 새로운 문장을 만들 수 있다. 유사한 기법은 다른 도메인에도 적용될 수 있다. 예를 들어, 그래프 문법[15]은 유사한 재귀 규칙 집합을 사용해 그래프의 구조를 모델링하며, 개별 그래프 노드가 말미 기호가 된다.

 

던전 생성 주제로 돌아가면, Adams[1]는 그래프 문법을 사용해 일인칭 슈팅 게임(FPS) 레벨을 생성한다. FPS 레벨은 던전과 명백히 같지 않을 수 있지만, 우리 목적에선 그 레벨이 던전으로 간주된다. 왜냐하면 그들은 같은 구조—상호 연결된 방들의 미로—를 공유하기 때문이다. 그는 그래프 문법의 규칙을 사용해 레벨의 토폴로지를 설명하는 그래프를 생성한다: 정점은 방을 나타내고, 두 방 사이의 간선은 이 두 방이 인접해 있음을 의미한다. 이 방법은 방 크기와 같은 추가 기하학적 세부 사항을 생성하지는 않는다. 레벨의 이러한 고수준, 토폴로지적 표현의 장점은 그래프 생성을 난이도, 재미, 전역 크기와 같은 매개변수를 통해 제어할 수 있다는 점이다. 검색 알고리즘은 특정 시점에서 생산 규칙의 모든 결과를 분석하고, 지정된 목표에 가장 잘 부합하는 규칙을 선택함으로써 입력 매개변수와 일치하는 레벨을 찾는다.

 

Adams의 작업 한계는 그 문법 규칙과 특히 매개변수의 임시적이고 하드코딩된 특성이다. 이는 던전의 토폴로지적 묘사를 생성하는 데 유효한 접근법이지만, 더 넓은 범위의 게임과 목표에 일반화하려면 매번 새로운 입력 매개변수와 규칙을 만들어야 한다. 그럼에도 불구하고, Adams의 결과는 게임플레이를 통해 던전 생성을 제어하는 동기와 중요성을 보여준다.

 

Dormans의 연구[3]는 5장에 더 광범위하게 다루어지므로 여기서는 그의 탐험 게임용 던전 공간을 생성하기 위한 생성적 문법 사용을 간략히 언급한다. 그래프 문법을 통해 미션은 먼저 방향 그래프 형태로 생성되며, 이는 플레이어가 수행해야 할 연속적인 작업 모델로 사용된다. 이후 각 미션은 노드와 엣지의 네트워크로 추상화되어 형태 문법에 의해 대응되는 게임 공간이 생성된다.

 

이는 미션 문법의 개념을 통해 게임플레이 기반 제어를 최초로 성공적으로 도입한 방법이다. 그러나 이 방법은 실제 제어 매개변수를 제공하지 않는다. 왜냐하면 제어는 그래프와 형태 문법의 서로 다른 규칙에 의해 수행되며, 이는 대부분의 디자이너에게 직관적이지 않기 때문이다.

 

Dormans의 연구에 영감을 받아 van der Linden 등[8]은 게임플레이 문법을 사용하여 던전 레벨을 생성하는 방식을 제안했다. 게임 디자이너는 게임 내에서 수행할 플레이어 행동, 그 순서와 구성을 포함한 상호 관계 및 연관 콘텐츠로 구성된 게임플레이 지향 어휘를 사용해 사전 디자인 제약을 표현한다. 이러한 디자이너가 작성한 제약은 직접적으로 생성적 그래프 문법, 즉 게임플레이 문법을 만들어내며, 서로 다른 제약 집합을 통해 여러 문법을 표현할 수 있다. 문법은 플레이어 행동 그래프를 생성하며, 이는 차례로 던전 레벨의 레이아웃을 결정한다. 생성된 각 그래프에 대해 그래프의 제약을 따라 특정 콘텐츠가 합성된다. 몇 가지 제안된 알고리즘은 그래프를 필요한 게임 공간에 매핑하고, 두 번째 절차적 방법은 그래프가 요구하는 방과 복도의 기하학을 생성한다.

 

이 접근법은 게임플레이 기반 제어를 일반적인 수준에서 개선하려는 목적을 가지고 있다. 이는 디자이너가 처음부터 문법 기반의 플레이어 행동 그래프 생성기를 효과적으로 만들 수 있는 도구를 제공한다. 이 접근법은 일반적이며, 이러한 도구는 특정 도메인에 연결되어 있지 않으므로 플레이어 행동과 관련된 설계 제약을 여러 게임에서 생성하고 조작할 수 있다. 그러나 실제 게임에 플레이어 행동 그래프를 통합하려면, 해당 그래프를 해당 게임에 맞는 구체적인 던전 레벨로 변환할 수 있는 전문화된 생성기가 필요하다. Van der Linden 등은 단 한 가지 사례 연구에서 이러한 전문화된 생성기를 시연했으며, 이를 통해 게임 *Dwarf Quest*에 완전하게 플레이 가능한 3D 던전 레벨을 만들었다[27]. 그림 3.1은 (a) 게임플레이 그래프와 (b) 이 방법으로 생성된 던전을 보여준다.

 

게임플레이 기반 제어 측면에서 이 접근법은 디자이너가 보다 자연스러운 설계 지향 용어로 던전 생성을 지정하고 제어할 수 있도록 한다. 디자이너는 자신만의 플레이어 행동을 만들고 이를 용어집으로 사용해 던전 생성기를 제어하고 제작할 수 있다. 이를 위해 원하는 게임플레이를 지정하면 그에 따라 게임 공간 생성이 제한된다. 또한 디자이너는 난이도와 같은 자신의 매개변수를 표현할 수 있으며, 이는 게임플레이 문법에서 규칙 재작성(rewriting)을 제어한다. 이러한 게임플레이 기반 매개변수를 설정함으로써 생성된 던전에 대해 더욱 세밀한 제어가 가능해진다.

 

(a) (b)

그림 3.1: (a) van der Linden 등(8)이 만든 게임플레이 그래프와 (b) 이에 대응하는 던전 레이아웃

 

3.6 고급 플랫폼 생성 방법

 

이 절에서는 플랫폼 레벨을 생성하기 위해 처음 제안된 두 가지 최신 방법을 논의하면서 플랫폼 생성 방법에 초점을 맞춘다. 이전 절과 달리 이 방법들을 특징짓는 단일 카테고리나 계통은 존재하지 않는다. 흥미롭게도, 우리는 각 방법의 핵심 개념이 던전 생성에도 크게 기여할 수 있음을 지적할 것이다.

 

첫 번째 방법은 Smith et al. [23]이 제안한 리듬 기반 플랫폼 생성이다. 이 방법은 사용자 행동의 타이밍과 반복과 연결되는 리듬 개념에 기반해 레벨을 생성한다. 그들은 먼저 리듬 그룹이라고 부르는 레벨의 작은 조각들을 두 단계의 문법 기반 접근법으로 생성한다. 첫 번째 단계에서는 플레이어 행동 집합이 만들어지고, 이후 이 행동 집합이 대응되는 기하학으로 변환된다. 리듬 그룹을 연결함으로써 많은 레벨이 만들어지며, 구현된 평가자가 가장 우수한 레벨을 선택한다.

 

Smith 등은 디자이너가 생성 과정을 제어할 수 있도록 ‘노브’라고 부르는 일련의 매개변수를 제안한다. 여기에는 (i) 레벨 전체를 통과하는 일반 경로(시작, 끝, 중간 선분 등), (ii) 생성될 리듬의 종류, (iii) 기하학 구성요소의 종류와 빈도, (iv) 레벨에 분포되는 수집물(동전)의 배분 방식(예: 그룹당 동전 수, 갭 위 동전 출현 확률 등)이 포함된다. 또한, 생성된 각 리듬 그룹마다 점프 빈도, 점프를 위해 특정 기하학(스프링)이 얼마나 자주 발생해야 하는지와 같은 파라미터가 있다. 다른 파라미터 집합은 리듬 길이, 밀도, 비트 종류 및 비트 패턴을 제어한다.

 

추상화 수준이 다른 다수의 파라미터는 많은 제어 옵션을 제공하며, 매우 다양한 레벨을 다채롭게 생성할 수 있게 해준다. 또한, 이 방법은 특히 플랫폼 게임 장르에서 게임플레이와 매우 자연스럽게 연결된다. 하지만 이 접근법은 던전 생성에도 잘 맞출 수 있을 것이다. Dormans와 마찬가지로, 두 단계의 문법을 사용하며, 첫 번째 단계는 게임 플레이(이 경우에는 플레이어 행동)를, 두 번째 단계는 게임 공간(지오메트리)를 고려한다. Smith 등이 정의한 리듬 개념은 던전에는 직접 적용되지 않지만, 방과 복도를 통과하는 속도 또는 템포는 던전 기반 게임에서 유사한 가치를 가질 수 있다. 레벨을 리듬 그룹으로 분해하는 것은 속도와 같은 독특한 게임플레이 특성을 가진 던전 그룹으로 던전을 분할하는 것과도 잘 연결된다.

 

두 번째 방법은 Mawhorter 등(11)의 제안으로 'OccupancyRegulated Extension(ORE)'라고 하며, 이는 2D 플랫폼 레벨을 절차적으로 생성하는 것을 직접 목표로 한다. ORE는 인간 설계 기반 레벨 작성이 임의의 규모에서 지원되는 일반적인 지오메트리 조립 알고리즘이다. 이 접근 방식은 사전에 작성된 레벨 청크를 기초로 삼아, 라이브러리에서 이러한 청크를 사용해 레벨을 조립한다. 청크는 단일 지상 요소, 지상 요소와 오브젝트의 조합, 상호작용 가능한 오브젝트 등과 같은 레벨 지오메트리를 의미한다. 이는 Smith 등(23)이 도입한 리듬 그룹과 다르다. 리듬 그룹은 PCG 방법으로 별도로 생성되는 반면, ORE 청크는 수동으로 만든 콘텐츠 조각들이 라이브러리에 존재한다. 알고리즘은 다음 단계를 거친다: (i) 임의의 잠재적 플레이어 위치(점유율)를 선택하여 청크를 배치; (ii) 문맥 기반 호환 청크 목록에서 청크 선택; (iii) 새 청크를 기존 지오메트리와 통합. 이 과정은 잠재적 플레이어 위치가 더 이상 없을 때까지 계속되며, 그 후 후처리는 파워업과 같은 오브젝트 배치를 담당한다.

 

이 프레임워크는 일반적인 2D 플랫폼 게임을 위해 설계되었으므로, 특정 게임 요소와 메커니즘을 채워 넣어야 하고, 청크를 설계해 라이브러리에 추가해야 한다. 다양한 레벨은 최소한 흥미로운 청크 라이브러리를 사용해야만 생성될 수 있다.

 

Mawhorter 등은 그들의 ORE 알고리즘에 대한 구체적인 제어 매개변수는 언급하지 않지만, 디자이너는 여전히 일정 부분 제어할 수 있다. 우선, 라이브러리 속 청크와 발생 확률은 암묵적 매개변수이며, 이는 실제로 레벨의 지오메트리와 다양성을 결정한다. 따라서 플레이어가 수행할 수 있는 동작은 정의되고 청크 설계에 포함되어야 한다. 그리고 가장 중요한 점은 그들의 혼합 주도 방식이 게임플레이 관점에서 제공할 수 있는 가장 큰 제어를 제공한다는 것이다. 그러나 이 방식을 지나치게 확장하면 수동으로 레벨을 구성하는 것에 지나치게 가까워져 PCG의 이점을 감소시킬 수 있다. 요약하면, 이 방법은 많은 제어를 제공하지만, 생성 과정은 아직 비효율적일 수 있다. 특정 레벨을 생성하기 위해서는 여전히 많은 수작업이 필요해 보인다.

 

이 ORE 방법은 혼합 주도 방식을 제안하며, 디자이너가 알고리즘이 나머지를 생성하기 전에 콘텐츠를 배치할 수 있는 옵션을 제공한다. 이 접근법은 던전 생성에서도 매우 흥미롭다. 부분적으로 설계된 레벨을 채워넣을 수 있는 알고리즘은 큰 가치를 지닌다. 디자이너가 특수 이벤트 방을 배치하고, 그 뒤에 알고리즘이 보다 일반적인 부분을 추가하도록 상상해 보라. 이 혼합 주도 방식은 레벨의 다양성과 디자이너의 제어를 동시에 향상시키면서도 그들의 작업 부담을 덜어준다. 또한, 특수 방이 보다 일반적인 복도로 연결되는 던전 디자인 원칙에도 부합한다. 청크 라이브러리를 활용하는 것은 던전 레벨 생성(예: 템플릿 방, 교차점, 복도 세트의 결합)과 잘 맞는다. 다만, 3D 던전 레벨은 일반적으로 2D 플랫폼 레벨보다 훨씬 크고 복잡한 청크 라이브러리를 요구한다. 이는 많은 유사한 지면 지오메트리를 공유하기 때문이다.

 

3. 7 플랫폼 생성 예시

 

3. 7. 1 Spelunky

 

Spelunky는 2008년 Derek Yu가 처음 만든 2D 플랫폼 인디 게임이다 [29]. 게임의 PC 버전은 무료로 제공된다. 이후 2012년 Xbox Live Arcade에서 향상된 그래픽과 더 많은 콘텐츠를 갖춘 업데이트 버전이 출시되었으며, 2013년에는 PC에서 향상판이 추가로 출시되었다. Spelunky의 게임 플레이는 2D 레벨을 탐색하고, 아이템을 수집하고, 적을 처치하며 끝까지 도달하는 것이다. 게임에서 승리하려면 로프, 버프, 돈 등 다양한 자원을 잘 관리하는 기술이 필요하다. 어느 레벨에서든 게임에 졌을 때는 처음부터 다시 시작해야 한다.

 

게임은 난이도가 점점 증가하는 네 개의 그룹으로 구성된 맵으로 이루어져 있다. 각 레벨 세트는 구별되는 레이아웃을 가지고 있으며 새로운 도전과 새로운 종류의 적을 도입한다. 두 번째 세트의 예시 레벨은 그림 3.12에 제시되어 있다.

 

Spelunky의 돋보이는 특징은 게임 콘텐츠의 프로시저적 생성이다. PCG를 사용하면 매번 플레이할 때마다 독특한 무한한 변형을 생성할 수 있다. Spelunky의 각 레벨은 4×4 격자로 나뉜 16개의 방으로 구성되며, 두 방은 레벨의 시작과 끝을 표시한다 (그림 3.13 참조). 인접 방을 연결하는 복도도 있다. 모든 방이 반드시 연결되는 것은 아니다; 그림 3.13에는 좌상단과 좌하단 모서리에 있는 고립된 방 같은 것이 있다. 이러한 방에 도달하려면 플레이어는 한정된 자원인 폭탄을 사용해 벽을 파괴해야 한다.

 

각 방의 레이아웃은 미리 정의된 템플릿 세트에서 선택된다. 그림 3.13에 제시된 방 중 하나의 예시 템플릿은 그림 3.14에 나타나 있다. 각 템플릿에서는 무작위화가 발생할 수 있는 여러 청크가 표시된다. 레벨이 생성될 때마다 이 청크들은 무작위 숫자 생성기 세트를 따라 다양한 종류의 장애물로 대체된다 [10]. 이 방법을 따라, 알고리즘을 실행할 때마다 새로운 레벨 변형을 생성할 수 있다. 

 

그림 3.12: Spelunky 스냅샷 

그림 3.13: Spelunky에서의 레벨 생성. [10]에서 가져옴 

그림 3.14: Spelunky의 예시 방 디자인. [10]에서 가져옴

 

더 구체적으로, Spelunky의 각 방은 8×10 행렬에 배열된 80개의 타일로 구성된다 [6]. 예시 방 템플릿은 다음과 같을 수 있다.

 

0000000011

0060000L11

0000000L11

0000000L11

0000000L11

0000000011

0000000011

1111111111

 

여기서 0은 빈 칸을 나타내고, 1은 벽 또는 벽돌을, L은 사다리를 나타낸다. 이 예에서 6은 무작위 장애물로 대체될 수 있어 다양한 변형을 생성할 수 있다. 장애물 또는 함정은 일반적으로 원래 타일을 덮어쓰는 5×3 타일 블록으로 구성된다. 게임에 포함된 예시 함정으로는 스파이크, 거미줄, 화살 함정 등이 있다.

 

레벨의 기본 레이아웃은 부분적으로 무작위이며, 변형 기회를 제공하지만 몬스터와 함정의 배치는 100% 무작위이다. 물리적 레이아웃이 생성된 후, 레벨 맵은 몬스터를 생성할 수 있는 잠재적 장소를 스캔한다. 예를 들어, 뒤에 빈 타일이 있는 벽돌은 거미를 생성하기에 충분한 공간을 제공한다. 몬스터 생성을 제어하는 또 다른 무작위 숫자 세트가 있다. 이 숫자들은 유형과 생성 빈도를 제어한다. 예를 들어, 거대 거미를 생성할 확률이 20%이며, 한 번 거미가 생성되면 이 확률은 0으로 설정되어 레벨에 한 개 이상의 거대 거미가 존재하지 않도록 한다.

 

이러한 관점에서 Spelunky의 레벨 생성은 세 가지 주요 단계의 조합으로 볼 수 있다: 첫 번째 단계에서는 사용 가능한 템플릿 중에서 방을 선택하고 출입점을 정의하여 레벨의 주요 레이아웃을 생성한다. 두 번째 단계는 장애물 생성을 포함하며, 이는 사전에 정의된 공간에 휴리스틱 집합에 따라 장애물을 배치하는 에이전트가 레벨을 가로질러 진행하는 것으로 생각할 수 있다. 마지막 단계는 몬스터 생성 단계이며, 다른 에이전트가 레벨을 검색하고 충분한 공간이 발견되고 일련의 조건이 만족될 때 몬스터를 배치한다. 

 

3.7.2 Infinite Mario Bros.

Super Mario Bros.는 닌텐도에서 개발하고 1980년대 중반에 출시된 매우 인기 있는 2D 플랫폼 게임이다 [12]. 게임의 퍼블릭 도메인 복제판인 Infinite Mario Bros. (IMB)[14]는 이후 Markus Persson에 의해 발표되었다. IMB는 Super Mario Bros.의 아트 자산과 일반 게임 메커니즘을 특징으로 하지만 레벨 구성이 다르다. IMB는 웹에서 플레이할 수 있으며 Java 소스 코드도 제공된다. Super Mario Bros.의 대부분 기능을 구현하면서 IMB의 돋보이는 특징은 자동 레벨 생성이다. 새로운 게임을 시작할 때마다 레벨 맵을 순회하면서 특정 휴리스틱에 따라 특징을 추가해 레벨이 무작위로 생성된다. 

 

IMB에서 레벨의 내부 표현은 게임 요소들의 이차원 배열이다. “작은” 상태에서는 마리오가 한 블록 너비와 한 블록 높이이다. 배열의 각 위치는 벽돌 블록, 코인, 적 또는 빈칸으로 채울 수 있다. 레벨은 이차원 레벨 맵에 게임 요소를 배치함으로써 생성된다.

 

이 게임의 레벨을 생성하기 위해 다양한 접근 방식을 따를 수 있다[21, 19, 16, 24]. 아래에서는 한 가지 가능한 접근 방식을 설명한다.

 

확률적 다중 패스 생성기(Probabilistic Multi-pass Generator, PMPG)는 Ben Weber[21]가 Mario AI Championship[17]의 레벨 생성 트랙에 참여하기 위해 만들었다. 생성기는 에이전트 기반이며 먼저 기본 레벨을 만들고 그 다음에 여러 번의 패스를 수행한다. 레벨 생성은 왼쪽에서 오른쪽으로 이동하며 서로 다른 유형의 게임 요소 중 하나를 추가하는 여섯 번의 패스로 구성된다. 각 패스는 사전에 정의된 균일 확률 분포에 따라 발생할 수 있는 여러 이벤트(총 14개)와 연관된다. 이 분포는 수동으로 가중치를 부여하며, 이 가중치를 조정함으로써 간격, 언덕, 적 등 다양한 요소의 빈도를 제어할 수 있다.

 

고려되는 여섯 번의 패스는 다음과 같다: 

 

1. 지면의 높이를 변경하고 간격을 시작하거나 끝내어 레벨의 기본 구조를 변경하는 초기 패스; 

2. 두 번째 패스는 배경에 언덕을 추가한다; 

3. 세 번째 Pass에서는 기본적으로 생성된 플랫폼을 바탕으로 파이프 및 캐논과 같은 정적 적을 추가한다.

4. 쿠파와 구미보와 같은 움직이는 적을 추가한다.

5. 다섯 번째 Pass에서는 연결되지 않은 수평 블록을 추가하고, 마지막으로

6. 여섯 번째 Pass에서는 레벨 전역에 코인을 배치한다.

 

플레이 가능성, 즉 시작 지점에서 끝 지점까지의 경로가 존재함을 보장하기 위해 생성되고 배치된 항목에 제약을 가한다. 예를 들어, 생성된 구멍의 너비는 플레이어가 뛰어넘을 수 있는 최대 블록 수로 제한되며, 파이프의 높이는 플레이어가 통과할 수 있도록 제한된다. 

 

3.8 실습 세션: InfiniTux(및 Infinite Mario)의 레벨 생성기

 

InfiniTux는 Infinite Mario Bros.(IMB)의 레벨을 생성하는 데 사용되는 기반 소프트웨어를 Super Tux[26]의 아트 및 사운드 자산과 결합해 만든 2D 플랫폼 게임이다. 이 게임은 IMB를 대체하기 위해 만들어졌으며, 연구[13, 22, 25, 7, 2]와 Mario AI 챔피언십[20, 21, 5]에서 사용된다. InfiniTux의 레벨 생성기가 IMB에서 사용되는 것과 동일하기 때문에, 무작위 시드를 활용해 무한히 변형되는 레벨을 제공한다. 난이도는 장애물과 몬스터의 수, 빈도, 유형을 조절하는 서로 다른 난이도 값을 사용해 조정할 수 있다.

  

본 실습의 목적은 이 장에서 제시된 한 가지 이상의 방법을 활용해 게임용 콘텐츠를 생성하는 자체 생성기를 구현하는 것이다. 사용할 소프트웨어는 InfiniTux를 기반으로 한 Mario AI 챔피언십의 후속인 Platformer AI Competition[18]의 레벨 생성 트랙에서 사용되는 소프트웨어이다. 이 소프트웨어는 시스템과의 상호작용을 용이하게 하는 인터페이스를 제공하며, 좋은 출발점이 된다. 원본 레벨 생성기를 수정하거나 영감으로 활용할 수 있다. 소프트웨어 사용을 시작하는 데 도움을 주기 위해, 제공되는 인터페이스의 주요 구성 요소와 사용 방법을 설명한다.

 

레벨 생성 트랙 경쟁을 위해 소프트웨어가 개발되고 있으며, 이 트랙은 참가자들이 특정 플레이어에게 재미있는 레벨 생성기를 제출하도록 초대한다. 인터페이스는 생성기를 구축할 때 활용할 수 있는 플레이어 행동 정보를 통합한다. 이 정보는 플레이어가 테스트 레벨을 플레이하면서 수집되며, 게임플레이 세션에서 추출된 통계적 특징을 담은 게임플레이 매트릭스에 저장된다. 특징 예시로는 점프 횟수, 달리기에 소요된 시간, 수집한 아이템 수, 처치한 적 수 등이 포함된다.

 

생성기가 정상적으로 작동하려면, 레벨이 LevelInterface를 구현해야 하며, 이는 레벨이 어떻게 구성되는지와 다양한 유형의 요소가 레벨 전반에 어떻게 흩어지는지를 지정한다:

 

public byte[][] getMap();

public SpriteTemplate[][] getSpriteTemplates() 

 

레벨 맵의 크기는 320×15이며, 맵을 채우기 위해 원하는 방식을 구현해야 한다. 레벨의 기본 구조는 적의 배치 정보를 저장하는 맵과는 다른 맵에 저장된다는 점을 주의해야 한다.

 

레벨 생성기는 플레이어의 게임플레이 매트릭스를 레벨에 전달하고 시뮬레이터와 통신해야 하며, LevelGenerator 인터페이스를 구현해야 한다:

 

public LevelInterface generateLevel(GamePlay playerMat); 

 

이 소프트웨어를 콘텐츠 생성에 활용한 사례가 문헌에 다수 보고되고 있으며, 그 중 일부는 Mario AI 챔피언십에 참여했고, 구현체는 오픈 소스로 공개되어 있으며 경쟁 웹사이트[17]에서 자유롭게 이용할 수 있다. 

 

3.9 요약 

건설적 방법은 롤플레잉 게임과 특정 플랫포머에서 던전과 레벨을 생성하는 데 일반적으로 사용된다. 이러한 방법은 예측 가능한, 대부분 짧은 시간 내에 실행되기 때문이다. 이러한 방법의 한 가지 계열은 이진 공간 분할(Binary Space Partitioning)을 기반으로 하며, 영역을 재귀적으로 더 작은 단위로 분할한 뒤, 순서대로 이 단위들을 연결하여 던전을 구성한다. 또 다른 계열은 "굴착"하는 에이전트(agent)를 기반으로 하여 던전을 탐색하며 구성한다. 이러한 방법은 게임 개발에서 유래했으며 다소 덜 원칙적일 수 있지만, 던전 또는 레벨 생성에 사용되는 다른 방법들은 잘 알려진 컴퓨터 과학 기법의 응용이다. 문법 기반 방법은 5장에 더 자세히 다루어지며, 생성 규칙을 사용해 공리(axion)에서부터 던전을 확장한다. 셀룰러 오토마타는 확률적이며 반복적인 방법으로, 독립적으로 사용하거나 다른 방법과 결합해 부드럽고 유기적인 디자인을 만들 수 있다. 마지막으로, 관련된 몇 가지 방법은 레벨을 여러 번에 걸쳐 순차적으로 처리하며 간단한 확률 규칙에 따라 다양한 유형의 콘텐츠를 추가한다. 이러한 방법은 상징적인 로그라이크 플랫폼 게임 Spelunky와 마리오 AI 프레임워크에도 사용되었지만, 던전에도 쉽게 적용될 수 있다.