📚 지식 노트

시드 하나에서 월드까지: 규칙을 지키는 무작위

절차 생성(procedural generation)에서 난수를 만드는 일은 한 줄이면 된다. 어려운 것은 무작위인데도 반드시 지켜야 할 약속이다. 바이옴마다 보스방이 하나씩 있어야 하고, 같은 종류의 랜드마크는 일정 거리 이상 떨어져야 하고, 난이도는 시작점에서 멀어질수록 올라가야 하고, 중요한 곳은 전부 걸어서 갈 수 있어야 한다. 이런 약속을 먼저 적고, 그 약속이 알고리즘과 순서를 정하게 두는 것이 핵심이다.

1. 점 뿌리기: 영역의 씨앗이 될 점을 던지되, 이미 놓인 점과 너무 가까우면 버린다(기각 표본법, dart throwing). 조건이 빡빡하면 끝없이 실패할 수 있으니 시도 횟수에 상한을 두고, 넘으면 간격을 조금 줄여 다시 시작한다.
2. 영역 나누기: 칸마다 가장 가까운 점이 주인인 보로노이 분할(Voronoi diagram)을 쓴다. 경계를 따로 저장할 필요가 없다. 경계가 너무 반듯하면, 경계를 고치는 대신 “이 좌표는 누구 땅인가”를 물을 때 좌표를 노이즈만큼 밀어서 묻는다(도메인 워프).
3. 바이옴 배정: 바이옴마다 최소·최대 개수, 붙으면 안 되는 조합, 거리에 따른 난이도 순서가 얽혀 있다. 하나씩 정하다 막히면 되돌아가는 제약 충족 문제(CSP)와 백트래킹으로 푼다. 시작점에서 가까운 영역부터 정하면 막혀도 얕은 곳에서 빨리 막힌다.
4. 배치: 보스방, 랜드마크, 보물을 차례로 놓되 앞 단계가 놓은 것을 피할 구역으로 넘긴다. 가장 깊은 곳 같은 최적 자리를 고르지 말고, 조건을 통과한 후보를 모두 모아 그중에서 고르게 뽑아야 회차마다 위치가 달라진다.
5. 연결은 검사가 아니라 구성: 지형을 만든 뒤 막혔는지 검사하고 다시 만들면 몇 번 만에 통과할지 알 수 없다. 영역마다 중요 지점을 최소 신장 트리(MST)로 먼저 이어 길의 뼈대를 정하고, 지형 생성기가 무엇을 만들든 그 길을 판다.

길의 모양은 비용이 정한다. 길을 A*로 찾되 칸마다 “벽이 될 만한 정도”를 비용으로 주면 길이 계곡을 따라 흐른다. 이때 길찾기가 읽는 값과 지형 생성기가 벽을 찍을 때 쓰는 값은 같은 함수에서 나와야 한다. 같은 규칙을 두 곳에 따로 짜면 반드시 어긋나고, 생성은 됐는데 자기 검사기를 통과하지 못하는 월드가 생긴다.

여럿이 같은 월드를 돌아다니는 협동 게임이라면 시드 하나만 주고받고 각자 만든다. 그러려면 같은 시드가 모든 기계에서 비트 단위로 같은 결과를 내야 한다. 부동소수점은 CPU·컴파일러에 따라 마지막 자리가 달라질 수 있어 생성 단계에서는 정수나 고정소수점만 쓰고, 언어 표준 난수 대신 알고리즘이 고정된 난수(xoshiro 계열 등)를 직접 구현한다. 난수도 하나를 길게 굴리지 말고 단계마다, 영역마다, 청크마다 시드에서 따로 유도해야, 청크 하나를 만들 때 다른 청크를 먼저 만들 필요가 없다.

• 비율 맞추기: 노이즈 값에 “0.46보다 크면 바닥” 같은 문턱을 그으면 바닥 비율이 의도와 다르게 나온다. 여러 겹을 합친 노이즈는 값이 가운데로 몰리기 때문이다. 값의 분포를 표본으로 재 백분위로 바꾸면(히스토그램 평탄화) “43% 열림”이 실제로 43%가 된다.
• 다듬기: 칸마다 둘레 여덟 칸 중 다수를 따라가는 셀룰러 오토마타(cellular automata)를 몇 번 돌리면 외톨이 칸이 사라지고 동굴처럼 매끄러워진다. 반복 횟수가 곧 매끈함 손잡이다.
• 검사기: 규칙을 작게 나눠 시드 수천 개에 돌리고, 실패를 “생성 실패”가 아니라 어느 규칙이 몇 개 시드에서 깨졌는지, 후보가 몇 개였고 왜 떨어졌는지로 보고한다.

