Wave Function Collapse를 이용한 절차적 생성 (Procedural Generation)

(2022-05-03 수정: Wave Function Collapse 알고리즘이 "Model Synthesis"라고 불리는 기존 알고리즘에서 큰 영감을 받았다는 사실을 알게 되었습니다. 더 자세한 정보를 위해 저자의 웹사이트 링크가 포함된 추가 읽기 섹션을 추가했습니다.)

Wave Function Collapse (WFC)는 어떤 타일이 서로 인접할 수 있는지에 대한 규칙과 각 타일이 상대적으로 얼마나 자주 나타나야 하는지에 대한 규칙에 따라 타일 모음을 배치하여 이미지를 생성하는 절차적 생성 (Procedural Generation) 알고리즘입니다. 이 알고리즘은 출력 이미지의 각 픽셀에 대해 그곳에 배치될 수 있는 타일들의 확률 분포 (Probability Distribution)를 유지합니다. 알고리즘은 "붕괴 (Collapse)"시킬 픽셀을 반복적으로 선택하며, 해당 픽셀의 분포를 기반으로 사용할 타일을 결정합니다. WFC라는 이름은 양자 물리학 (Quantum Physics)에서 유래되었습니다.

이 포스트의 목표는 WFC 알고리즘이 어떻게, 그리고 왜 작동하는지에 대한 직관을 형성하는 것입니다.

저는 WFC를 두 개의 별개 알고리즘으로 나누어 각각 설명하겠습니다. 각각은 그 자체로 흥미로우며, 둘 사이의 인터페이스는 단순합니다.

