절차적 생성을 위한 한걸음 : 파동 함수 붕괴 알고리즘(Wave Function Collapse Algorithm)
안녕하세요. 게임 게발을 좋아하는 개발자 내잔입니다. 오늘은 월드맵을 생성하는 과정에서 겪은 고통스러운 순간과 이 순간을 통해 얻은 배움을 공유하려고 합니다. 그리고 이 글에서는 모든 문제를 해결하는지에 대해서 다루지 않고 문제를 해결하면서 겪은 점에 대해 말하고자합니다.
최근 진행하고 있는 개인 프로젝트에서 월드맵을 제작하면서 어떻게하면 게임에 몰입감을 줄 수있는지에 대해 많은 고민을 했습니다. 제 프로젝트는 오픈월드(오픈월드이긴하지만 무한생성이 존재하지 않는 스트리밍 기술을 사용하는 엄청 큰 맵)를 목표로 두고 개발을 진행했기에 이를 위해 해결해야할 과제들이 몇가지 존재했습니다. 제가 직면한 과제는 다음과 같습니다.
1. 월드맵 전체를 디자인할 방법
2. 월드 곳곳에 배치할 건물들
3. 건물 내부 인테리어 구조(여기서 다루지 않음)
1번은 언리얼의 5.2부터 등장한 Procedular Content Generator(PCG) 를 이용하면 경이로울 정도로 아름다운 월드가 만들어지기 때문에 큰 문제점이 아니였습니다.
제 프로젝트는 FPS게임임과 동시에 건물 내부에서 CQB(Close-quarters combat) 상황이 자주 만들어지므로 건물들의 디테일과 내부 인테리어가 중요하게 다가왔습니다.
여기서 고민을 하게 됩니다. 어떻게하면 모든 건물들을 일정하지 않고 자연스럽게 만들어 줄 수 있을까?
언리얼의 PCG는 배경을 디자인하는데 있어서는 최고의 툴이지만 건물과 같이 균일하면서도 복잡한 구조를 디자인하는데 있어서는 약간의 아쉬움이 존재합니다.
PCG로 만든 건물은 너무 균일하고 규칙적이기 때문에 PCG가 아닌 다른 해결방법이 필요했습니다. 여기서 찾게 된 것이 파동 함수 붕괴 알고리즘을 이용한 절차적 생성이였습니다.
2번을 해결하기 위한 첫번째 시도가 시작됩니다.
파동 함수 붕괴 알고리즘의 늪
절차적 생성에서의 파동 함수 붕괴 알고리즘이란 건물을 제작할 때 필요한 모든 재료를 각각의 파동이라고 하고 이 재료중 필요한 재료를 선택하여 넓어진 파동을 하나씩 줄여나가면서 적절한 재료를 선택하여 건물을 완성하는 알고리즘입니다.
건물이 완성되게 되면 파동이 모두 사라지게 되고 모든 파동이 붕괴됩니다.
건물을 지을때 지붕 위에 지붕이 또 존재하는 이상한 모양이 되면 안되는 것처럼 하나의 파동이 다른 파동에게 이제 지붕이 있는 위치 위에는 또 다른 지붕이 배치될 수 없어! 라고 알려주는 것이 파동 함수 알고리즘의 핵심 원리입니다.
간단한 예제를 들어봅시다. 여러분들은 스도쿠라는 게임을 아시나요?
스도쿠는 1~9의 숫자를 이용해 각각의 가로, 세로, 3X3칸에 중복되지 않는 1부터 9까지의 숫자를 모두 채워넣는 게임입니다.
일반적으로 스도쿠를 풀때 빈 공간은 1~9의 숫자가 모두 들어갈 수 있는 상태를 띄게 됩니다. 그리고 중복되지 않는 숫자를 하나하나 선택하며 문제를 해결해나가죠.
이러한 원리는 마치 파동 함수 붕괴 알고리즘과 굉장히 유사합니다.
건물의 재료를 숫자에 빗대어 보면 숫자가 곧 건물을 제작할때 필요한 모든 재료가 되는 것이고 숫자를 배치하는 것이 건물을 만들어가는 과정인 것입니다.
여기까지 듣고 모두 이해하셨다면 정말 대단합니다. 그럼에도 실제 게임에 적용되는 건 또 다른 의미를 가집니다. 이번엔 실제 2D에서 맵을 만든다고 가정해봅시다.
여러분은 타일 기반의 2D맵을 만드려고 하고 각 타일의 속성이 아래와 같이 존재한다고 해봅시다.
(순서대로 풀, 나무, 숲, 모래, 바다)
그리고 타일들은 아래의 규칙를 가집니다.
- 풀은 풀, 나무, 모래와 붙어있을 수 있습니다.
- 나무는 풀, 나무, 숲과 붙어있을 수 있습니다.
- 숲은 나무, 숲과 붙어있을 수 있습니다.
- 모래는 풀, 모래, 바다와 붙어있을 수있습니다.
- 바다는 모래, 바다와 붙어있을 수 있습니다.
이제 3 * 3타일에 임의로 타일을 배치한다고 가정합시다. 맨처음엔 아무곳에도 설치하지 않았으니 각 타일은 모든 요소들이 들어올 수 있습니다.
임의로 한곳에 풀을 배치하게되면 사정이 달라집니다. 이제 풀의 이웃들은 숲, 모래, 바다일 수 없습니다. 그리고 그 이웃의 이웃들도 모래, 바다일 수 없죠.
이렇게 가능한 요소들을 임의적으로 배치하게 되면 랜덤하게 만들어진 하나의 월드가 생성됩니다.
이것이 파동 함수 붕괴 알고리즘을 이용한 지형 생성 과정입니다.
심연으로 깊게 빠져들다
이론은 이제 충분한 것 같습니다. 지금부턴 실제로 구현을 해야하는데, 이게 정말 막막하게 느껴집니다. 3D는 생성할 월드의 크기부터 방향별로 6개의 블록 속성과 블럭 간의 규칙을 저장해줄 곳도 필요합니다. 이때 규칙이란 이 블록이 연결될 수있는 블록의 제한리스트입니다. 그리고 각각 순회에 필요한 이웃들도 있죠!
특히 타일예시와는 다르게 블럭의 경우 각면이 규칙에 맞게 이루어져야지만 서로 붙을 수 있다는 의미이기에 각 블럭의 가지는 모양에 따라 붙을 수 있는지와 없는지가 결정되게 됩니다.
(지붕타일의 위쪽에는 아무런 모양이 없으므로 이어질 면이 존재하지 않으면 어떠한 타일도 지붕 위에 만들어질 수 없습니다.)
(반면 벽은 일자형의 면이 존재하기때문에 맞닿을 수있는 타일이 있다면 벽 옆에 붙어서 생성할 수 있게 됩니다.)
이러한 요소들을 이용하여 순차적으로 구현에 필요한 부분들을 정리해보면 다음과 같습니다.
- 초기화과정 : 월드 크기, 블럭 6면 속성, 각 면의 가지는 규칙들 등 셋팅
- 실행과정 : 임의로 1개의 블럭 선택 후 각 블럭들이 가지는 타일의 선택지가 1개만 남을때까지 파동 붕괴 함수 실행
- 생성과정 : 블럭 정보를 기반으로 월드에 스폰
구현 의사 코드
(모든 코드는 의사코드로 진행됩니다)
0. 변수 선언
// 순서대로 건물의 가로, 세로, 높이입니다.
int width, depth, height;
// 실제로 건물의 한블럭을 담당할 데이터 집합입니다.
3차원 배열<블럭> 블럭들;
// 블럭 규칙은 한 블럭이 가지고있는 면들의 모양정보 집합입니다.
// 한 블럭(하나의 형태)은 각 방향별로 다양한 모양을 가지고 있습니다.
// 이때 위에서 말한 타일예시에서 땅, 숲과 같이 특정 타일의 속성을 string으로 나타내기로 했습니다.
// 그 이유는 블럭은 상당히 복잡하게 이루어져 있기때문에 enum으로 관리하게되면 매번 블럭이 추가될때마다 컴파일을 하는 불편함이 생깁니다.
// 그렇기에 정말 간단한 이니셜을 key값으로 셋팅하여 각 블럭의 모양을 간단하게 표현하기로 했습니다.
map<블럭형태(string), map<방향, 모양>> 블럭규칙;
// 특정 모양이 어느 모양들과 함께 붙을 수 있는지를 담은 맵입니다.
map<모양, array<모양>> 붙을 수 있는 면 정보;1. 초기화
1-1. 블럭규칙, 면 정보 사전 셋팅
1-2. 블럭들 3차원 배열 생성 -> 각 블럭들의 이웃정보 셋팅
3차원 Block들 생성...
for (int32 Z = 0; Z < Dimention.Z; ++Z)
{
for (int32 Y = 0; Y < Dimention.Y; ++Y)
{
for (int32 X = 0; X < Dimention.X; ++X)
{
if (X > 0)
Block.AddNeighbour(뒤, Blocks[Z][Y][X - 1]);
if (X < Dimention.X - 1)
Block.AddNeighbour(앞, Blocks[Z][Y][X + 1]);
}
}
}2. 실행
inside of WaveFunctionCollapse()...
Block BlockToCollapse = Blocks[Index]; -> 가장 쉽게 만들 수있는 블럭 선택, 없다면 랜덤으로 선택
BlockToCollapse->Collapse(); -> 조건에 알맞게 블럭 형태 선택 후 붕괴
stack<블럭> Stack;
Stack.Push(BlockToCollapse);
while(!Stack.Empty())
{
블럭 = Stack.pop();
for(방향)
{
Neighbour->Constrain() -> 이웃이 가지고 있는 선택가능한 블럭형태 중 현재 블럭과 결합가능한 형태만 남기기
if(이웃의 선택가능한 블럭형태가 줄어들었다면)
{
Stack.Push(Neighbour); -> 스택에 추가하여 다음 이웃도 체크
}
}
}3. 블럭 생성
전체 건물을 모두 순회하며 각각의 블럭형태를 기반으로 월드에 스폰
(생성된 이미지 중 하나)
실제로 제작할때엔 부서진 느낌을 주고싶었기 때문에 건물의 외벽이 없는 것 같은 느낌은 정상이었지만 생각보다 자연스러운 느낌은 없었습니다.
벽이 많이 없는 이유는 건물 제작에 사용한 리소스에서 벽 형태를 가진 요소가 많이 없는것이 그 이유입니다.
파동 함수 붕괴 알고리즘을 이용하면 과연 자연스러울까?
파동 함수 알고리즘은 절차적 맵 생성에 있어서 좋은 기술이긴합니다. 하지만 제가 사용하기에 단점은 명확했습니다. 디테일함이 없다.
모든 맵을 생성하는데 있어 각각의 지형의 전체적인 구조나 디테일을 잡지 못했습니다. 예를 들면 여기에 벽이 있으면 바로 옆에는 벽이 있기보다는 약간의 공간이 있으면 어떨까?와 같이 당장의 옆에 무슨 블럭이 오든 상관없다는 듯이 마치 현재 가장 좋은 선택을 하는 그리디 알고리즘을 보는 것 같았습니다.
파동 함수 붕괴 알고리즘을 이용한 방법을 시도하며 약 5일간의 시간이 지처없이 흘렀습니다.
물론 제가 한 방법이 알맞지 않고 성급하게 내린 결론일 수 있습니다. 하지만 명확한 건 파동 함수 알고리즘만으로는 AAA급 건물 구조를 만드는데에는 한계가 있다는 것이 5일 동안의 노고 끝에 내린 결론입니다.
오히려 모든 건물을 미리 구축해두고 Seed에 따라 랜덤으로 돌려주는 방법이 더 자연스러울 수 있습니다.(시간도 절약될 수도 있구요)
물론 건물 생성 알고리즘은 제가 시도한 파동 함수 붕괴 알고리즘만 있는 건 아닙니다. 또 다른 알고리즘으로는 마르코프 알고리즘(https://github.com/mxgmn/markovjunior)도 있습니다. 자세한건 저도 잘 모르지만 확실히 쉽지 않은 녀석인건 분명합니다.
다음을 위한 준비
지난 5일간 알고리즘을 이해하고 활용하여 건물을 직접 만드는 시스템을 구축하는 것은 제가 했던 가장 어리석은 일이였고 그만큼 힘든 일이였습니다. 프로젝트를 진행하며 포기할까를 속으로 3번쯤 생각할 정도로 이해하기 난해한 내용들이였고 실제로 구현하는데 있어서 많은 어려움이 존재했습니다. 그럼에도 개발자라면 뭐랄까 이런걸 직접 만들어보고 테스트해보지 않으면 5일은 커녕 한달동안 고민에 빠져있을거같은 저의 모습을 생각하니 어떻게 해서든 끝내버리겠다는 생각이 저를 한걸음 앞으로 나아가게 했던 것 같습니다.
절차적 건물 생성에 대해 아직도 많은 고민을 하고 있고 그만큼 많은 아쉬움이 남은 시간이였습니다. 프로젝트에 많은 시간을 투자할 수 없다는 것을 알고 있기에 현재 파동 함수 붕괴 알고리즘을 이용한 방법은 여기까지일듯합니다.
비록 완성된 작품을 보여주진 못했지만 제가 겪은 시행착오를 흥미롭게 보는 시간이 되었으면 합니다.
저는 게임을 다채롭고 몰입감있게 만드는 요소를 개발하기 위해서 최선을 다해 나아가고 이 과정에서 제 한계를 한걸음씩 넘어가고자 합니다.
피드백은 언제나 환영입니다! 긴 글 읽어주셔서 감사합니다.