펄린 노이즈와 침식

끝없이 가도 땅이 나오는 게임은 땅을 저장하지 않는다. 좌표를 넣으면 높이가 나오는 함수를 들고 있다가 가까워진 곳만 그때 계산한다. 칸마다 난수를 뽑으면 이웃끼리 관계가 없어 가시밭이 되므로, 난수는 격자점에만 두고 사이를 부드럽게 잇는다.

• 값 노이즈(value noise): 격자점마다 높이를 뽑아 보간한다. 단순하지만 격자 방향의 결이 드러나기 쉽다.
• 펄린 노이즈(Perlin noise): 격자점마다 기울기 방향을 뽑고, 점까지의 벡터와 내적한 값을 보간한다. 결이 훨씬 옅다. 보간 곡선은 3t² − 2t³ 대신 6t⁵ − 15t⁴ + 10t³을 쓰면 양 끝에서 2차 도함수까지 0이라 격자선마다 음영에 줄이 서지 않는다.
• fBm(fractal Brownian motion): 주파수를 두 배, 세기를 절반으로 줄인 노이즈를 여러 겹(옥타브) 더해 큰 굴곡 위에 잔주름을 얹는다.
• 도메인 워핑(domain warping): f(p + fbm(p))처럼 함수에 넣는 좌표를 다른 노이즈로 먼저 비틀어 산줄기가 흘러내린 듯 휘게 한다.

노이즈 산은 물이 흐른 자국이 없다. 물방울 침식(hydraulic erosion)은 아무 데나 떨어뜨린 물방울을 내리막으로 한 걸음씩 굴린다. 방향은 내리막과 관성을 섞고, 실을 수 있는 흙의 양은 경사·속도·물의 양에 비례한다. 덜 실었으면 바닥을 깎아 담고, 넘치면 내려놓고, 물은 걸음마다 조금씩 증발한다. 한 칸만 깎으면 아주 가는 홈이 생기니 깎는 양을 둘레 여러 칸에 붓처럼 나눈다. 수십만 번 되풀이하면 골짜기가 파이고 기슭에 흙이 쌓인다.

• 강 찾기: 칸마다 여덟 이웃 중 가장 낮은 쪽으로 화살표를 긋고, 각 칸으로 흘러드는 칸 수를 센다(흐름 누적). 그 값이 큰 칸이 강이다.
• 웅덩이 메우기: 둘레가 다 높은 오목한 칸에서는 화살표가 갈 곳이 없어 강이 산 중턱에서 끊긴다. Priority-Flood는 바다(가장자리)에 닿은 칸을 우선순위 큐에 넣고 가장 낮은 칸부터 꺼내며, 꺼낸 칸보다 낮은 이웃을 그 높이까지 채운다. 채울 때 아주 작은 값 ε만큼 더 올리면 채운 평지에도 바다 쪽 기울기가 남아 물이 끝까지 흐른다.
• 기후로 고르는 바이옴: 바이옴을 구역마다 노이즈로 뽑으면 사막 옆에 설원이 붙는다. 추위(위도·고도)와 습도(물에서 먼 정도)를 먼저 만들고, 두 값의 단계를 짝지은 표에서 고른다.
• 나무 심기: 난수로 뿌리면 뭉친 곳과 빈 곳이 생긴다. 어떤 두 점도 r보다 가깝지 않게 뿌리는 포아송 원반 샘플링은 아래 절에서 따로 다룬다.
• 나무 모양: L-시스템(L-system)은 F → F[+F]F[−F]F 같은 글자 바꾸기 규칙을 글자열 전체에 동시에 적용하고, 거북이가 글자를 읽으며 가지를 긋는다. 글자 수가 세대마다 몇 배씩 불어나므로 세대 수가 곧 예산이다.

끝없는 세계로 넓히면 두 가지가 더 걸린다. 옛 펄린 구현처럼 256칸짜리 순열표에서 난수를 꺼내면 256칸마다 같은 산이 반복되므로, 좌표 두 수를 통째로 섞는 해시를 쓴다. 침식은 물방울이 조각 경계를 넘어 흐르니 조각마다 따로 깎으면 경계에 절벽이 선다. 둘레에 여유 칸을 두고 넓게 깎은 뒤 가운데만 쓰면 줄어든다. 조각 하나를 만드는 데 한 프레임보다 오래 걸리면, 플레이어가 다가오기 전에 뒤에서 미리 만들어 둬야 한다.

포아송 원반: 고르게, 그러나 격자 티 없이

