라떼군 이야기
4,100개의 타일이 20초 만에 뚝딱: WFC 알고리즘과 WebGPU로 구현한 완벽한 절차적 맵 생성기
TL;DR 파동 함수 붕괴(WFC) 알고리즘을 활용해 4,100개 이상의 헥스 타일로 구성된 3D 지도를 브라우저에서 절차적으로 생성하는 방법을 분석한 글입니다. WFC의 고질적인 교착 상태(Dead-end) 문제를 해결하기 위한 다중 그리드 분할과 로컬 재탐색 기법, 그리고 WebGPU 기반의 렌더링 최적화 노하우를 담고 있습니다.
게임 개발이나 시뮬레이션에서 ‘절차적 생성(Procedural Generation)‘은 무한한 콘텐츠를 제공하는 매력적인 기술입니다. 특히 타일 기반의 맵 생성에 자주 쓰이는 ‘파동 함수 붕괴(WFC)’ 알고리즘은 훌륭한 결과를 내지만, 맵이 커질수록 모순에 빠져 생성을 실패하는 치명적인 단점이 있습니다. 이 글은 단순한 WFC 튜토리얼을 넘어, 헥사곤(육각형) 타일과 3차원 고도라는 복잡한 제약 조건 속에서 알고리즘의 한계를 어떻게 극복했는지 보여주는 훌륭한 포스트모템(Post-mortem)입니다. 브라우저 환경에서 WebGPU를 활용해 데스크탑과 모바일 모두에서 60fps를 달성한 엔지니어링 여정도 매우 흥미롭습니다.
핵심 내용
저자는 30종의 타일과 5단계의 고도를 가진 헥스 맵을 WFC로 생성할 때 발생하는 조합 폭발 문제를 해결하기 위해 전체 맵을 19개의 독립된 그리드로 분할했습니다. 그러나 그리드 경계에서 발생하는 해결 불가능한 모순을 극복하기 위해, 문제가 발생한 좁은 영역(반경 2칸)만 다시 계산하는 ‘Local-WFC’라는 혁신적인 복구 시스템을 도입했습니다. 또한, WFC가 숲이나 마을 같은 거시적인 군집 패턴을 만드는 데는 부적합하다는 것을 깨닫고, 지형은 WFC로, 장식 요소는 펄린 노이즈(Perlin Noise)로 역할을 분리했습니다. 시각적으로는 Three.js의 WebGPU와 TSL을 활용해 커스텀 셰이더를 작성했으며, 물의 파도 효과나 그림자 최적화 등에서 발생하는 다양한 엣지 케이스를 창의적인 꼼수와 수학적 접근으로 해결했습니다.
기술적 인사이트
이 글에서 가장 돋보이는 기술적 통찰은 ‘알고리즘의 실패를 인정하고 우회하는 아키텍처 설계’입니다. WFC가 막혔을 때 무한정 백트래킹을 하는 대신, 국소적인 영역만 재구성하거나 아예 산 타일로 덮어버리는(Drop and hide) 실용적인 타협안은 엔지니어링 측면에서 매우 훌륭한 트레이드오프입니다. 또한, 수천 개의 타일을 개별적으로 그리는 대신 BatchedMesh와 단일 공유 재질(Palette Texture)을 사용하여 드로우 콜(Draw call)을 극단적으로 줄인 렌더링 최적화 기법은 WebGL/WebGPU 환경에서 성능을 쥐어짜내는 정석을 보여줍니다. 복잡한 2D 헥스 좌표계를 큐브 좌표계(q, r, s)로 변환하여 이웃 탐색 비용을 최소화한 점도 수학적 이해도가 돋보이는 대목입니다.
시사점
이 사례는 프론트엔드 및 게임 개발자들에게 브라우저 기반 3D 그래픽의 한계가 WebGPU를 통해 어디까지 확장될 수 있는지 명확히 보여줍니다. 또한, ‘모든 것을 하나의 알고리즘(WFC)으로 해결하려 하지 마라’는 저자의 교훈은 복잡한 시스템을 설계할 때 관심사의 분리(Separation of Concerns)가 얼마나 중요한지 다시금 일깨워 줍니다. 실무에서도 완벽한 단일 알고리즘을 찾기보다, 여러 기법(WFC, 노이즈, 휴리스틱)을 조합하고 적절한 폴백(Fallback) 메커니즘을 두는 것이 훨씬 안정적이고 효율적인 프로덕트를 만드는 길임을 시사합니다.
완벽함을 추구하기보다 ‘실패를 우아하게 수습하는 방법’을 고민하는 것이 때로는 더 나은 엔지니어링 결과물로 이어집니다. 여러분의 현재 프로젝트에서도 특정 기술이나 알고리즘의 한계에 부딪혔을 때, 문제 자체를 살짝 비틀어 해결할 수 있는 ‘산 타일(Mountain tile)’ 같은 돌파구는 무엇일지 고민해 보시기 바랍니다.