# 웨이브 펑션 콜랩스로 절차적 육각형 지도 만들기 > Clean Markdown view of GeekNews topic #27357. Use the original source for factual precision when an external source URL is present. ## Metadata - GeekNews HTML: [https://news.hada.io/topic?id=27357](https://news.hada.io/topic?id=27357) - GeekNews Markdown: [https://news.hada.io/topic/27357.md](https://news.hada.io/topic/27357.md) - Type: GN+ - Author: [neo](https://news.hada.io/@neo) - Published: 2026-03-10T09:50:30+09:00 - Updated: 2026-03-10T09:50:30+09:00 - Original source: [felixturner.github.io](https://felixturner.github.io/hex-map-wfc/article/) - Points: 3 - Comments: 1 ## Topic Body - **웨이브 펑션 콜랩스(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** 사용 ### 체험 및 소스 - [라이브 데모](https://felixturner.github.io/hex-map-wfc/)에서 지도 확장 및 전체 생성 가능 - [GitHub 소스코드](https://github.com/felixturner/hex-map-wfc) 공개, 50개 이상의 파라미터로 조명·색상·수면·WFC 설정 조정 가능 ### 요약 - 주사위 대신 알고리듬이 세계를 만드는 경험을 제공하며, 매번 다른 지형과 도로·강 연결을 탐험할 수 있음 - 절차적 생성, 그래픽 최적화, 셰이더 기술이 결합된 **WebGPU 기반 지도 생성 실험** ## Comments ### Comment 52735 - Author: neo - Created: 2026-03-10T09:50:30+09:00 - Points: 1 ###### [Hacker News 의견들](https://news.ycombinator.com/item?id=47311815) - 글에서 **backtracking**을 단순히 500단계로 제한했다고 하지만, 실제로 제약 프로그래밍은 매우 흥미롭고 복잡한 분야임 Knuth의 [Algorithm X](https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X)와 **dancing links**를 사용하면, 글에서 언급된 "Layer 2" 영역을 86%보다 높은 성공률로 해결할 수 있을 것 같음 또한 다양한 **휴리스틱**을 적용하면 단순한 brute force보다 훨씬 빠르게 탐색 가능함. Sudoku 솔버를 만들어본 사람이라면 brute force가 얼마나 느려지는지 잘 알 것임 - 이런 종류의 **제약 기반 조합 최적화 문제**에는 이미 전용 솔버나 고수준 모델링 언어가 많이 존재함 예를 들어 [MiniZinc](https://www.minizinc.org/)은 여러 솔버 백엔드를 지원하는 고수준 모델링 언어를 제공함 직접 알고리즘을 짜기보다 이런 산업용 솔버를 활용해 문제를 모델링하고, 솔버가 무작위 혹은 전체 탐색으로 해답을 찾게 하는 편이 효율적임 그러면 솔버 작성에 시간을 쓰기보다, **문제 정의를 조정해 더 흥미로운 맵을 만드는 데 집중**할 수 있음 - 내 노트북(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](https://www.youtube.com/watch?v=Uxeo9c-PX-w&pp=ygUhdG93bnNjYXBlciB3YXZlIGZ1bmN0aW9uIGNvbGxhcHNl0gcJCa4KAYcqIYzv)에서 볼 수 있음 - Jasper Flick의 Unity 튜토리얼 [Hex Terrain](https://catlikecoding.com/unity/tutorials/hex-map/)이 떠오름 이 프로젝트는 미리 만든 타일을 제약 조건으로 맞추는 반면, Jasper의 튜토리얼은 **타일 경계를 동적으로 생성**함 두 접근 모두 흥미롭고 읽는 재미가 있음 - 정말 멋진 프로젝트였음 참고로 작성자가 본다면, 타일의 **superposition 상태**(가능한 옵션 집합)를 bitfield로 표현하는 방법을 고려했는지 궁금함 예전에 WFC를 구현할 때 bitfield로 바꾸자 **속도 향상**이 엄청났음. 백트래킹보다 전체 청크를 다시 계산하는 게 더 빨라졌음 - 나도 비슷한 경험이 있음. 내 WFC 봇은 **Carcassonne 맵**을 생성하는데, [bitset 라이브러리](https://github.com/bits-and-blooms/bitset)를 사용하면서 성능이 크게 개선됨 일정 주기마다 상태를 스택에 저장하고, 막히면 마지막 상태로 되돌아가는 식으로 동작함 변수 이름이 `tenper`인 걸 보면 과거의 나를 약간 원망하게 됨 - 제약을 만족하는 배열을 찾는 게 가장 어려운 부분 같음 혹시 **SAT solver**를 사용하는 대안이 있을까 생각해봄. 다만 그럴 경우 항상 ‘쉬운’ 해만 찾고 무작위성이 떨어질 수 있음 일부 SAT 솔버는 초기 변수값을 무작위로 설정할 수 있지만, 그게 곧 무작위 해답을 의미하진 않음. 혹시 비슷한 시도를 해본 사람이 있는지 궁금함 - SAT 솔버는 계산 복잡도도 높고, **형식 방법(formal methods)** 을 배우지 않은 사람에게는 이해가 어렵다는 문제가 있음 반면 WFC는 단순한 brute force 방식이라 구현이 쉽고, 막다른 길만 많지 않다면 **계산 비용이 낮음** 게임에서는 완벽한 해보다 ‘충분히 괜찮은’ 결과면 되기에 WFC가 더 실용적일 수 있음 - 영감을 주는 프로젝트였음. 참고 자료도 훌륭하고 소스 코드도 공개되어 있음 여기에 [Here Dragons Abound](https://heredragonsabound.blogspot.com/)의 **비주얼 스타일**을 결합하면 멋질 것 같음 - OP가 이미 알고 있을 수도 있지만, [Red Blob Games의 Hexagon 수학 페이지](https://www.redblobgames.com/grids/hexagons/)에는 훌륭한 예제와 코드가 많음 - 글에서도 그 사이트를 링크하고 있음 - **비정사각형(non-square) 그리드**에서의 WFC 탐구가 흥미로움 제약 전파의 복잡도가 기존 예제보다 훨씬 높을 것 같음 이런 복잡한 위상에서는 **Constraint Logic Programming** 같은 다른 제약 솔버가 표현력과 성능 면에서 유리할 수도 있겠다는 생각이 듦 - *Dorfromantik*이 떠오름. [Steam 링크](https://store.steampowered.com/app/1455840/Dorfromantik/) - 그건 같은 이름의 **보드게임**을 기반으로 함. [BoardGameGeek 페이지](https://boardgamegeek.com/boardgame/370591/dorfromantik-the-board-game) 참고