숲에 나무를 심거나 들판에 바위를 놓을 때 좌표를 균일 난수로 뽑으면 생각보다 고르지 않다. 난수는 “어디든 같은 확률”일 뿐이라 우연히 서너 그루가 겹쳐 서고, 그 옆은 휑하게 빈다. 반대로 격자 칸마다 하나씩 놓으면 줄이 보인다. 칸 안에서 위치를 조금 흔드는 지터 격자(jittered grid)는 싸지만, 이웃 칸의 점끼리 경계에서 거의 맞붙을 수 있고 격자 결도 희미하게 남는다.

포아송 원반 샘플링(Poisson disk sampling)은 규칙 하나만 지킨다. 어떤 두 점도 최소 거리 r보다 가깝지 않다. 이렇게 뽑은 점은 뭉침이 없으면서 반복되는 무늬도 없다. 눈에 거슬리는 큰 얼룩(저주파 성분)이 적은 이런 분포를 블루 노이즈(blue noise)라고 부르며, 렌더링의 표본 위치나 디더링에도 같은 성질을 쓴다.

1. 배경 격자: 칸 한 변을 r/√2로 잡으면 칸의 대각선이 r이라, 한 칸에는 점이 많아야 하나다. 칸마다 점 하나만 기억하면 되고, 새 후보의 가까운 점은 둘레 5×5칸만 보면 다 나온다.
2. 활성 목록: 첫 점을 아무 데나 놓고 “아직 둘레에 자리가 남았을지 모르는 점” 목록에 넣는다.
3. 고리에서 후보 뽑기: 목록에서 점 하나를 골라, 그 점에서 r~2r 떨어진 고리 안에 후보를 몇십 개까지 차례로 뽑는다. r보다 가까운 점이 없는 후보가 나오면 놓고 목록에 넣는다.
4. 지우기: 정한 횟수 안에 아무 후보도 못 놓으면 그 점 둘레는 꽉 찼다고 보고 목록에서 뺀다. 목록이 비면 끝이다. 점마다 시도 횟수가 상한이 있어 전체 비용이 점 수에 비례한다.

• 밀도 지도: r을 상수 대신 좌표의 함수로 두면 물가에서는 빽빽하고 산등성이에서는 드문 숲이 된다. 습도·높이 같은 다른 지도에서 r을 읽으면 된다.
• 크기 순서로 겹 쌓기: 큰 나무를 큰 r로 먼저 뿌리고, 덤불은 작은 r로 뿌리되 큰 나무의 줄기 둘레도 피하게 한다. 큰 것부터 놓아야 작은 것이 빈틈을 메운다.
• 재현성: 결과가 난수 순서에 따라 달라지므로 시드를 고정해야 같은 숲이 나온다. 끝없는 세계에서는 청크마다 따로 뿌리면 경계에서 규칙이 깨지니, 미리 만든 이어 붙일 수 있는 점 무늬를 타일처럼 깔아 쓰기도 한다.

다각형 지도: 높이와 습도로 고르는 바이옴

노이즈 하나로 높이를 만들면 섬 가운데에 오목한 분지가 생기고, 강을 흘리면 분지에 고인다(위의 웅덩이 메우기). 순서를 바꿔 해안선을 먼저 정하고 높이를 거기서 끌어내면 이런 문제가 처음부터 생기지 않는다. 칸 수백만 개짜리 격자 대신 다각형 몇천 개로 지도를 만들면 이 계산이 그래프 위의 일이 되어 가볍다. 단계별 결과를 직접 만져 볼 수 있는 지도 생성기 데모가 이 흐름을 잘 보여 준다.

1. 다각형 만들기: 점을 몇천 개 뿌리고 보로노이 다각형을 만든다. 각 점을 자기 다각형의 무게중심으로 옮기고 다시 만드는 일을 몇 번 하면(로이드 완화, Lloyd relaxation) 크기가 고르게 된다. 이웃 다각형의 중심끼리 이은 선은 들로네 삼각분할(Delaunay triangulation)이고, 다각형의 꼭짓점과 변까지 셋이 서로를 가리키는 그래프가 된다.
2. 땅과 물: 다각형마다 땅인지 물인지 정한다. 노이즈 값과 “가운데에서 얼마나 먼가”를 섞어 문턱을 그으면 섬 모양이 된다. 지도 가장자리에서 물을 따라 채워 가며 닿는 물은 바다, 땅에 갇혀 닿지 않는 물은 호수다.
3. 높이: 해안에서 몇 걸음 떨어졌는지를 너비 우선 탐색으로 재 그대로 높이로 쓴다. 해안에서 멀수록 높으니 땅의 어느 점에서도 바다까지 내리막 길이 있다. 그다음 낮은 땅이 많고 산은 드물도록 값을 원하는 분포로 다시 펴 준다.
4. 강: 높은 꼭짓점 몇 개에서 출발해 가장 낮은 이웃 꼭짓점으로 변을 따라 내려간다. 내리막이 보장되니 강은 반드시 바다나 호수에 닿는다. 두 강이 만나면 물의 양을 더해 아래쪽을 굵게 그린다.
5. 습도: 강과 호수, 즉 민물에서 멀어질수록 줄어들게 퍼뜨린다. 강이 지나는 골짜기는 젖고 강에서 먼 고원은 마른다.

