이 글을 게시한 후 2년 동안, 저는 이 알고리즘을 개선하여 Generate Worlds라는 실시간 세계 생성기(real-time world generator)를 만드는 데 매진했습니다. 이 도구를 통해 사용자는 자신만의 2D 및 3D 타일 세트(tile sets)를 설계하고, 생성된 세계를 1인칭 시점으로 탐험할 수 있습니다. 이를 설명하는 포스트가 있으며, itch.io에서 구매할 수 있습니다.

다음은 Generate Worlds의 작동 모습입니다:

서론 (Introduction)

이 포스트는 단순한 색상 타일 세트와 해당 타일의 배치 제약 조건(constraints)을 사용하여 복잡한 절차적 세계(procedural worlds)를 생성하는 두 가지 알고리즘을 설명합니다. 타일 세트를 신중하게 설계함으로써 도시가 있는 풍경이나 복잡한 내부 구조를 가진 던전(dungeons)과 같이 흥미로운 절차적 생성 콘텐츠를 만들 수 있음을 보여드리겠습니다. 아래 영상은 43개의 색상 타일에 인코딩된 규칙을 기반으로 절차적 세계를 생성하는 시스템을 보여줍니다.

아래 이미지는 위 영상에서 세계를 생성하는 데 사용된 타일 세트를 보여줍니다. 세계에는 이를 실제 환경으로 인식하는 데 필요한 상상력을 돕기 위한 주석이 달려 있습니다.

우리는 타일링(tiling)을 각 격자 칸(grid square)에 타일 중 하나가 놓여 있는 유한한 그리드(finite grid)로 정의하겠습니다. 또한, 인접한 타일의 가장자리(edges)를 따라 색상이 동일해야 하는 상태를 유효한 세계(valid world)로 정의하겠습니다.

이것이 타일링에 대한 유일한 구체적인 규칙입니다: 타일 가장자리 색상이 일치해야 합니다. 모든 상위 수준의 구조는 여기서부터 파생됩니다.

유효한 타일링은 다음과 같습니다:

이것은 물, 해변, 풀밭, 건물이 있는 마을(파란색 직사각형), 그리고 눈 덮인 산이 있는 지도를 나타내는 타일링입니다. 검은색 선은 타일 사이의 경계를 나타냅니다.

이것은 세상을 묘사하고 생성하는 매우 흥미로운 방식이라고 생각합니다. 왜냐하면 매우 빈번하게, 절차적 생성 (procedural generation) 알고리즘들은 하향식 (top-down) 접근 방식을 취하기 때문입니다. 예를 들어, L-시스템 (L-systems)은 객체의 재귀적 묘사에 의존하며, 여기서 상위 레벨의 큰 세부 사항들이 하위 레벨의 세부 사항들보다 먼저 결정됩니다. 이 접근 방식에 문제가 있는 것은 아니지만, 단순한 하위 레벨의 관계만을 인코딩할 수 있는 타일 세트(예: 바닷물과 풀밭 사이에는 반드시 해변이 있어야 함, 건물은 볼록한 90도 모서리만 가질 수 있음)를 만들고, 이를 통해 상위 레벨의 패턴(예: 정사각형 건물)이 나타나는 것을 지켜보는 것이 흥미롭다고 생각합니다.

타일링은 NP-완전 제약 충족 문제 (NP complete Constraint Satisfaction Problem)이다

제약 충족 문제 (Constraint Satisfaction Problems, CSPs)에 익숙한 독자라면, 유한한 세계를 타일링하는 것이 CSP라는 점이 이미 명확할 것입니다. CSP에서는 변수(variables)의 집합, 각 변수가 가질 수 있는 값의 집합(도메인 (domain)이라 불림), 그리고 제약 조건 (constraints)의 집합이 존재합니다. 우리에게 있어 변수는 지도의 위치이며, 각 변수의 도메인은 타일 세트이고, 제약 조건은 타일들이 인접한 타일과 가장자리를 따라 서로 일치해야 한다는 것입니다.

