About
이 글은 게임이 던전을 생성하는 방식에 관해 제가 정리한 노트입니다. 맵 생성기가 수행하는 작업이 워낙 많고 각 부분이 어떤 역할을 하는지 파악하는 데 시간이 걸리기 때문에 100% 완벽하지는 않지만, 대부분의 사항이 목록에 포함되어 있습니다.
'하늘의 탐험대'의 맵은 가로 56타일, 세로 32타일 크기이며, (0,0)은 왼쪽 상단 타일입니다. 첫 번째와 마지막 행 및 열은 항상 어떤 수단으로도 지나갈 수 없고 어떤 방식으로도 부술 수 없는 통과 불가능한 벽으로 만들어집니다.
던전 층이 가질 수 있는 매개변수들을 나열한 던전 데이터 문서의 섹션을 읽어보시는 것을 추천합니다. 그중 일부가 맵 생성에 사용되기 때문입니다.
Map generation
Main Loop
맵 생성 프로세스의 대부분은 최대 10회까지 반복되는 루프 내에 포함되어 있습니다. 매 반복마다 게임은 전체 맵을 하나 생성한 뒤, 생성된 맵이 유효한지 확인합니다.
만약 유효하다면 프로세스는 종료됩니다. 유효하지 않다면 루프는 다음 반복으로 넘어가고 새로운 맵이 생성됩니다.
만약 루프가 10번의 반복을 모두 마쳤다면(즉, 10번의 시도 동안 유효한 맵을 생성하지 못했다면), 맵 전체를 차지하는 단일 방으로 구성된 기본 맵이 생성되며, 이 방은 몬스터 하우스가 됩니다.
Map layouts
생성될 수 있는 레이아웃에는 여러 종류가 있습니다. 어떤 것들은 특정 위치에 방을 배치하기도 하고(예를 들어 방을 가장자리에 배치하는 "십자가"형, 혹은 모든 방을 중앙에 배치하는 "외곽 고리"형 레이아웃), 다른 것들은 방과 교차로(Crossroads)로 구성된 그리드를 무작위로 생성합니다. 이 마지막 방식이 가장 일반적인 경우이기에 제가 연구한 대상도 바로 이것입니다.
던전 데이터 문서에 이 모든 레이아웃을 목록으로 정리해 두었습니다.
전형적인 그리드 기반 맵을 생성하기 위해 다음과 같은 단계들이 수행됩니다.
Grid initialization
게임은 맵의 크기(레이아웃에 의해 결정됨)에 따라 특정 수의 행과 열로 구성된 그리드를 사용합니다. 맵의 한 행에서 사용할 수 있는 타일의 총량을 그리드가 가진 열의 수로 나누며, 이 값들이 그리드 각 열의 경계선을 결정합니다.
예를 들어, 맵의 너비가 56타일일 때 4개의 열을 가진 맵은 56/4 = 14가 되어 열당 14타일씩 할당됩니다. 이 경우 열의 경계선은 X = 0, X = 14, X = 28, X = 42, 그리고 X = 56에 위치하게 됩니다. 동일한 과정이 행(세로)에 대해서도 반복됩니다.
모든 경계선이 계산되면 맵 그리드가 완성됩니다. 각 셀은 최종 맵에서 방이나 교차로가 될 가능성이 있는 공간이 됩니다.
Max size check
각 레이아웃은 생성될 수 있는 방의 개수를 제한하는 서로 다른 크기를 가지고 있습니다. 게임은 특정 수치(출처를 확인하지는 못했으나, 레이아웃과 관련이 있을 것으로 보입니다)를 가져오며, 그 값에 따라 세 가지 상황이 발생할 수 있습니다.
- 값이 1인 경우: (열 번호 $\ge$ 전체 열 개수 / 2)에 해당하는 모든 열이 폐기됩니다. (해당 셀들은 무효로 표시되어 방이나 교차로를 생성할 수 없게 됩니다.)
- 값이 2인 경우: (열 번호 $\ge$ 전체 열 개수 $\times$ 0.75)에 해당하는 모든 열이 폐기됩니다.
- 그 외의 경우: 어떤 열도 폐기되지 않습니다.
예를 들어, 4개의 열을 가진 맵에서 이 값이 1이라면 제한 수치는 $4 / 2 = 2$가 되며, 따라서 0번과 1번 열에서만 무언가가 생성됩니다.
Room assignment
그 다음으로, 게임은 그리드의 각 셀 중 어느 곳에 방을 생성하고, 어느 곳을 복도를 연결하는 교차로(Crossroad)로 만들지 결정합니다.
방의 개수는 방 밀도(Room density) 수치에 의해 결정됩니다. 게임은 이 수치에 0에서 2 사이의 무작위 값을 더합니다. 그 후, (방의 개수)만큼의 셀을 무작위로 선택하여 방으로 지정합니다.
게임은 모든 셀을 확인하며, 만약 현재 셀이 유효하고 방을 생성하도록 선택되었다면 해당 셀을 '방 셀(Room cell)'로 표시합니다. 참고로, 이는 무효(Invalid)로 표시된 셀도 방으로 선택될 수는 있지만, 최종적으로는 아무것도 생성하지 않음을 의미합니다. 따라서 실제 생성되는 총 방의 개수는 설정된 방 밀도보다 적을 수 있습니다.
게임은 생성 가능한 방의 최대 개수를 31개로 제한하려 시도하지만, 해당 체크 로직이 제대로 구현되지 않아 아무런 영향을 주지 않는 것으로 보입니다. (해당 셀이 방으로 무작위 선택되었는지 확인하는 과정에서 이 제한이 즉시 무시되어버립니다.)
마지막으로, 만약 생성된 방이 2개 미만일 경우 최대 200번까지 반복되는 루프가 실행됩니다. 이 루프 내부에는 각 셀을 훑는 또 다른 루프가 존재합니다. 현재 셀이 유효하다면 60%의 확률로 해당 셀을 방 셀로 전환합니다. 이 과정이 한 번 발생하면 루프는 종료됩니다.
Room and crossroad size and position
이 시점에서 그리드의 셀들은 교차로, 방, 또는 무효(Invalid) 셀로 분류되어 있습니다. 이제 게임은 교차로와 방이 배치될 위치와 방의 크기를 결정합니다. 모든 셀을 하나씩 반복하며, 유효한 각 셀에 대해 다음 과정을 수행합니다.
1. 방(Room)인 경우
생성기의 이 섹션은 6가지 값을 사용합니다: 방의 상단 경계, 좌측 경계, 너비 제한, 높이 제한, 실제 너비, 실제 높이.
값들은 다음과 같이 초기화됩니다:
- 방의 좌측 경계 = 셀의 좌측 경계 + 2
- 방의 상단 경계 = 셀의 상단 경계 + 2
- 방의 너비 제한 = 셀 너비 - 4
- 방의 높이 제한 = 셀 높이 - 3
- 방의 너비 = 5와 (너비 제한 - 1) 사이의 무작위 값
- 방의 높이 = 4와 (높이 제한 - 1) 사이의 무작위 값
참고: 너비 및 높이 제한은 '허용하기엔 너무 큰 값'을 의미합니다. (즉, 너비 제한이 5라면 허용되는 최대 크기는 4입니다.)
초기화 후, 만약 너비가 짝수라면 1을 더합니다. (단, 이로 인해 너비 제한에 도달하게 된다면 변경하지 않습니다.) 높이 역시 동일하게 처리합니다.
또한, 너비는 높이의 1.5배를 초과할 수 없습니다. 만약 초과한다면 그 값으로 제한(Cap)됩니다. 직후에 높이에 대해서도 동일한 체크를 수행합니다 (높이는 너비의 1.5배를 초과할 수 없음).
그 다음, 0과 (너비 제한 - 방 너비 - 1) 사이의 무작위 수를 선택하여 방의 좌측 경계에 더합니다. 이것이 최종적인 방의 좌측 경계가 됩니다. 높이 또한 0과 (높이 제한 - 방 높이 - 1) 사이의 무작위 수를 선택해 상단 경계에 더하여 최종적인 방의 상단 경계를 정합니다.
상단과 좌측 경계가 정해지면, 게임은 하단과 우측 경계를 (너비 + 좌측 경계) 및 (높이 + 상단 경계)로 계산합니다. 이 네 가지 경계를 통해 방의 네 좌표 (좌측, 상단, 우측, 하단) = (x0, y0, x1, y1)를 얻게 됩니다.
이 좌표들을 사용하여 게임은 (x0, y0)부터 (x1 - 1, y1 - 1)까지의 범위를 바닥 타일로 채웁니다.
방은 내부의 추가 지형 생성과 관련된 두 개의 불리언(Boolean) 값을 가집니다.
- 첫 번째 값이 참(True)일 경우: 방 모서리에 추가 벽이 생성될 수 있습니다 (완벽한 사각형이 아니게 됨).
- 두 번째 값이 참(True)일 경우: 방에 물(또는 용암 등)이 포함될 수 있습니다.
이 값들은 지금 설정되지만, 실제 지형 생성은 나중에 이루어집니다. 각 값이 참이 되기 위한 조건은 다음과 같습니다:
- Boolean 1: 해당 층 데이터의 0xD 바이트의 2번 비트(값 4)가 1이어야 합니다. 게임 내 모든 던전 층의 이 바이트 값이 0 또는 1이므로, 실제로는 모든 층에서 거짓(False)이 됩니다.
- Boolean 2: 해당 층 데이터의 0xC 바이트(보조 지형 방 존재 여부)가 0이 아니어야 하며, 80%의 확률 체크를 통과해야 합니다.
만약 체크 후 두 값이 모두 참이 된다면, 동일한 확률로 둘 중 하나를 거짓으로 변경합니다.
2. 교차로(Crossroad)인 경우
이 섹션은 8가지 값을 사용합니다: 교차로의 상단/좌측 경계, 최대 가로/세로 오프셋, 좌/상/우/하단 여백(Margin).
값들은 다음과 같이 초기화됩니다:
- 교차로 좌측 경계 = 셀의 좌측 경계 + 2
- 교차로 상단 경계 = 셀의 상단 경계 + 2
- 최대 가로 오프셋 = 셀 너비 - 4
- 최대 세로 오프셋 = 셀 높이 - 3
- 좌단 여백: 이 셀이 첫 번째 열이면 1, 아니면 2
- 상단 여백: 이 셀이 첫 번째 행이면 1, 아니면 2
- 우단 여백: 이 셀이 마지막 열이면 2, 아니면 4
- 하단 여백: 이 셀이 마지막 행이면 2, 아니면 4
교차로의 X 위치는 (좌측 경계 + 좌단 여백)과 (좌측 경계 + 최대 가로 오프셋 - 우단 여백 - 1) 사이의 무작위 값으로 정해집니다. 교차로의 Y 위치는 (상단 경계 + 상단 여백)과 (상단 경계 + 최대 세로 오프셋 - 하단 여백 - 1) 사이의 무작위 값으로 정해집니다.
좌표가 결정되면, 게임은 해당 교차로 위치에 바닥 타일을 하나 배치합니다.
Cell connection
방과 교차로의 계산이 끝나면, 그것들 사이의 연결 관계가 생성됩니다. (여기서 연결이란 어떤 셀들이 서로 이어질지에 대한 지표를 의미하며, 실제 복도를 만드는 과정은 나중에 이루어집니다.)
이 섹션은 던전 층의 매개변수 중 하나인 연결성(Connectivity) 값을 사용합니다. 프로세스는 무작위 셀 하나를 선택하는 것으로 시작됩니다. 그 후, 해당 층의 연결성 수치만큼 루프가 실행됩니다.
각 반복(Iteration)마다 무작위 방향(상, 하, 좌, 우)이 선택됩니다. 만약 해당 방향으로 이동했을 때 그리드 밖으로 벗어난다면, 다음 방향을 대신 사용합니다. 방향이 결정되면 게임은 그 방향에 있는 셀이 유효한지 확인합니다. 유효하다면 현재 셀과 그 방향의 셀 사이에 연결을 생성하고, 해당 셀을 다음 반복을 위한 현재 셀로 지정합니다. 유효하지 않다면 아무 일도 일어나지 않고 현재 반복이 종료됩니다.
기본적으로 게임은 그리드 내의 셀들을 걸어 다니며(Random Walk) 그들 사이에 경로를 생성하는 방식을 취합니다.
시작 셀이 무효(Invalid) 셀일 수도 있기 때문에, 무효 셀에서 유효 셀로 이어지는 경로가 생성될 수도 있습니다. 하지만 생성 프로세스의 다른 모든 단계에서 무효 셀은 무시되므로 보통은 아무런 영향을 주지 않습니다.
더 심각한 문제는, 시작 셀로 선택된 무효 셀이 다른 무효 셀들에 둘러싸여 있는 경우입니다. (예를 들어, 전체 열의 50%만 유효한 작은 맵에서 그리드 오른쪽에 있는 셀이 선택된 경우) 이 상황이 발생하면 단 하나의 연결도 생성되지 않으며, 결국 유효성 검사(Validity checks)를 통과하지 못해 메인 루프의 현재 시도가 실패하고 새로운 생성을 시도하게 됩니다.
매우 드문 일이지만, 10번의 생성 시도 모두에서 이런 일이 발생할 수 있으며, 이 경우 해당 층은 거대한 몬스터 하우스가 있는 기본 맵으로 생성됩니다. 유효한 셀이 2개 열뿐인 4개 열짜리 맵에서 이런 일이 발생할 확률은 대략 80만 분의 1입니다.
Dead end removal
해당 층 데이터의 0xB 바이트는 맵에 막다른 길을 허용할지 여부를 제어합니다. 이 값이 1이면 이 단계 전체가 생략됩니다. 1이 아닐 경우, 게임은 맵의 각 셀을 확인하기 시작하며, 해당 셀이 다음의 조건을 모두 만족하면 새로운 연결을 시도합니다:
- 유효한(Valid) 셀일 것.
- 방(Room)이 아닐 것.
- 오직 한 방향으로만 연결되어 있을 것.
이 조건에 해당하면, 현재 연결된 방향을 제외한 나머지 세 방향 중 하나를 무작위로 선택하여 그 방향으로 연결을 생성합니다.
이 연결은 선택한 방향으로 이동했을 때 맵 밖으로 나가지 않으며, 현재 셀의 오른쪽에 있는 셀이 유효할 경우에만 생성됩니다. (어느 방향으로 연결을 시도하든 상관없이 항상 '오른쪽' 셀의 유효성만 확인하는데, 이는 제가 보기에 복사-붙여넣기 실수(Copy-paste error)로 보입니다.)
만약 이번 반복(Iteration) 중에 연결이 최소 하나라도 생성되었다면, 모든 셀을 다시 처음부터 확인합니다. 더 이상 새로 생성된 연결이 없으면 프로세스가 종료됩니다.
Hallway creation
그 다음으로, 게임은 연결된 셀들 사이에 실제 복도를 생성합니다. 모든 유효한 셀을 루프하며, 4개 방향 각각에 연결이 있는지 확인하고 복도를 만듭니다.
현재 셀이 방(Room)이라면, 방 내부의 (x0 + 1, y0 + 1)부터 (x1 - 1, y1 - 1) 사이에서 무작위 지점을 하나 선택합니다. 만약 방이 아니라면(교차로라면), 해당 교차로의 왼쪽 상단 모서리(교차로 자체가 타일 1개 크기이므로 유일하게 유효한 지점)를 사용합니다.
그 후, 이 셀과 인접한 모든 유효한 셀 사이에 복도가 생성됩니다.
현재 셀과 그 위에 있는 셀 사이에 복도가 생성되는 과정을 상세히 설명하겠습니다: 먼저, 위에 있는 셀이 교차로라면 그 교차로의 X 좌표를 선택합니다. 만약 방이라면, 해당 방의 x0 + 1과 x1 - 1 사이에서 무작위 X 좌표를 선택합니다.
그 후, 복도 생성은 3단계로 진행됩니다:
1단계 (Phase 1)
게임은 (현재 셀의 무작위 X 좌표, 현재 셀의 y0) 지점에서 생성을 시작하여, 바닥 타일을 배치하며 위쪽으로 이동합니다. 만약 복도 생성 중 어느 지점에서든 시작 지점인 방의 일부가 아닌 다른 바닥 타일에 도달하면, 생성은 중단됩니다. 현재 셀(방이 아닌 그리드 칸 자체)의 상단 경계에 도달하면 2단계가 시작됩니다.
2단계 (Phase 2)
이제 게임은 이전에 선택했던 대상 셀의 무작위 X 좌표에 도달할 때까지 왼쪽 또는 오른쪽으로 이동하며 바닥 타일을 배치합니다. 1단계와 마찬가지로 이동 중 다른 바닥 타일에 도달하면 프로세스를 중단합니다.
3단계 (Phase 3)
1단계와 동일하게, 게임은 다시 위쪽으로 이동하여 대상 방의 y1 - 1 위치에 도달할 때까지 진행합니다. 바닥 타일 충돌 시 중단되는 규칙은 여기에도 적용됩니다.
마지막으로, 두 셀은 현재 방향(또는 상대 방 입장에서는 반대 방향)으로 연결되었다고 표시되며, 두 셀 모두 '어느 방향으로든 연결되어 있음'을 나타내는 바이트 값이 1로 설정됩니다. (이 과정들은 대상 셀이 무효였더라도 수행됩니다.)
Room merging
때때로 인접한 두 방은 하나로 합쳐져 더 큰 방이 되기도 합니다. 게임은 그리드의 모든 셀을 순회하며, 다음 조건들을 모두 만족하는 셀에 대해 5%의 확률로 병합을 시도합니다.
1. 유효한(Valid) 셀일 것. 2. 방(Room)일 것. 3. 최소 한 방향 이상 다른 방과 연결되어 있을 것. 4. 이미 병합된 상태가 아닐 것. 5. (알 수 없는 확인 절차: 해당 데이터의 9번째 바이트가 0일 것.)
방을 병합하기 위해 무작위 방향이 선택됩니다. 만약 해당 방향에 방이 없거나, 그 방이 시작 지점의 방과 동일한 요구 사항을 충족하지 못한다면 병합은 취소되고 루프는 다음 셀로 넘어갑니다.
두 셀이 모두 요구 사항을 충족하면, 두 셀의 좌표를 결합하여 새로운 병합 셀의 좌표를 다시 계산합니다. 예를 들어, 현재 방을 아래에 있는 방과 병합할 경우 좌표는 다음과 같이 설정됩니다:
- x0 = min(현재 방.x0, 대상 방.x0)
- x1 = max(현재 방.x1, 대상 방.x1)
- y0 = 현재 방.y0
- y1 = 대상 방.y1
그 후, 새로운 셀의 모든 영역이 바닥 타일로 바뀌고 두 방은 '병합됨'으로 표시됩니다. 병합 대상이 된 방의 '다른 방과 연결됨'을 나타내는 바이트 값은 비활성화됩니다.
Isolated cell connection
던전 생성의 이 단계에서는 최종 맵에 도달 불가능한 셀이 존재하지 않도록 보장합니다. 이를 위해 게임은 모든 셀을 대상으로 두 번의 루프를 실행합니다.
루프 1 (Loop 1)
만약 현재 셀이 유효하고, 어느 방향으로도 연결되어 있지 않으며, 다른 방으로 병합되지도 않은 상태라면 다음을 수행합니다:
- 해당 셀이 방이 아니거나 (알 수 없는 확인 절차: 바이트 9 != 0)인 경우, 셀 위치의 타일을 벽으로 바꿉니다.
- 만약 방이라면, 게임은 무작위 방향을 선택하여 해당 방향에 인접한 셀이 이미 다른 셀과 연결되어 있는지 확인합니다. 만약 연결된 인접 셀이 있다면, 두 셀 각각에서 무작위 지점을 선택하고 기존 복도 생성 코드와 동일한 로직을 사용하여 두 지점 사이에 복도를 만듭니다. 그 후, 이 셀의 '연결됨' 표시 바이트를 1로 설정하고, 두 셀 모두 해당 방향으로 연결되었음을 나타내는 바이트를 1로 설정합니다.
- 선택한 방향에 조건을 만족하는 셀이 없다면 다음 방향으로 다시 시도합니다. 만약 4개 방향 모두 실패하면 아무 일도 일어나지 않으며 다음 셀로 넘어갑니다.
루프 2 (Loop 2)
만약 현재 셀이 유효하고, 어느 방향으로도 연결되어 있지 않으며, 다른 방으로 병합되지 않았고 (알 수 없는 확인 절차: 바이트 0xF == 0)인 경우, 해당 방 안의 모든 타일을 벽으로 바꿉니다.
Maze room generation (never happens)
미로 방 생성 (실제로 발생하지 않음)
그 다음으로 게임은 층 데이터에 있는 "미사용 확률(unused chance)" 바이트를 확인합니다. (이 값은 보통 2개 층마다 1의 값을 가지며, 나머지는 0입니다.) 그리고 이 값을 바탕으로 무작위 검사를 수행하는데, 통과 확률은 1%(또는 0%)입니다.
만약 이 확률 체크를 통과하면, 게임은 메인 생성 루프의 현재 반복 횟수 사본을 찾아내고, 이 값이 양수(+)라면 아무 일도 일어나지 않습니다. 제가 확인한 바에 따르면 이 루프 카운터 사본을 덮어쓰는 코드를 찾지 못했기 때문에, 두 번째 체크는 항상 실패하는 것으로 보입니다.
만약 이 체크마저 강제로 통과시킨다면, 게임은 다음 기준을 충족하는 모든 셀 중에서 무작위로 하나를 선택합니다:
- 유효한 셀일 것.
- 병합으로 인해 덮어씌워지지 않았을 것.
- 최소 한 방향 이상 연결되어 있을 것.
- 방(Room)일 것.
- (알 수 없는 확인 절차: 바이트 9, C, E, F가 모두 0일 것.)
- 너비와 높이가 모두 홀수일 것.
이후 해당 셀은 미로 방(Maze room)으로 변하며, 일반적인 물 대신 벽으로 채워집니다. (물은 나중에 지형이 생성될 때 일부 벽을 대체할 수도 있습니다.)
Kecleon shop spawn
이 부분에 대해서는 자세히 살펴보지 않았으나, 게임은 켈리몬 상점 출현 확률(Kecleon shop chance)을 바탕으로 무작위 검사를 수행하며, 이를 통과할 경우 무작위 방 하나를 선택하여 그곳에 켈리몬 상점을 생성합니다. 방이 선택되기 위해서는 특정 조건들을 충족해야 하는 것으로 보입니다:
- 병합(Merge)을 통해 다른 방에 의해 덮어씌워진 방이 아닐 것.
- 다른 셀과 연결되어 있을 것.
- 물(지형)이 있는 방이 아닐 것.
- 최소 크기가 4x5 이상일 것.
- (알 수 없는 확인 절차: 바이트 9 == 0 및 바이트 0x10 == 0일 것.)
Monster house spawn
이 부분 역시 세부 사항까지 깊게 살펴보지는 않았습니다. 무작위 검사는 해당 층의 몬스터 하우스 출현 확률(Monster house chance) 수치를 사용하여 수행됩니다. 또한, 해당 층에 이미 켈리몬 상점이 생성되었다면 몬스터 하우스는 생성될 수 없습니다.
Extra hallway generation
맵 생성기에 영향을 주는 또 다른 층 매개변수는 추가 복도 밀도(Extra hallway density)입니다. 이 시점에서 게임은 해당 수치만큼 루프를 돌며, 매 반복마다 추가 복도 생성을 시도합니다. 프로세스는 다음과 같습니다:
먼저 무작위 셀을 선택합니다. 추가 복도를 생성할 자격이 되려면 해당 셀은 방(Room)이어야 하고, 다른 셀과 연결되어 있어야 하며, (알 수 없는 확인 절차: 바이트 0x10 == 0) 조건을 만족해야 합니다. 그렇지 않으면 해당 반복은 종료됩니다.
그다음 무작위 방향이 선택됩니다. 만약 해당 방향으로 이동했을 때 맵 경계에 닿는다면, 다음 방향으로 넘어가며 확인을 반복합니다(순서: 상, 우, 하, 좌). 또한, 방 내부의 무작위 지점이 시작 위치로 선택됩니다.
게임은 선택된 방향으로 이동하기 시작하여 현재 방을 벗어날 때까지, 그리고 현재 타일이 바닥 타일이 아닐 때까지 전진합니다. 이 두 조건이 모두 충족된 후, 만약 현재 타일이 물 타일이라면 반복이 종료됩니다(물은 아직 생성 전인데 이런 확인을 하는 것이 기이합니다). 또한, 현재 타일을 중심으로 하는 5x5 영역 내의 모든 타일이 맵 범위 안에 있는지 확인합니다. 하나라도 범위를 벗어나면 반복이 종료됩니다.
이어서 게임은 현재 진행 방향의 좌측과 우측 타일들을 확인합니다(수직 이동 중이면 좌우, 수평 이동 중이면 상하). 만약 이 중 하나라도 바닥 타일이라면 반복이 종료됩니다.
이제 실제 추가 복도가 생성되기 시작합니다. 이 복도들은 3~5타일 길이의 섹션들로 구성됩니다. 게임은 현재 방향으로 이동하며 바닥 타일을 배치하고, 각 섹션이 끝날 때마다 무작위로 왼쪽 또는 오른쪽으로 90도 꺾어(각 50% 확률) 새로운 섹션을 시작합니다.
이 과정 중 어느 지점에서든 맵 경계에 닿거나, 바닥 타일을 만나거나, 진행 방향의 좌우 타일이 바닥 타일인 경우 반복이 종료됩니다. 또한, 바닥 타일을 배치했을 때 2x2 크기의 작은 바닥 영역이 형성되는 상황이 발생하면 반복은 즉시 종료됩니다.
Room imperfections
다시 한번 게임은 모든 셀을 순회하며 각 셀에 대해 다음 조건들을 확인합니다:
- 현재 셀이 유효하고, 방(Room)이어야 합니다.
- 병합(Merge)된 상태가 아니어야 합니다.
- 다른 셀과 연결되어 있어야 합니다.
- "불완전한 방(Imperfect room)" 불리언 값이 1로 설정되어 있어야 합니다. (이전 "방과 교차로의 크기 및 위치" 섹션에서 언급했던 첫 번째 불리언입니다.)
- (알 수 없는 확인 절차: 바이트 9 == 0 및 바이트 0x10 == 0일 것.)
이 조건들을 모두 만족할 경우, 40%의 확률로 해당 방의 모서리 일부에 추가 지형(벽, 또는 물과 같은 보조 지형)이 생성됩니다. 결과적으로 이 방은 더 이상 정사각형이나 직사각형 모양이 아니게 됩니다.
Water rooms generation
이 부분은 미탐사 영역이나, 우리 모두가 알고 있듯이 방 내부에는 특정 고정된 패턴의 물 지형이나 물 미로가 생성될 수 있으며, 때로는 물줄기에 의해 방이 두 구역으로 나뉘기도 합니다. 방에 물을 생성하려면 해당 방의 "물 지형 방(Water room)" 불리언 값이 참(True)으로 설정되어 있어야 합니다. (이 값은 이전 "방과 교차로의 크기 및 위치" 섹션에서 언급했던 두 번째 불리언입니다.)
Valid map check
이제 게임은 생성된 방의 개수와 방에 속한 바닥 타일의 총합을 계산합니다. 유효한 맵으로 인정받기 위해서는 다음 조건을 만족해야 합니다:
- 방의 개수가 최소 2개 이상이어야 합니다.
- 방에 속한 바닥 타일의 총합이 최소 30개 이상이어야 합니다.
만약 이 조건에 부합하지 않으면 생성된 맵은 폐기되며, 메인 루프의 다음 반복(Iteration)이 시작됩니다. (단, 이 시도가 10번째 시도였다면 중단됩니다.)
이 검사를 통과하면 메인 루프가 종료되고, 게임은 맵의 나머지 요소들을 생성하는 단계로 넘어갑니다. 남아있는 요소들은 모든 맵 레이아웃에 공통적으로 적용되므로, 앞서 설명한 방 생성이나 특정 레이아웃 로직들과 달리 모든 던전 레이아웃에서 동일한 방식으로 생성됩니다.
Water generation
방 내부에서 생성될 수 있는 물 외에도, 일부 층에는 호수와 강이 포함되기도 합니다. 이러한 층은 데이터의 '추가 지형(extra terrain)' 바이트의 첫 번째 비트가 1로 설정된 층들입니다. 물은 통과 불가능한 벽(열쇠 문 주변이나 맵의 가장자리 등)을 제외한 일반 벽 타일을 대체하는 방식으로만 생성될 수 있습니다.
강 생성 (River generation)
먼저 [1, 1, 1, 2, 2, 2, 3, 3] 목록에서 무작위로 숫자 하나를 선택합니다. 이것이 맵에 생성될 강의 개수가 됩니다. 각 강은 다음과 같이 생성됩니다:
강은 맵의 상단에서 시작하여 아래로 흐르거나, 하단에서 시작하여 위로 흐릅니다. 각 강이 위로 흐를지 아래로 흐를지는 50%의 확률로 결정됩니다. 생성은 무작위 X 좌표에서 시작되며, 강의 유형에 따라 맵의 상단 또는 하단에서 시작됩니다. 강은 20개의 섹션으로 구성됩니다. 짝수 번호 섹션(0번부터 시작)은 위/아래로 이동하며, 홀수 번호 섹션은 오른쪽이나 왼쪽 중 하나로 이동합니다(각 50% 확률). 각 섹션의 길이는 2에서 7타일 사이입니다.
게임은 이 규칙에 따라 현재 섹션의 방향으로 이동하며 물 타일을 배치합니다. 생성 도중 다른 물 타일과 충돌하거나 강이 맵의 반대편 끝에 도달하면 생성이 중단됩니다.
강에는 추가적인 메커니즘이 있습니다. 강 생성이 시작되기 직전, 10에서 59 사이의 무작위 값을 선택합니다. 이 값은 생성이 한 타일씩 진행될 때마다 1씩 감소합니다. 강이 끝나기 전에 이 값이 0에 도달하면, 현재 위치에 호수가 생성됩니다.
호수 생성 (강 내부)
호수는 현재 위치를 중심으로 7x7 타일 그리드를 사용하여 생성됩니다. 게임은 루프를 100번 반복합니다. 각 반복마다 해당 그리드 내의 무작위 타일을 선택하고, 만약 그 타일이 맵의 경계 내부이면서 주변 8개 타일 중 하나라도 물이 있다면 해당 타일도 물로 바뀝니다. 그 후, 게임은 해당 7x7 그리드의 모든 타일을 다시 확인하여, 주변에 최소 4개의 물 타일이 있는 타일을 물로 바꿉니다.
호수 생성 (강과 독립적)
모든 강이 생성된 후, 게임은 호수를 추가합니다. 생성되는 호수의 개수는 해당 층의 수중 밀도(water density) 값과 동일합니다.
게임은 먼저 맵의 네 테두리가 아닌 위치 중 하나를 선택하기 위해 최대 200번의 시도를 합니다. 위치를 찾으면, 어떤 타일이 물이 될지 저장할 10x10 불리언 행렬을 만듭니다. 행렬의 네 테두리 값은 true로 설정되고, 내부 값은 false로 설정됩니다.
그 후 게임은 루프를 80번 반복합니다. 각 반복마다 테두리가 아닌 행렬 내 무작위 지점을 선택하고, 인접한 4개 위치 중 하나라도 true이면 선택된 지점도 true로 설정됩니다. 이제 게임은 이 행렬의 값과 무작위로 선택된 맵 위치를 결합하여, 행렬의 원소가 여전히 false인 모든 타일에 물 타일을 배치합니다. 행렬의 (5, 5) 위치가 선택된 맵 위치를 나타냅니다.
수중 지형 유효성 검사 (Valid water check)
물 타일이 될 수 없는 특정 타일들이 있습니다. 모든 물 생성이 완료되면, 게임은 맵의 모든 타일을 확인합니다:
- 만약 해당 타일이 몬스터 하우스, 켈리몬 상점, 절대 파괴 불가능한 벽(absolute mover 사용 불가) 또는 (알 수 없는 확인: 맵 타일 바이트 2의 0번 비트 == 1)인 경우, 바닥 타일로 교체됩니다.
- 만약 타일이 맵의 경계(통과 불가능한 벽으로 이루어진 곳)나 그 옆에 위치한다면, 벽으로 교체됩니다.
이 과정은 맵 전체를 둘러싸는 2타일 두께의 벽 "프레임"을 만들어야 하지만, 좌표 확인 로직의 버그로 인해 하단과 오른쪽 벽은 한 겹의 레이어만 생성됩니다.
Trap generation
함정 생성은 크게 복잡하지 않아 자세히 살펴보지는 않았습니다. 함정 스폰은 해당 층의 함정 밀도(Trap density) 수치에 따라 결정되며, 이 수치는 (밀도)와 (밀도 / 2) 사이의 값으로 무작위화됩니다. 이 결과값이 스폰될 함정의 총 개수가 됩니다. 이 값은 최대 56개로 제한됩니다.
그 후, 게임은 층 내에서 함정이 스폰될 수 있는 모든 타일의 목록을 만들고 이를 무작위로 재배열하는 것으로 보입니다. 이 과정은 목록 내의 무작위 위치 두 곳을 서로 바꾸는 방식으로 진행되며, (목록 길이) * 2회 반복됩니다.
이제 무작위로 섞인 목록에서 임의의 위치를 선택한 뒤 순회하며, 각 요소가 가리키는 위치에 함정을 배치합니다. 목록의 끝에 도달하면 다시 처음으로 돌아갑니다. 이 과정은 이전에 계산된 함정 개수만큼 배치가 완료될 때까지 반복됩니다. 어떤 종류의 함정을 배치할지는 해당 층의 각 함정별 스폰 확률을 참조하여 결정됩니다.
Other
그 외에도 생성되는 요소들이 더 있지만, 꽤 단순하거나 이미 나열한 것들과 유사하여 자세히 조사하지 않았습니다: 적 스폰, 아이템 스폰, 계단 스폰, 팀의 초기 배치 등이 이에 해당합니다.