바이옴은 높이와 습도 두 단계의 짝으로 표에서 고른다(표의 칸 구성은 예시다). 노이즈로 바이옴을 직접 뽑을 때와 달리 사막 바로 옆에 우림이 붙는 일이 드물고, 강을 따라 초록 띠가 생긴다. 격자 지도에서도 같은 순서를 쓸 수 있다. 높이 노이즈 하나, 습도 노이즈 하나를 따로 만들어 칸마다 두 값으로 표를 읽으면 된다. 노이즈 두 장으로 지도를 만드는 과정은 노이즈로 지도 만들기 글에 단계별로 나와 있다.

• 다각형이 곧 게임 단위: 다각형 하나가 영토 한 칸, 마을 자리 하나가 되므로 전략 지도의 지역 나누기와 바로 이어진다. 그래프가 작아 지역 사이 길찾기도 싸다.
• 그릴 때는 다듬는다: 다각형 경계를 그대로 그리면 직선 조각이 보인다. 변을 노이즈로 구불구불하게 쪼개거나, 다각형 값을 격자로 옮긴 뒤 부드럽게 칠한다.

육각 격자: 좌표 셋으로 다룬다

사각 격자에는 이웃이 두 종류다. 변을 맞댄 네 칸은 거리 1, 꼭짓점만 맞댄 대각선 네 칸은 거리 √2다. 그래서 “대각선 이동을 허용하나, 비용은 얼마로 하나”를 매번 정해야 한다. 육각 격자는 이웃 여섯 칸이 모두 변을 맞대고 중심까지 거리도 같다. 전략 게임과 보드게임식 지도가 육각을 즐겨 쓰는 이유다. 대가는 좌표다. 줄마다 반 칸씩 밀린 칸을 2차원 배열에 담으면 홀수 줄과 짝수 줄의 이웃 규칙이 달라 계산이 지저분해진다.

깔끔한 방법은 큐브 좌표(cube coordinates)다. 육각 격자를 정육면체를 쌓아 놓고 대각선 방향에서 내려다본 단면으로 보고, 칸마다 세 좌표 q, r, s를 주되 언제나 q + r + s = 0이 되게 한다. 값이 둘이면 셋째는 정해지니 저장은 q, r 둘만 하고(축 좌표, axial coordinates) 계산할 때 s를 꺼내 쓴다.

• 이웃: 여섯 방향은 (+1, −1, 0)처럼 세 좌표 중 둘을 +1과 −1로 바꾸는 여섯 가지 조합이다. 줄의 홀짝을 따질 필요가 없다.
• 거리: 두 칸의 좌표 차이를 구해 max(|dq|, |dr|, |ds|)를 쓴다. 세 절댓값 합의 절반과 같다. 이 값은 A*의 휴리스틱으로도 정확하다.
• 범위: 거리 N 안의 칸은 세 좌표가 모두 −N~N이고 합이 0인 칸이다. 이중 반복문 하나로 다 나오고, 개수는 3N(N+1)+1이다(N = 2면 19칸, 3이면 37칸).
• 마우스 클릭: 화면 좌표를 거꾸로 변환하면 소수 좌표가 나온다. 셋을 각각 반올림하면 합이 0에서 어긋날 수 있으니, 반올림으로 가장 크게 바뀐 좌표 하나를 나머지 둘에서 다시 계산한다.
• 선 긋기와 회전: 두 칸 사이를 n등분한 점마다 위의 반올림을 하면 칸을 잇는 직선(사거리·시야 판정)이 된다. 세 좌표를 한 자리씩 돌리고 부호를 뒤집으면 60도 회전이다.

저장은 여전히 2차원 배열이 편하다. 배열 인덱스로는 줄마다 밀린 좌표(오프셋 좌표)를 쓰고, 계산하기 직전에 큐브 좌표로 바꿨다가 결과를 다시 돌려 놓는 식으로 둘을 나눠 쓴다. 방향 이름 짓기, 꼭짓점 위·변 위 배치, 고리와 나선 순회까지 그림으로 정리한 육각 격자 안내서에 자세하다.

오토타일과 타일맵