직관적으로, 사소하지 않은 타일링을 올바르게 생성하는 문제는 어렵습니다. 타일 세트가 임의의 장거리 의존성 (long range dependencies)을 인코딩할 수 있기 때문입니다. 형식적으로, 타일 세트를 일반적인 관점에서 고려할 때 이는 NP-완전 제약 충족 문제 (NP complete constraint satisfaction problem)입니다. 타일링을 생성하기 위한 단순한 (naive) 알고리즘은 타일링 공간을 전수 조사하게 되며 지수 시간 (exponential time) 내에 실행됩니다. 우리의 희망은 휴리스틱 (heuristics)에 의해 가속화된 탐색을 통해 해결 가능한 타일 세트를 사용하여 흥미로운 세계를 만드는 것입니다. 다른 선택지는 거의 정확하지만 소수의 잘못된 배치가 있을 수 있는 타일링을 만드는 것입니다. 저는 몇몇 흥미로운 타일 세트에서 잘 작동하는 두 가지 알고리즘을 찾아냈으며, 아래에 이를 설명하겠습니다.

방법 1: 백점핑 (Backjumping)을 이용한 탐욕적 배치 (Greedy Placement)

무작위 위치를 계속 선택하여 유효한 타일을 배치합니다. 만약 막히게 되면, 일부를 제거하고 다시 시도합니다.

전체 맵을 UNDECIDED(미결정) 상태로 초기화합니다.
맵에 UNDECIDED 타일이 남아 있는 동안:
맵에 배치 가능한 유효한 타일이 있다면
...

타일 세트(tile set)로부터 타일링(tiling)을 생성하기 위해 제가 처음 시도한 접근 방식은, 전체 그리드(grid)를 미정의(undefined) 상태로 시작하여, 유효한 위치에 무작위 타일을 반복적으로 배치하거나, 만약 유효한 위치가 없다면 미정의 타일 근처의 작은 영역을 미정의 상태로 설정하고 탐욕적 배치(greedy placement)를 계속하는 것이었습니다. "탐욕적 배치 (greedy placement)"란, 이 배치가 기존 타일을 제거하지 않고서는 완성할 수 없는 부분적인 타일링을 만들게 될지 여부와 상관없이, 타일의 모든 가장자리가 기존 타일과 일치하는 한 계속해서 타일을 배치하는 전략을 의미합니다. 이러한 상황이 발생하여 더 이상 타일을 배치할 수 없게 되면, 이전에 배치했던 일부 타일을 제거해야 합니다. 하지만 어떤 타일을 제거하는 것이 이상적인지는 말할 수 없습니다. 왜냐하면 만약 그 문제를 해결할 수 있다면, 애초에 타일을 똑똑하게 배치하는 문제 또한 해결할 수 있었을 것이기 때문입니다. 주어진 영역에 대한 유효한 타일링을 찾을 기회를 알고리즘에 한 번 더 주기 위해, 우리는 해당 위치 주변의 모든 타일을 미정의 상태로 설정하고 탐욕적 배치 전략을 계속합니다. 결국 유효한 타일링이 발견되기를 기대하지만, 이것이 보장되지는 않습니다. 알고리즘은 유효한 타일링이 발견될 때까지 계속 실행될 것이며, 이는 영원히 지속될 수도 있습니다. 이 알고리즘은 타일 세트가 해결 불가능한 상태인지 감지하는 능력이 없습니다.

이 알고리즘이 멈출 것이라는 보장은 없습니다. 색상을 전혀 공유하지 않는 두 개의 타일로 구성된 단순한 타일 세트(tile set)는 이 알고리즘을 영원히 루프(loop)에 빠지게 할 것입니다. 훨씬 더 단순한 사례로는 위아래 색상이 서로 다른 하나의 타일이 있을 수도 있습니다. 유효한 타일링 (tiling)을 생성할 수 없는 타일 세트를 어떤 방식으로든 확인하는 것이 합리적일 수 있습니다. 우리는 타일 세트가 무한한 평면을 채울 수 있다면 확실히 유효하다고 말할 수 있을 것입니다. 어떤 경우에는 타일 세트가 무한한 평면을 채울 수 있는지 여부를 증명하거나 반증하는 것이 명확하게 가능하지만, 이 문제는 일반적으로 결정 불가능 (undecidable)한 것으로 밝혀졌습니다. 따라서 유효한 타일링을 생성할 수 있는 타일 세트를 만드는 것은 타일 세트 설계자의 몫입니다.

