▲

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

 (felixturner.github.io)
2P by GN⁺ 16시간전 | ★ favorite | 댓글 1개
  • 웨이브 펑션 콜랩스(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 사용

체험 및 소스

요약

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

  • 글에서 backtracking을 단순히 500단계로 제한했다고 하지만, 실제로 제약 프로그래밍은 매우 흥미롭고 복잡한 분야임
    Knuth의 Algorithm X와 dancing links를 사용하면, 글에서 언급된 "Layer 2" 영역을 86%보다 높은 성공률로 해결할 수 있을 것 같음
    또한 다양한 휴리스틱을 적용하면 단순한 brute force보다 훨씬 빠르게 탐색 가능함. Sudoku 솔버를 만들어본 사람이라면 brute force가 얼마나 느려지는지 잘 알 것임

    • 이런 종류의 제약 기반 조합 최적화 문제에는 이미 전용 솔버나 고수준 모델링 언어가 많이 존재함
      예를 들어 MiniZinc은 여러 솔버 백엔드를 지원하는 고수준 모델링 언어를 제공함
      직접 알고리즘을 짜기보다 이런 산업용 솔버를 활용해 문제를 모델링하고, 솔버가 무작위 혹은 전체 탐색으로 해답을 찾게 하는 편이 효율적임
      그러면 솔버 작성에 시간을 쓰기보다, 문제 정의를 조정해 더 흥미로운 맵을 만드는 데 집중할 수 있음

  • 내 노트북(11세대 Core i5, Iris Xe, Chrome 최신 버전)에서는 데모가 5 FPS로 실행됨. GPU가 병목인 듯함
    글에서는 모바일에서 60 FPS로 돌아간다고 했기에 좀 더 효율적일 줄 알았음
    맵은 아름답지만, WFC의 타일 단위 제약 때문에 비자연스러운 결과가 생김. 비국소적 영향(non-local influence)을 반영하기 어렵기 때문임
    타일을 하나씩 탐험하는 게임에는 괜찮지만, 전체 맵 생성에는 적합하지 않음
    Red Blob Games의 노이즈 기반 접근법이 더 나은 결과를 보여줌. 강은 습도 추적으로, 도로나 다리는 별도 패스로 처리하면 더 빠르고 견고함
    그래도 WFC는 흥미로운 프로그래밍 문제라 구현 자체는 즐거웠을 것임. 전반적으로 훌륭한 글과 인상적인 데모였음

    • 혹시 Windows나 Linux에서 실행 중인지, 아니면 CPU 렌더링을 쓰고 있는지 궁금함
    • 내 모바일에서는 잘 작동함. FPS는 어떻게 측정했는지 궁금함. 사이트에 표시가 없던데, 혹시 Chrome Dev Tools로 본 것인지?

  • Oskar Stålberg가 Wave Function Collapse(WFC) 를 여러 게임에서 사용했음. 대표적으로 Townscaper가 있음
    관련 발표 영상은 SGC21 - Beyond Townscapers에서 볼 수 있음

  • Jasper Flick의 Unity 튜토리얼 Hex Terrain이 떠오름
    이 프로젝트는 미리 만든 타일을 제약 조건으로 맞추는 반면, Jasper의 튜토리얼은 타일 경계를 동적으로 생성함
    두 접근 모두 흥미롭고 읽는 재미가 있음

  • 정말 멋진 프로젝트였음
    참고로 작성자가 본다면, 타일의 superposition 상태(가능한 옵션 집합)를 bitfield로 표현하는 방법을 고려했는지 궁금함
    예전에 WFC를 구현할 때 bitfield로 바꾸자 속도 향상이 엄청났음. 백트래킹보다 전체 청크를 다시 계산하는 게 더 빨라졌음

    • 나도 비슷한 경험이 있음. 내 WFC 봇은 Carcassonne 맵을 생성하는데, bitset 라이브러리를 사용하면서 성능이 크게 개선됨
      일정 주기마다 상태를 스택에 저장하고, 막히면 마지막 상태로 되돌아가는 식으로 동작함
      변수 이름이 tenper인 걸 보면 과거의 나를 약간 원망하게 됨

  • 제약을 만족하는 배열을 찾는 게 가장 어려운 부분 같음
    혹시 SAT solver를 사용하는 대안이 있을까 생각해봄. 다만 그럴 경우 항상 ‘쉬운’ 해만 찾고 무작위성이 떨어질 수 있음
    일부 SAT 솔버는 초기 변수값을 무작위로 설정할 수 있지만, 그게 곧 무작위 해답을 의미하진 않음. 혹시 비슷한 시도를 해본 사람이 있는지 궁금함

    • SAT 솔버는 계산 복잡도도 높고, 형식 방법(formal methods) 을 배우지 않은 사람에게는 이해가 어렵다는 문제가 있음
      반면 WFC는 단순한 brute force 방식이라 구현이 쉽고, 막다른 길만 많지 않다면 계산 비용이 낮음
      게임에서는 완벽한 해보다 ‘충분히 괜찮은’ 결과면 되기에 WFC가 더 실용적일 수 있음

  • 영감을 주는 프로젝트였음. 참고 자료도 훌륭하고 소스 코드도 공개되어 있음
    여기에 Here Dragons Abound의 비주얼 스타일을 결합하면 멋질 것 같음

  • OP가 이미 알고 있을 수도 있지만, Red Blob Games의 Hexagon 수학 페이지에는 훌륭한 예제와 코드가 많음

    • 글에서도 그 사이트를 링크하고 있음

  • 비정사각형(non-square) 그리드에서의 WFC 탐구가 흥미로움
    제약 전파의 복잡도가 기존 예제보다 훨씬 높을 것 같음
    이런 복잡한 위상에서는 Constraint Logic Programming 같은 다른 제약 솔버가 표현력과 성능 면에서 유리할 수도 있겠다는 생각이 듦

  • Dorfromantik이 떠오름. Steam 링크

답변달기