생성기가 만든 것은 “이 칸은 벽, 저 칸은 바닥”이라는 배열이다. 벽 칸을 한 가지 그림으로 칠하면 벽이 아니라 얼룩으로 보인다. 벽은 이웃과 이어진 덩어리의 실루엣으로 읽히므로, 어느 방향으로 이어져 있는지에 따라 다른 그림이 필요하다. 이웃을 보고 그림을 고르는 것이 오토타일(autotile)이다.

이웃 여덟 칸이 벽인지를 비트로 읽으면 256가지다. 그런데 대각선 칸은 양옆 두 변이 모두 벽일 때만 모양에 영향을 준다. 북쪽이 비어 있으면 그 모서리는 어차피 바깥이라 북동쪽이 무엇이든 같은 그림이다. 이렇게 의미 없는 대각선 비트를 지우면 서로 다른 모양은 47가지만 남는다. 256칸짜리 변환 표를 미리 구워 두면 칸마다 배열을 한 번 읽어 그림을 고른다.

• 변주는 좌표 해시로: 같은 모양의 벽도 칸마다 무늬를 조금씩 다르게 하되, 난수 대신 좌표를 넣으면 나오는 고정 해시로 고른다. 여러 클라이언트가 아무것도 주고받지 않아도 같은 무늬를 고르고, 월드 시드를 다시 굴려도 그대로인 지형의 무늬는 그대로다.
• 위에서 본 벽에 높이 주기: 탑다운 시점에서 벽 칸에는 윗면을, 그 아래(남쪽) 칸에는 벽의 앞면을 덧그린다. 앞면은 남쪽이 열린 모양에만 붙는다.
• 앞뒤 정렬: 벽을 이루는 타일맵 여러 장과 캐릭터 스프라이트가 같은 정렬 순서를 쓰고 앞뒤는 y좌표로 가르면(Y 정렬), 캐릭터가 벽 뒤로 가면 가려지고 앞으로 나오면 벽을 덮는다.
• 청크 이음매: 청크 가장자리 칸의 마스크를 완성하려면 이웃 청크를 읽어야 한다. 앞면처럼 “위 칸의 모양”까지 보는 그림이 있으면 두 칸 밖까지 필요하다. 청크 생성이 좌표만 받는 순수 함수라 아직 화면에 없는 이웃도 미리 물어볼 수 있다.

화면과 게임 판정이 어긋나지 않게 하는 원칙도 같다. 2D 조명의 그림자 모양을 손으로 따로 만들지 않고 충돌체를 합친 외곽선에서 뽑으면, 이동은 막는데 빛은 통과하는 벽이 생길 수 없다. 미니맵·AI·시야가 각자 지도를 만들지 않고 같은 청크 데이터를 읽게 하면, 미니맵의 길이 화면에서는 벽인 일이 없다. 엔진에 딸린 규칙 타일(Rule Tile) 같은 기능은 한 칸에 그림 하나를 고르는 데는 편하지만, 한 마스크에서 여러 장의 타일을 동시에 고르거나 다른 칸에 그려야 할 때는 직접 짜는 편이 낫다.

파동함수 붕괴(WFC)가 하는 일과 못 하는 일

파동함수 붕괴(Wave Function Collapse, WFC)는 디자이너가 “무엇 옆에 무엇이 올 수 있나”라는 인접 규칙만 적으면 배치를 알고리즘이 하는 방법이다. 이름과 달리 양자역학과는 상관없고, 실체는 스도쿠와 같은 부류의 제약 충족 문제다. 예시 이미지에서 N×N 패턴을 뽑아 규칙을 자동으로 만드는 overlapping 모델과, 인접 표를 직접 받는 tiled 모델이 있다. Bad North, Townscaper, Caves of Qud 같은 게임이 썼다.

1. 칸마다 놓일 수 있는 타일 후보 전부를 들고 시작한다.
2. 관측(observe): 아직 안 정해진 칸 하나를 골라 남은 후보 중 하나로 확정한다. 보통 후보가 가장 적은(엔트로피가 가장 낮은) 칸을 고른다.
3. 전파(propagate): 그 확정 때문에 불가능해진 후보를 이웃에서 지우고, 줄어든 이웃의 이웃도 다시 본다. 제약 충족의 호 일관성(arc consistency, AC-3)과 같은 일이다.
4. 모든 칸이 정해지면 끝, 어느 칸의 후보가 0개가 되면 모순이다.