이 알고리즘은 이 포스트 상단의 영상에 등장하는 던전 타일 세트 (dungeon tile set)에 대한 좋은 해답을 찾아내지 못합니다. 이 알고리즘은 더 단순한 타일 세트에서는 잘 작동합니다. 우리는 타일 간의 전이 (transition) 유형이 매우 다양하고 많은 규칙(예: 도로는 건물에서 시작하고 끝남)이 인코딩된 더 복잡한 타일 세트를 해결하고 싶습니다. 우리는 앞을 내다보고(look ahead), 해당 배치가 미래의 배치에 어떤 선택지를 남겨둘지 어느 정도 인지하면서 타일을 배치할 수 있는 알고리즘이 필요합니다. 이를 통해 복잡한 타일 세트를 효율적으로 해결할 수 있을 것입니다.

제약 충족 (constraint satisfaction) 관점에서

이 알고리즘은 백점핑 무작위 탐색 (backjumping random search)입니다. 각 단계에서 우리는 단일 변수 (variable)를 할당하려고 시도합니다. 만약 할당할 수 없다면, 해당 변수와 제약 조건 (constraints)으로 연결된 모든 변수의 할당을 해제합니다. 이를 백점핑 (backjumping)이라고 부르며, 한 번에 하나의 변수만 할당 해제하는 백트래킹 (backtracking)과는 다릅니다. 백트래킹에서는 일반적으로 변수를 할당했던 순서의 역순으로 할당 해제하지만, 백점핑에서는 당면한 문제의 구조에 따라 변수를 할당 해제합니다. 특정 위치에 어떤 타일도 배치할 수 없다면, 그 타일들의 배치가 해결 불가능한 상황을 만들었으므로 인접한 타일들의 배치를 변경해야 한다는 것은 타당한 논리입니다. 반면 백트래킹은 공간적으로 멀리 떨어져 있지만 우연히 최근에 할당된 변수들을 할당 해제하게 만들 수도 있습니다.

이 탐색은 어떠한 지역적 일관성 (local consistency) 방법도 채택하지 않습니다. 즉, 우리는 미래의 단 한 단계의 탐색에서조차 나중에 해결 불가능한 상황을 초래하지 않을 타일을 배치하려는 시도를 하지 않습니다. 몇 개의 타일 떨어진 곳의 가능한 배치에 미칠 영향을 추적함으로써 탐색을 가속화하는 것이 가능할 수도 있습니다. 이를 통해 탐색이 수행한 작업을 되돌리는 데 너무 많은 시간을 소비하지 않기를 바랍니다. 이것이 다음 알고리즘이 하는 일입니다.

방법 2: 지역 정보 전파를 이용한 가장 제약이 많은 배치 (Most Constrained Placement with Local Information Propagation)

각 위치의 타일에 대한 확률 분포 (probability distribution)를 유지하며, 배치 결정이 내려질 때 이 분포들에 비지역적 (nonlocal) 업데이트를 수행합니다. 절대 백트래킹을 하지 않습니다.

다음으로, 저는 반드시 종료가 보장되며 제가 시도해 본 모든 타일 세트에 대해 더 보기 좋은 결과를 생성하는 알고리즘을 설명하겠습니다. 이 알고리즘은 훨씬 더 복잡한 타일 세트에 대해서도 거의 유효한 타일링 (tilings)을 생성할 수 있습니다. 트레이드오프 (tradeoff)는 이 알고리즘이 출력값이 항상 유효한 타일링임을 보장하지는 않는다는 점입니다. 최적화 (Optimizations) 섹션에서는 이 기술이 대규모 타일 세트와 맵에서도 빠르게 실행될 수 있도록 돕는 최적화 기법들을 설명합니다.

