언리얼 블루프린트로 WFC 알고리즘 구현

WFC 블루 프린트로 생성한 맵 이미지

1. 개요

---

예전 프로젝트에서 다른 팀원이 개발하던 wfc 알고리즘을 담당해서 맵생성 알고리즘을 개발한 적이 있다. 그때 WFC에 필요한 모델링을 만들거나, WFC를 기획과 연결하기 위해서 WFC 알고리즘의 대략적인 구조를 접해본 적 있다.

그 과정에서 블루프린트로 WFC 알고리즘의 맵생성을 구현하면 비주얼 스크립팅도 익숙해지면서 동시에 꽤 재밌는 경험이 되겠다 싶어서 시작했다.

 

2. WFC 알고리즘

---

우선 실제 구현에 앞서 사용한 알고리즘을 먼저 소개하겠다. 본 프로젝트는 블루프린트의 기능을 숙지하고 리마인하는 측면에서 진행되었으므로 실제 알고리즘을 완벽히 구현한다기보다는 성능에 신경쓰지 않고 핵심적인 컨셉을 유지하는데 주안점을 두었다.

 

(좌: 블루프린트 구현에 사용한 플로우차트; 우: Using Wave Function Collapse algorithm for 2D and 3D level generation( Wauthier Tristan 2022-2023))

 

위 다이어그램과 같이 알고리즘의 시작 단계에 Initialize를 거친 다음 Contradiction, FindMinEntropy, Collapse, Propagation 총 4개 단계를 하나의 이벤트로 묶어서 언리얼의 Set Timer by Event 노드에 바인드하여 Timer 틱을 주기로 알고리즘을 실행시켰다.

 

블루프린트로 구현한 WFC 알고리즘은 생성할 타일들의 블루프린트 어레이와 각 타일들의 인덱스, 가중치(확률), 인접규칙들로 정의된 데이터 테이블 그리고 생성할 맵의 사이즈를 요구한다. 이렇게 받은 타일, 인접규칙, 맵사이즈를 바탕으로 일련의 과정을 거쳐서 맵을 생성한다.

 

1D <-> 3D 인덱스 변환 매크로(오른쪽 multiplay 블루프린트에 0은 잘못 넣음)

 

맵은 WIDTH * HEIGHT * DEPTH으로 구성된 3차원 배열이다.(블루프린트 노드에서 3차원 배열 지원을 안해서 3d to 1d, 1d to 3d로 좌표를 변환해주는 위 이미지와 같은 매크로를 사용했다.) 각 배열은 하나의 Cell로 구성되었는데 Cell은 IsCollapsed와 PossibleTiles

2.1. Initialize

Timer 설정 + Initialize

Initialize

2.2. Contradction

Contradiction

 

Contradiction 단계에서는 붕괴하지 않았는데 가능한 타일이 없는 경우(Possible Tiles가 0인 경우) 맵을 다 채우는데 실패한 것으로 보고 WFC_Fail로 판단하도록 bool 값을 반환한다. Fail이 된 경우 WFC 알고리즘은 새롭게 시작한다.

 

2.3. FindMinEntropy

Using Wave Function Collapse algorithm for 2D and 3D level generation( Wauthier Tristan 2022-2023)

FindMinEntropy

ㄴ

 

2.4. Colllapse

Fitness proportionate selection example - Fitness proportionate selection - Wikipedia

s

 

2.5. Propagation

s

 

3. 블루프린트 구현

---

블루 프린트 전체 아키텍처

ㅇㅇ

VARIABLES of WFC generator

ㅇㅇ

TileRuleDataTable

ㅇㅇ

4. 문제와 해결사항

---

코드 구현을 할 때 전체적인 구조는 이미 구상이 끝나서 블루프린트로 시작한 구현 자체는 빨리 끝났다. 하지만 빠르게 구현한만큼 단위 테스트 후 통합과 같은 디버깅 절차가 전무해서 매우 끔찍한 디버깅 시간을 보냈다.(Sans)

생성하는 WorldLocation이 이상한데 배치됨

4.1. Spawn된 Tile Actor의 WorldPosition이 이상하게 배치됨

블루프린트로 breakpoint를 박아서 step by step으로 찾아서 발견했다. 1차원 배열과 3차원 좌표 축을 계산하기 위해 만든 매크로 식이 잘못된게 원인이였다. 사용하던 매크로 식을 고쳐서 해결했다.

규칙성 없게 생성된다.

4.2. 타입과 매개변수 이름 중복

코드로 작성할 때는 일어나기 어려운 실수인데 입력으로 받은 매개변수명을 IntVector 타입과 동일하게 했다. 그런데 이미 IntVector을 쓰기 전에 컴파일을 해서 다음에 IntVector을 사용할 때 컴파일이 안됐다.

노드를 지웠다 추가했다 여러 번 해봐도 컴파일 자체가 안되네 도저히 고쳐지지 않아서 함수를 지우고 새롭게 만드니 해결되었다.

참고로 해당버그는 컨트롤 z를 많이 눌러서 찾아냈다. ctrl z가 다른 페이지의 블루프린트 노드까지 영향을 끼쳐서 이런 문제가 발생했다. 블루프린트 작성 시에는 컨트롤 z를 매우 주의할 것

4.3. TileRule을 어기고 생성됨

디버깅 과정에서 제일 많은 시간을 차지한 파트였다.

블루프린트 디버거에서 Outpin에서 나오는 값이 실제 값이 아닌게 출력된다

도저히 부분적인 디버깅으로는 발견할 수가 없어서 Initialize부터 시작해서 처음부터 끝까지 스텝을 진행했다

그러던 중 언리얼 블루프린트 디버거에서 블루프린트 노드에서 아웃풋에 출력되는 핀의 값이 -1이 찍히는걸 확인했다. 실제로 그런가 싶어서 직접 로그를 출력시켜서 확인해보니 디버거 자체에서 표시를 잘못한 것이였다. 이것을 해결하기 위해 중요한 흐름에서는 로그로 데이터값을 직접 출력하기 시작했다.

z축은 3이 나오면 안된다.

로그로 발견한 index가 배열 사이즈를 초과하는 버그를 발견했다. 이 문제 역시 TileRule을 어기며 생성되는 버그와 연결된 버그였다.

TileRuleIndex가 -1이 나왔던 이유

아주 허무하게도 이 모든 문제를 발생시킨 버그는 FineMinEntropy 함수 중 Sampling 과정에서 Total Weight의 랜덤 범위에 - (-1)을 한 것이 원인이였다. Random Integer in Range 노드가 [a, b)가 아닌 [a, b] 범위여서 신경 쓰였는데 결국 사달이 난 것이다. 블루프린트 노드 추가 과정은 좀 더 세심하게 처리해야 할 것 같다.(스크립트 코딩보다 낯설어서 이런 실수가 자주남)

5. 개선점

---

6. 비고

---

시연영상

Recording 2026-04-23 170013.mp4

8.26MB