• 일하는 것은 전파다: 전파를 끄면 가중치대로 타일을 흩뿌리는 것과 같아 규칙이 마구 깨진다. 반대로 칸을 고르는 순서는 결과에 생각보다 덜 중요하다. 이미 정해진 칸 옆을 고르기만 하면 왼쪽 위부터 훑어도 잘 된다. 서로 모르는 결정을 판 여기저기에 흩뿌리는 무작위 순서가 모순을 부른다. 원저자도 최소 엔트로피를 고른 까닭으로 사람이 그림을 그리는 순서와 닮아 보기 좋다는 점을 들었다.
• 되돌림이 없다: 기본 WFC는 모순이 나면 한 수 되돌리지 않고 판 전체를 버리고 다시 한다. 빈 판에서는 모순이 드물지만, 입구·보스방처럼 미리 못 박아 둔 칸이 많을수록 실패가 잦아진다. 게임은 늘 뭔가를 미리 정해 두므로, 되돌림(backtracking)을 붙이거나 실패 횟수에 상한을 둔다.
• 전역 성질은 못 만든다: 인접 규칙은 맞닿는 두 칸 사이의 조건이라 “모든 길이 하나로 이어진다” 같은 판 전체의 성질을 표현할 수 없다. 규칙을 하나도 어기지 않았는데 도로가 여러 덩어리로 쪼개진다. 그래서 WFC를 생성 파이프라인의 중간 단계로 쓰고, 앞뒤를 연결을 보장하는 다른 기법으로 감싼다.
• 청크로 쪼개기 어렵다: 한 칸의 결정이 몇 칸 너머까지 번지므로 청크를 따로 만들면 이음매에서 규칙이 깨진다. 노이즈처럼 좌표만으로 청크를 만드는 방식과 정반대다.

정리하면 노이즈는 지역적으로 싸게 계산하는 대신 전역 성질을 포기하고 무한히 넓힐 수 있으며, WFC는 전역적으로 일관된 대신 판이 유한해야 한다. 끝없는 오픈월드는 노이즈를, 손으로 만든 듯한 마을이나 던전은 WFC를 쓰는 까닭이다.

미션 그래프와 솔버 검사: 만든 뒤 풀어 본다

게임 내용물은 보기만 좋으면 되는 게 아니라 작동해야 한다. 예를 들어 열쇠가 잠긴 문 너머에 놓이면 진행이 막히고, 단서가 모자라면 추리가 운에 맡겨진다. 생성기는 이런 조건을 보장해야 한다. 방법은 둘이다. 틀릴 수 없는 순서로 만들거나, 만든 뒤 풀이기(solver)로 검사해 통과한 것만 내놓는다. 대개 둘을 함께 쓴다.

• 건물: 쪼개기 문법(split grammar): 덩어리를 면으로, 면을 층으로, 층을 칸으로, 칸을 창·문으로 자르는 규칙을 차례로 적용한다. 창은 층 안에서만, 문은 1층 바닥에서만 나오게 짜여 있으니 층을 가로지르는 창이나 공중에 뜬 문이 애초에 나오지 않는다. 비탈에 세울 때는 집 자리를 먼저 평평하게 다진다.
• 던전: 미션 먼저, 공간은 나중: 할 일의 순서(입구 → 열쇠 → 잠긴 문 → 보스)를 그래프로 먼저 키우고, 방 배치는 그 그래프를 담도록 나중에 만든다. 열쇠는 늘 그 문보다 앞선 방에 놓인다. 검사는 (방, 가진 열쇠)를 상태 하나로 보고 시작 방에서 갈 수 있는 상태를 퍼뜨려 보스방에 닿는지 본다.
• 퍼즐: 풀이기부터 짠다: 풀이기가 추론만으로 풀어내는 판은 답이 있을 뿐 아니라 답이 하나다. 지뢰찾기는 판을 만든 뒤 풀이기가 막힌 곳 근처의 지뢰만 옮겨 다시 풀면 찍지 않아도 되는 판이 된다. 스도쿠는 꽉 찬 답에서 숫자를 하나씩 지우되, 지울 때마다 답의 수를 세어 둘째 답이 생기면 되돌린다. 답이 하나인 스도쿠는 단서가 최소 17개 필요하다는 것이 전수 탐색으로 증명돼 있다.
• 난이도: 풀이기에 허락한 추론의 종류가 곧 난이도다. 후보 지우기만으로 풀리면 쉬운 판, 넣어 보고 되돌리는 추론이 필요하면 어려운 판이다. 결국 풀이기가 못 푸는 퍼즐은 만들 수 없으니, 검사기는 생성기의 천장이기도 하다.