유효한 타일링 (tiling)을 생성하는 난이도는 두 타일 유형 사이를 이동하는 데 필요한 전이 (transitions)의 수에 의해 크게 결정됩니다. 단순한 타일 세트에는 모래, 물, 풀만 포함될 수 있습니다. 만약 풀과 물이 서로 맞닿을 수 없다면, 두 유형 사이에는 모래로의 전이가 필요할 것입니다. 이는 이전 알고리즘이 쉽게 해결할 수 있는 간단한 사례입니다. 더 복잡한 사례는 타일 유형의 많은 중첩된 단계들을 포함할 수 있습니다. 예를 들어, 심해, 물, 모래, 풀, 고원, 산, 그리고 설산이 있을 수 있습니다. 만약 이 유형들이 제가 언급한 순서 외에는 서로 맞닿을 수 없다고 가정한다면, 이 모든 유형이 나타나기 위해서는 맵에 7개의 전이가 존재해야 합니다. 또한, 특정 유형의 타일에서 시작하고 끝나야 하는 도로와 같이, 타일 간에 자연스럽게 장거리 의존성 (long-distance dependencies)을 생성하는 타일을 만듦으로써 더 높은 복잡성을 도입할 수 있습니다.

직관적으로, 이 문제를 해결하기 위한 알고리즘은

예를 들어, 지도에 물 (water) 타일이 배치된다면, 그 옆에 있는 타일들은 반드시 일정량의 물을 포함해야 합니다. 그 옆의 타일들 또한 물을 포함할 수 있지만, 만약 원래의 물 옆에 해변 (beach)이 배치되었다면 풀밭 (grass)과 같은 다른 가능성도 존재할 수 있습니다. 배치된 타일에서 멀어질수록 가능한 타일의 유형은 더욱 많아집니다. 이러한 관찰을 구체적으로 활용하기 위해, 우리는 원래 타일 근처의 각 타일 배치에 도달할 수 있는 방법의 수를 셀 수 있습니다. 어떤 경우에는 주어진 거리 동안 하나의 타일이 다른 타일로 전이 (transition)될 수 있는 전이 시퀀스 (transition sequence)가 단 하나뿐일 수도 있습니다. 반면, 다른 경우에는 가능한 전이 시퀀스가 매우 많을 수도 있습니다. 일단 타일을 배치하고 나면, 우리가 배치한 타일에서 근처 타일들로 전이할 수 있는 방법의 수를 계산함으로써 근처 위치의 타일 확률 분포 (probability distributions)를 결정할 수 있습니다. 알고리즘이 수행하는 "룩 어헤드 (look ahead)"는 이러한 전이 횟수를 추적하고, 이를 향후 배치할 타일을 선택하기 위한 확률 분포로 취급하는 것입니다.

각 타임 스텝 (time step)마다, 알고리즘은 아직 결정되지 않은 모든 타일 위치를 조사하며, 각 위치는 타일들에 대한 확률 분포를 가집니다. 그리고 타일을 배치할 위치 하나를 선택합니다. 알고리즘은 지도에서 엔트로피 (entropy)가 가장 낮은 분포를 가진 위치를 선택합니다. 낮은 엔트로피를 가진 다항 분포 (multinomial distributions)는 확률이 몇 개의 모드 (modes)에 집중되는 경향이 있으므로, 이를 먼저 배치한다는 것은 우리가 이미 어느 정도 제약 조건 (constraints)을 가지고 있는 타일들을 먼저 배치한다는 것을 의미합니다. 이것이 바로 알고리즘이 이미 결정된 타일 근처의 타일들을 먼저 채워 넣는 이유입니다.

이것은 제가 이 문제를 해결하기 위해 구현한 가장 효과적인 알고리즘이며, 실행되는 동안 멋진 시각화 (visualization)를 제공할 수 있다는 추가적인 장점도 있습니다. 일종의 백트래킹 (backtracking)을 추가함으로써 이 알고리즘을 개선하는 것이 가능할 수도 있습니다. 만약 최종 타일링 (tiling)에 유효하지 않은 위치가 존재한다면, 근처의 타일 배치를 취소한 다음 해당 위치의 결과 분포 (distributions)로부터 다시 샘플링 (resampling)함으로써 최종 타일링에 대한 해결책을 찾을 수 있을지도 모릅니다. 물론, 유효한 타일링이 발견될 때까지 항상 탐색을 계속하기로 결정한다면, 현재 우리가 가지고 있는 유한한 실행 시간 보장 (bounded run time guarantee)을 잃게 될 것입니다.

최적화 (Optimizations)