웨이브 펑션 콜랩스로 절차적 육각형 지도 만들기

• 웨이브 펑션 콜랩스(WFC) 알고리듬을 이용해 약 4,100개의 육각형 타일로 구성된 중세풍 섬 지도를 자동 생성하는 프로젝트
• 각 타일은 도로, 강, 해안, 절벽, 숲, 마을 등의 지형 정보를 포함하며, Three.js WebGPU와 TSL 셰이더로 약 20초 만에 생성
• 대규모 격자에서 발생하는 실패를 해결하기 위해 19개의 육각형 서브그리드로 분할하고, 백트래킹과 로컬-WFC 복구 시스템으로 성공률을 86% 이상 확보
• 시각적으로는 PBR 머티리얼, WebGPU 기반 셰이더, 수면 반사·파도 효과, 후처리(조명·피사계 심도·그레인) 등을 적용해 입체감 강화
• BatchedMesh 렌더링과 단일 머티리얼 공유로 수천 개 타일을 60fps로 렌더링하며, 절차적 생성과 실시간 그래픽의 결합 가능성을 보여줌

절차적 지도 생성 개요

• 프로젝트는 AD&D 던전 주사위 생성 방식에서 영감을 받아, 사용자가 직접 설계하지 않아도 알고리듬이 스스로 세계를 구성하는 형태
• 생성된 지도는 도로, 강, 해안선, 절벽, 숲, 마을을 포함한 중세 섬 형태로, 약 4,100개의 육각형 셀로 구성
• Three.js WebGPU와 TSL 셰이더를 사용해 약 20초 내에 전체 지도를 완성

웨이브 펑션 콜랩스(WFC) 알고리듬

• WFC는 인접한 타일의 가장자리(edge) 가 일치해야 한다는 제약을 기반으로 지형을 구성
• 육각형 타일은 6개의 엣지를 가지므로 사각형보다 50% 더 많은 제약 조건을 가짐
• 각 타일은 6방향 엣지 타입과 가중치(weight)를 정의하며, 예를 들어 3방향 도로 교차점은 도로와 잔디 엣지를 번갈아 가짐
• 알고리듬은
  1. 모든 셀을 가능한 모든 상태로 초기화
  2. 가장 제약이 큰 셀을 선택해 하나의 상태로 ‘붕괴’
  3. 인접 셀의 불가능한 상태를 제거하며 전파
  4. 전체 셀이 해결될 때까지 반복 수행

대규모 격자와 모듈형 해결

• 작은 격자에서는 안정적이지만, 4,000셀 이상에서는 실패 확률 급증
• 이를 해결하기 위해 19개의 육각형 서브그리드로 나누고, 각 그리드를 독립적으로 해결하되 경계 타일을 고정 제약으로 유지
• 경계 제약이 충돌할 경우 백트래킹만으로는 해결 불가

백트래킹과 복구 시스템

• 백트래킹은 잘못된 선택을 되돌려 다른 타일을 시도하는 방식으로, 최대 500회까지 수행
• 그러나 그리드 간 충돌은 별도 복구 시스템으로 처리
  • 1단계: Unfixing — 충돌 셀을 다시 가변 상태로 전환해 주변 셀을 새 제약으로 설정
  • 2단계: Local-WFC — 반경 2셀(19셀) 영역을 재해결해 경계 호환성 확보, 최대 5회 시도
  • 3단계: Drop & Hide — 실패 시 해당 셀을 제거하고 산악 타일로 덮어 자연스럽게 처리
• 이 다층 복구로 전체 지도 생성 성공률 약 86% 달성

3차원 고도 처리

• 지도는 5단계 고도 레벨을 가지며, 경사면과 절벽 타일이 상하 레벨을 연결
• 잘못 연결되면 도로가 절벽에 막히거나 강이 위로 흐르는 오류 발생
• 고도 정보는 인스턴스 색상으로 인코딩되어 셰이더가 저지대·고지대 색상 팔레트를 혼합

육각형 좌표계

• 육각형은 6방향 구조로 인해 단순한 2D 좌표계로는 인접 계산이 복잡
• 큐브 좌표계(q, r, s) 를 사용해 인접 탐색을 단순화
• WFC는 실제 기하보다 엣지 매칭 그래프 구조에 집중하므로, 좌표계는 주로 렌더링과 다중 그리드 배치에 사용

나무·건물 배치

• WFC는 국소적 패턴에는 강하지만 대규모 분포에는 부적합
• 나무와 건물은 Perlin 노이즈 필드로 밀도를 결정해 숲·마을의 자연스러운 군집 형성
• 추가 로직으로 도로 끝에는 건물, 해안에는 항구·풍차, 언덕에는 석환(henge) 배치

수면 효과 구현

• 바다는 단순한 평면이 아니라 반짝임과 해안 파도를 포함
• 반짝임(Sparkles) 은 Voronoi 노이즈 대신 작은 스크롤 텍스처 + 노이즈 마스크로 구현해 GPU 부하 감소
• 해안 파도(Coast Waves) 는 해안 마스크를 블러 처리해 거리 기반 사인파 밴드를 생성
• 만(Cove) 문제에서는 블러 기반 거리 계산이 부정확해, CPU가 주변 셀을 검사해 파도 얇게 처리할 영역 마스크를 생성

타일 제작과 정렬

• 기본 모델은 KayKit Medieval Hexagon Pack을 사용하되, 누락된 연결 타일(경사 강, 절벽 변형 등)은 Blender로 직접 제작
• 모든 타일은 폭 2 유닛으로 통일되며, UV 정렬 오차가 생기면 경계선이 드러나므로 정밀한 매핑 필요

시각 효과와 렌더링

• Three.js WebGPU + TSL 셰이더로 구현, GLSL 대신 노드 기반 셰이더 사용
• 후처리 스택
  1. GTAO로 음영 강조
  2. 피사계 심도(Depth of Field) 로 미니어처 효과
  3. 비네팅·필름 그레인으로 아날로그 질감 부여
• 동적 그림자 맵은 카메라 시야에 맞춰 매 프레임 재조정해 확대 시에도 선명한 그림자 유지

성능 최적화

• BatchedMesh로 각 그리드의 타일과 장식을 묶어 한 번의 드로우콜로 렌더링
• 모든 메시는 단일 머티리얼을 공유해 셰이더 상태 전환 최소화
• 결과적으로 38개의 BatchedMesh, 4,100+ 셀, 60fps 렌더링 달성

주요 수치 및 기술 스택

• 30종 타일, 19개 그리드, ~4,100 셀, 500회 백트래킹, 5회 Local-WFC 시도, 20초 생성, 100% 성공률(500회 테스트)
• Three.js r183, TSL 셰이더, Web Workers, Vite 빌드, BatchedMesh, Seeded RNG 사용

체험 및 소스

• 라이브 데모에서 지도 확장 및 전체 생성 가능
• GitHub 소스코드 공개, 50개 이상의 파라미터로 조명·색상·수면·WFC 설정 조정 가능

요약

• 주사위 대신 알고리듬이 세계를 만드는 경험을 제공하며, 매번 다른 지형과 도로·강 연결을 탐험할 수 있음
• 절차적 생성, 그래픽 최적화, 셰이더 기술이 결합된 WebGPU 기반 지도 생성 실험