스도쿠 풀이기의 속은 WFC와 같다. 칸마다 후보를 두고, 하나가 정해지면 같은 줄·열·상자의 후보를 지우고, 후보가 빈 칸이 생기면 모순이다. 추리 사건에도 같은 틀을 쓸 수 있다. 저녁 한나절을 먼저 시뮬레이션해 누가 몇 분에 어느 방에 있었는지 기록하고, 그 기록에서 목격담과 알리바이를 단서로 뽑는다. 탐정 코드는 “이 사람만 거짓말한다”를 한 명씩 가정하고, 사람 × 분 칸마다 있을 수 있는 방을 후보로 두고 단서와 “1분에 옆방 하나만 움직인다”는 규칙으로 지워 간다. 모순 없이 살아남는 가정이 하나뿐인 사건만 내놓으면, 매번 새로 만든 사건이 늘 풀린다. 꼭 필요한 단서만 남기고 빼 보면 단서 수로 난이도를 고를 수 있다.

캐릭터 모델도 같은 태도로 만든다. 부품을 따로 붙이면 관절에서 표면이 서로 파고드니 몸 전체를 껍질 하나로 짜고, 숫자 검사로 안 보이는 문제(팔이 실루엣에 묻힘)는 렌더해서 본다. 애니메이션 파일 없이 걷게 하는 절차 애니메이션은 애니메이션 노트에 있다.

청크 스트리밍과 히스테리시스

오픈월드에 로딩이 없는 게 아니다. 세계를 같은 크기의 청크(chunk)로 나누고, 플레이어 둘레 반경 안의 청크만 메모리에 올리고 나머지는 내리는 것이다. 엔진들은 이것을 기능으로 만들어 뒀다. 언리얼 엔진의 월드 파티션은 월드를 격자 셀로 나눠 스트리밍 소스 둘레의 로딩 범위 안 셀을 올리고, Unity는 씬을 비동기로 얹는 API를 준다. 문제는 걷는 동안 올리는 일이 공짜가 아니라는 것이다.

• 프레임 예산: 청크 하나를 통째로 한 프레임에 세우면 그 프레임이 수백 ms가 되어 화면이 턱 걸린다(게임 성능 노트의 히치). 프레임마다 쓸 시간을 정해 두고, 가까운 청크부터 그 안에서만 오브젝트를 세우고 남은 것은 다음 프레임으로 넘긴다. 세우는 총량은 같고 언제만 다르다.
• 프리로드: 예산은 몇 개를 세우는지는 나누지만 어떤 메시를 처음 읽는 비용은 나누지 못한다. 곧 쓸 에셋을 미리 디스크에서 읽어 두는 몫이다.
• 히스테리시스(hysteresis): 켜는 선과 끄는 선이 같으면, 플레이어가 경계 위에서 조금만 흔들려도 같은 청크가 수백 번 켜졌다 꺼진다. 끄는 반경을 켜는 반경보다 조금 멀리 두면 작은 흔들림은 어느 선도 넘지 못한다. 온도 조절기가 20도에서 켜고 22도에서 끄는 것과 같은 까닭이다. 틈이 넓을수록 잠잠하지만 메모리에 더 오래 남는다.
• 오브젝트 풀(object pool): 나간 오브젝트를 부수지 않고 숨겨 뒀다 같은 메시가 들어오면 꺼내 쓴다. 할당과 가비지는 크게 줄지만, 통째로 세우는 프레임의 히치는 예산이 줄인다. 둘은 다른 비용이다.

반경으로 조금씩 바꾸는 방법이 안 통할 때도 있다. 두 구역이 메모리에 동시에 안 들어갈 만큼 크면 A를 다 내린 뒤에야 B를 올릴 수 있는데, 그사이 화면이 비면 안 된다. 그래서 두 구역 사이에 앞뒤가 안 보이고 시간이 걸리는 자리를 둔다. 좁은 벽 틈, 엘리베이터, 유난히 천천히 열리는 문이 그 자리다. 로딩 화면이 사라진 것이 아니라 통로가 로딩 화면 노릇을 한다.

복셀 청크와 면 컬링

마인크래프트에서 렌더 거리를 크게 올리면 플레이어 둘레의 블록 칸은 수억 개가 된다. 칸마다 물체(객체)를 두면 그 객체를 가리키는 주소만으로 메모리가 넘친다. 그래서 블록 하나하나는 객체가 아니라 청크 배열 속 숫자 하나로 저장된다. 떨어지는 모래처럼 움직일 때만 잠시 객체로 바뀌고, 화면에 그릴 때는 다른 블록에 가린 면을 아예 빼 버린다.