fn wfc_core(
adjacency_rules: AdjacencyRules,
frequency_rules: FrequencyHints,
...

이것은 지정된 규칙에 따라 그리드 (Grid)에 타일을 배치하는 문제를 해결하는 알고리즘의 저수준 (Low-level) 부분입니다. 여기서는 핵심 (Core) 부분에 대해 "블랙박스 (Black box)" 방식으로 설명하고, 내부적으로 어떻게 작동하는지는 아래에서 설명하겠습니다.

"핵심 (Core)"는 각 방위 (Cardinal direction)에서 어떤 타일이 다른 타일 옆에 나타날 수 있는지를 설명하는 인접 규칙 (Adjacency rules) 세트를 전달받습니다. 규칙의 예로는 "타일 6은 타일 4를 포함하는 셀의 위쪽 (ABOVE) 셀에 나타날 수 있다"와 "타일 7은 타일 3을 포함하는 셀의 왼쪽 (LEFT) 셀에 나타날 수 있다" 등이 있습니다.

또한 각 타일을 다른 타일 대비 출력물에 얼마나 자주 나타나야 하는지를 나타내는 숫자로 매핑한 빈도 힌트 (Frequency hints) 세트를 전달받습니다. 만약 타일 4가 6에 매핑되고 타일 5가 2에 매핑된다면, 타일 4는 타일 5보다 3배 더 자주 나타나야 합니다.

코어(Core)는 실제로 타일 그 자체를 보지 않습니다. 대신, 타일은 0부터 타일 개수에서 1을 뺀 범위 내의 정수로 참조되며, 이를 **타일 인덱스 (tile indices)**라고 부르겠습니다. **인접 규칙 (adjacency rules)**과 **빈도 힌트 (frequency hints)**는 모두 이 **타일 인덱스 (tile index)**를 기준으로 지정됩니다.

알고리즘은 **인접 규칙 (adjacency rules)**을 완벽하게 준수하고, **빈도 힌트 (frequency hints)**를 확률적으로 준수하는 방식으로 그리드에 **타일 인덱스 (tile indices)**를 채워 넣습니다. 인접한 모든 타일 쌍은 **인접 규칙 (adjacency rules)**에 의해 명시적으로 허용될 것이며, 출력물에서 타일의 상대적 빈도는 대개 **빈도 힌트 (frequency hints)**에 명시된 것과 거의 비슷할 것입니다.

이것이 코어 알고리즘과 입력 및 출력 이미지 사이를 이어주는 "접착제 (glue)" 역할을 합니다. 일반적으로 WFC는 입력 이미지와 "유사한" 출력 이미지를 생성하는 데 사용됩니다. 출력 이미지가 입력 이미지와 반드시 동일한 크기(dimensions)일 필요는 없습니다.

구체적으로, 유사하다는 것은 특정 **타일 크기 (tile size)**에 대해 다음과 같음을 의미합니다:

• 출력 이미지의 모든 타일 크기 (tile-sized) 픽셀 사각형이 입력 이미지의 어딘가에 나타남
• 출력 이미지 내 타일 크기 (tile-sized) 픽셀 사각형의 상대적 빈도가 입력 이미지와 대략적으로 동일함

다시 말해, 출력 이미지는 입력 이미지와 동일한 국소적 특징 (local features)을 갖지만, 전역적 구조 (global structure)는 다를 수 있습니다.

유사한 이미지를 생성하는 것 외에도, 사용자가 지정한 **인접 규칙 (adjacency rules)**과 **빈도 힌트 (frequency hints)**에 따라 수작업으로 제작된 타일을 배치하는 것과 같은 WFC의 대안적인 응용 사례들이 있음에 유의하십시오. 이러한 응용 사례들도 동일한 코어 알고리즘을 사용하지만, **이미지 프로세서 (image processor)**는 달라질 것입니다.

fn wfc_pre_process_image(
input_image: Image,
tile_size: u32, /* 종종 2 또는 3 */
...

이 단계의 목표는 코어 알고리즘의 입력값으로 전달될 **인접 규칙 (adjacency rules)**과 **빈도 힌트 (frequency hints)**를 생성하는 것입니다.

먼저, 서로 다른 타일(tile)들이 무엇인지 알아야 합니다.
**입력 이미지 (input image)**와 **타일 크기 (tile size)**가 주어지면, 입력 이미지로부터 타일 크기의 모든 픽셀 사각형을 열거합니다. 이때, 왼쪽 상단 픽셀이 오른쪽 또는 아래쪽 가장자리로부터 타일 크기 이내에 위치하는 사각형들도 포함하며, 이러한 경우에는 입력 이미지의 반대편으로 되돌아오는(wrapping around) 방식을 사용합니다.

다음 4x4 픽셀 입력 이미지를 고려해 보십시오:

타일 크기가 3일 때, 픽셀의 첫 번째 행을 따라 왼쪽 상단 모서리를 기준으로 생성된 처음 3개의 타일은 다음과 같습니다:

3번째 타일에서는 이미지의 가장자리 밖을 샘플링했습니다. 이와 같은 경우에는 이미지의 반대편으로 되돌아갑니다(wrap around). 사실상 이미지가 모든 방향으로 무한히 반복된다고 가정하는 것입니다.

이런 방식으로 계속하여 모든 타일을 열거합니다. 이 예시에서는 16개가 있으며, 모두 고유합니다.

각 타일에 **타일 인덱스 (tile index)**를 할당합니다. 예시에서는 0부터 15까지의 숫자를 인덱스로 사용합니다. **빈도 힌트 (frequency hints)**와 **인접 규칙 (adjacency rules)**은 타일 자체가 아닌 타일 인덱스를 기준으로 제공됩니다.

다음 몇 개의 섹션에서는 핵심 알고리즘이 입력과 유사한 이미지를 생성할 수 있도록 빈도 힌트와 인접 규칙을 구성하는 방법을 설명합니다.

다음은 WFC를 사용하여 생성된, 예시 이미지와 유사한 이미지입니다:

입력 이미지로부터 타일을 생성할 때, 반드시 입력 이미지에 존재하는 것은 아니더라도 입력 이미지에 있는 타일의 회전(rotation) 또는 반사(reflection) 형태인 타일들을 포함하고 싶을 수도 있습니다.

각 타일의 모든 회전 및 반사 형태가 타일 세트(tile set)에 포함되므로, 이를 입증하기 위해 새로운 예시 이미지가 필요합니다. 다음 입력 이미지를 사용해 보겠습니다:

타일 크기가 3일 때, 추출할 첫 번째 왼쪽 상단 타일은 다음과 같습니다:

이 타일의 모든 회전 및 반사 형태:

이미지에서 추출된 모든 타일에 대해 이 과정을 반복합니다.

이 타일들을 출력에 포함하려면, 이들을 고유한 **타일 인덱스 (tile indices)**를 가진 완전한 타일로서 타일 세트에 추가하고, 나머지 알고리즘을 정상적으로 진행하면 됩니다.

회전이나 반사가 포함되지 않은, 입력값과 유사한 이미지:

모든 회전과 반사가 포함된 출력 결과:

이 페이지 상단의 배너는 모든 회전과 반사를 포함한 다음 이미지로부터 생성되었습니다:

축소된 버전:

지면(ground)이 사라진 것이 보이시나요? 입력 이미지가 래핑(wrapped)되어 있기 때문에, 지면이 끝나거나 방향이 바뀌는 타일이 존재하지 않습니다. 이는 출력물에 지면이 존재한다면, 반드시 출력물의 한쪽 끝에서 반대쪽 끝까지 하나의 연속된 선을 형성해야 함을 의미합니다. 이는 상당히 제한적인 제약 조건이므로, 대부분의 출력물에는 지면이 전혀 나타나지 않습니다. 이미지의 구조상 **인접 규칙 (adjacency rules)**을 위반하지 않고는 타일을 배치할 방법이 없다면, 출력물이 **빈도 힌트 (frequency hints)**에서 벗어날 수도 있습니다.

출력물에 지면이 포함될 아주 작은 가능성도 있습니다:

입력 이미지가 래핑되어 있기 때문에 화면 하단에는 나타나지 않습니다.

회전과 반사를 포함하여 생성되었기 때문에, 지면이 수직으로 나타나는 것을 막을 요소는 없습니다.

입력 이미지에서 각 타일의 출현 횟수를 계산하며, 타일의 인덱스에서 그 횟수로의 매핑이 **빈도 힌트 (frequency hints)**를 구성합니다.

첫 번째 예시 이미지를 수정해 보겠습니다:

이 **입력 이미지 (input image)**에 있는 고유한 3x3 타일 세트는 첫 번째 예시와 동일하겠지만, 첫 번째 예시에서는 각 타일이 정확히 한 번씩 나타났던 것과 달리, 여기서는 일부 패턴이 여러 번 나타납니다.

다음 타일들은 이 이미지에서 5번씩 나타납니다:

나머지 타일들은 여전히 한 번씩만 나타납니다.

위 4개 타일의 상대적 빈도는 5가 되며, 다른 타일들에 대한 힌트는 1이 됩니다. 이는 위 4개의 타일이 다른 타일들보다 특정 위치에 나타날 확률이 5배 더 높다는 것을 의미합니다.

이것이 출력물을 어떻게 변화시킬 것이라고 생각하시나요?

수직선이 나타날 확률을 높인다는 것은 수직선이 더 많이 나타날 가능성이 높다는 것을 의미합니다. 이는 이미지 속의 그리드 셀 (grid cells)이 일반적으로 너비보다 높이가 더 긴 형태로 나타나는 결과로 이어집니다.

코어 (core)는 출력 이미지의 단일 픽셀에 각각 대응하는 타일 인덱스 (tile indices) 그리드를 생성합니다.
이 그리드의 셀에 지정된 특정 **타일 인덱스 (tile index)**에 대해, 해당 셀에 대응하는 출력 픽셀은 그 **타일 인덱스 (tile index)**에 해당하는 타일의 색상을 부여받게 됩니다.
이때 타일의 왼쪽 상단 픽셀의 색상만이 사용됩니다.
이 섹션에서는 다음 사항을 유념하십시오:
배치되는 모든 타일에 대해, 타일의 단일 픽셀(왼쪽 상단 픽셀)만이 실제로 출력 이미지에 추가됩니다.
코어가 그리드 셀에 픽셀 인덱스를 할당함에 따라, 코어가 타일의 왼쪽 상단 모서리를 출력 이미지의 픽셀에 할당한다고 말할 수 있습니다.

**이미지 프로세서 (image processor)**의 목표는 입력 이미지에 존재하는 모든 **타일 크기 (tile-sized)**의 픽셀 사각형이 출력 이미지에도 나타나도록 하는 것임을 기억하십시오.
이 목표를 달성하기 위해서는, 코어가 타일의 왼쪽 상단 픽셀을 출력 이미지의 픽셀에 할당할 때마다 타일의 나머지 픽셀들도 결과적으로 올바른 위치에 놓이도록 보장해야 합니다. 이는 예시를 통해 가장 잘 설명할 수 있습니다. 다음은 배너를 확대한 섹션입니다:

빨간색 테두리가 있는 3x3 픽셀 사각형을 가정해 봅시다.
이 사각형은 입력 이미지(오른쪽 하단 꽃 아래에 위치하며 시계 반대 방향으로 90도 회전된 상태)에 존재합니다.
이 사각형에 타일 인덱스 (tile index) 7이 할당되었다고 가정해 보겠습니다.
코어 알고리즘은 빨간색 사각형의 왼쪽 상단 픽셀에 대응하는 그리드 셀이 타일 인덱스 (tile index) 7을 포함해야 한다고 결정했습니다.
타일 인덱스 (tile index) 7이 3x3 타일 전체를 참조하더라도 (이 사실은 오직 **이미지 프로세서 (image processor)**만이 알고 있습니다), 이 셀에 타일 인덱스 (tile index) 7을 선택한 결과로 출력 이미지에는 해당 타일의 왼쪽 상단 픽셀만이 채워지게 됩니다.

하지만 왠지 모르게 빨간 사각형의 나머지 부분도 타일 인덱스 (tile index) 7인 타일처럼 보이게 되었습니다. 왜 그럴까요? **타일 인덱스 (tile index)**가 셀에 할당될 때마다, 우리는 타일의 왼쪽 상단 픽셀뿐만 아니라 타일 전체의 픽셀이 타일 배치 위치를 기준으로 출력 이미지의 올바른 픽셀 위치에 채워지도록 보장할 방법이 필요합니다. 각 타일 배치는 단지 타일의 왼쪽 상단 픽셀만을 기여하기 때문에, 새로운 타일이 이미 배치된 타일의 왼쪽 상단 픽셀로부터 타일 크기 (tile size) 픽셀 이내에 배치될 때마다, 새로 배치된 타일의 픽셀이 이미 배치된 타일의 픽셀과 충돌하지 않도록 보장해야 합니다.

이를 시각화하는 데 도움이 되는 편리한 가설은, 코어(core)가 셀에 타일을 배치할 때마다 해당 셀을 왼쪽 상단으로 하는 타일 크기 (tile-sized) 정사각형 영역 내의 각 픽셀을 타일의 해당 픽셀과 일치하도록 색칠하되, 오직 왼쪽 상단 셀만 "채워짐(populated)" 상태로 표시한다고 상상하는 것입니다. 채워지지 않은(하지만 색칠되었을 수도 있는) 셀에는 타일을 배치할 수 있습니다. 단, 새 타일에 의해 채워지는 정사각형 내의 모든 셀이 아직 색칠되지 않았거나, 새 타일의 해당 픽셀과 동일한 색상을 포함하고 있는 경우에만 가능합니다.

코어가 두 타일의 겹치는 픽셀이 충돌하는 위치에 절대 타일을 배치하지 못하도록 **인접 규칙 (adjacency rules)**을 생성해 봅시다.
**인접 규칙 (adjacency rule)**은 다음과 같은 형태임을 상기하십시오: "타일 인덱스 (tile index) A는 타일 인덱스 (tile index) B를 포함하는 셀로부터 **방향 (DIRECTION)**에 있는 셀 1 공간에 나타날 수 있다".
규칙은 **방향 (DIRECTION)**에서 B에 인접하여 A를 배치하는 것이 충돌을 일으키지 않을 경우에만 이를 허용해야 합니다.
충돌하지 않는 모든 인접 관계는 허용되어야 합니다.

let mut adjacency_rules = AdjacencyRules::new();
for a in all_tiles {
for b in all_tiles {
...

compatible(a: Tile, b: Tile, direction: Direction) -> bool 함수는 b가 direction 방향으로 1픽셀 오프셋되어 있을 때, a와 b가 겹치는 부분의 두 타일 픽셀이 동일할 경우에만 true를 반환합니다.

아래 예시에서는 compatible(A, B, RIGHT) == true입니다.

.

이 예시에서 타일은 3x3 크기이지만, 이러한 **인접 규칙 (adjacency rules)**은 인접한 타일들이 서로 호환됨만을 보장합니다. 2픽셀 떨어져 있는 타일 쌍이 서로 겹치는 것이 가능할 수도 있습니다. 무엇이 이들이 충돌하는 것을 방지할까요?

다음 예시를 살펴보십시오:

**빨간색 (red)**과 파란색 (blue) 사각형은 2픽셀 떨어져 있는 타일 배치들을 둘러싸고 있습니다. 이들은 인접해 있지 않으므로, **인접 규칙 (adjacency rules)**은 교차 영역에서 빨간색 타일의 픽셀과 파란색 타일의 픽셀이 서로 달라지는 것을 명시적으로 금지하지 않습니다.

하지만 빨간색 및 파란색 사각형 모두와 인접한 검은색 (black) 사각형이 존재한다는 것은, 빨간색과 파란색 타일 배치가 서로 충돌하지 않음을 의미합니다.