• 팔레트와 비트: 마인크래프트 자바 에디션은 청크를 높이 16칸짜리 조각(섹션, 16×16×16 = 4,096칸)으로 나누고, 조각 안에 나오는 블록 종류만 모은 목록(팔레트)을 둔 뒤 칸에는 목록 번호만 몇 비트로 적는다. 한 종류뿐인 조각(공기뿐인 하늘 등)은 칸마다 적지 않는다.
• 움직일 때만 물체: 떨어지는 모래는 아래가 비었을 때 칸의 번호를 지우고 떨어지는 엔티티가 되었다가, 내려앉을 칸에 다시 블록으로 놓일 수 있으면 번호로 돌아가고 아니면 아이템이 된다. 모래 기둥 밑에 횃불을 꽂으면 기둥이 통째로 아이템이 되는 요령이 이 규칙에서 나온다. 이웃이 바뀔 때만 깨어나므로 가만히 있는 칸은 아무도 들여다보지 않는다.
• 면 컬링(face culling): 블록마다 여섯 면을 다 그리면 땅속 면이 대부분이다. 조각의 메시를 만들 때 이웃이 꽉 찬 불투명 블록인 면은 건너뛴다. 땅이 꽉 찰수록 버리는 몫이 커서, 실제 지형에서는 면 대부분이 사라진다.

• 그리디 메싱(greedy meshing): 같은 종류의 이웃한 면을 큰 사각형 하나로 합쳐 사각형 수를 더 줄인다. 마인크래프트 기본 렌더러는 합치지 않지만 많은 복셀 엔진이 쓴다.
• 보이지 않는 조각 건너뛰기: 조각마다 “어느 면에서 어느 면으로 투명한 칸이 이어지는가”를 미리 적어 두고, 카메라가 있는 조각부터 통하는 면으로만 넓혀 가며 그릴 조각을 고른다. 동굴 안에서는 바깥 산을 아예 그리지 않는다.

다른 블록 게임도 뼈대는 같고 세부 규칙이 다르다. 떨어질 블록을 곧바로 엔티티로 만들거나, 내려앉을 칸의 횃불을 부수고 그 자리에 앉는 게임도 있다. 그리는 쪽 이야기는 렌더링·빛 노트와 GPU 노트에 이어진다.

듀얼 컨투어링: 둥글게 파이는 복셀 땅

오랫동안 게임 지형의 표준은 높이 지도(height map)였다. 바닥 격자의 자리마다 높이 하나만 적으니 싸고 매끈하지만, 자리마다 높이가 하나뿐이라 동굴이나 옆으로 뚫린 굴, 튀어나온 바위(오버행)를 담지 못한다. 옆에서 공을 밀어 넣으면 굴이 아니라 위에서부터 홈이 파인다. 그래서 굴이 필요하면 지형에 구멍을 내고 따로 만든 모형을 끼운다.

복셀(voxel)은 공간을 칸으로 나눠 어떤 모양이든 담는다. 마인크래프트처럼 칸마다 “있다·없다”만 적으면 칸 모양 그대로 네모나게 보인다. 둥글게 파이는 땅은 격자점마다 얼마나 찼는지(밀도, 0~1)를 적고, 값이 0.5가 되는 자리를 이어 겉면을 다시 뽑는다. 이웃한 두 격자점이 0.3과 0.8이면 0.5는 그 사이 비율 자리에 있으니, 칸은 네모여도 겉면은 비스듬하게 지나간다. 공이 박히면 공 모양만큼 밀도를 빼고 그 둘레 겉면만 다시 뽑는다. 닌텐도는 동키콩 바난자의 지형이 복셀이라 거의 모든 것을 부술 수 있다고 인터뷰에서 밝혔다.

• 마칭 큐브(marching cubes, 1987): 칸의 여덟 꼭짓점이 안인지 밖인지로 256가지 경우를 나누고, 경우마다 정해 둔 삼각형을 교점에 놓는다. 단순하고 빠르지만 날카로운 모서리가 뭉개진다.
• 듀얼 컨투어링(dual contouring, 2002): 칸마다 겉면 점을 하나 두고 이웃 칸의 점끼리 잇는다. 교점마다 그 자리의 면 방향(법선)까지 기억해 두고(허밋 데이터), 그 면들까지 거리 제곱의 합이 가장 작은 자리(QEF, quadratic error function)에 점을 놓는다. 평평한 곳에서는 평균과 같고, 모서리가 든 칸에서는 점이 정확히 모서리에 선다.

대가는 계산이다. 듀얼 컨투어링은 칸마다 작은 연립방정식을 풀어야 해 평균 자리보다 비싸다. 그래서 땅을 조각으로 나누고 건드린 조각만 다시 뽑으며, 멀리 있는 조각은 칸을 합친 낮은 해상도로 뽑는다(LOD). 칸마다 재질 값을 두면 바위는 덜 파이고 흙은 잘 파이게 할 수 있다. 칸을 한 축으로 두 배 촘촘히 하면 자료는 여덟 배가 되므로, 빈 조각에는 메모리를 주지 않는 식으로 아껴 쓴다.