Wave Function Collapseで手続き型の六角形マップを作る

• Wave Function Collapse（WFC） アルゴリズムを使い、約4,100個の六角形タイルで構成された中世風の島マップを自動生成するプロジェクト
• 各タイルは道路、川、海岸、崖、森、村などの地形情報を含み、Three.js WebGPU と TSLシェーダーで約20秒で生成
• 大規模グリッドで発生する失敗を解決するため、19個の六角形サブグリッドに分割し、バックトラッキングとローカルWFC復旧システムで成功率86%以上を確保
• ビジュアル面では**PBRマテリアル、WebGPUベースのシェーダー、水面反射・波エフェクト、ポストプロセス（ライティング・被写界深度・グレイン）**などを適用して立体感を強化
• BatchedMeshレンダリングと単一マテリアル共有により数千個のタイルを60fpsでレンダリングし、手続き型生成とリアルタイムグラフィックスの融合可能性を示す

---

手続き型マップ生成の概要

• このプロジェクトはAD&Dのダンジョンサイコロ生成方式に着想を得ており、ユーザーが直接設計しなくてもアルゴリズムが自律的に世界を構成する形
• 生成されるマップは道路、川、海岸線、崖、森、村を含む中世の島の姿をしており、約4,100個の六角形セルで構成
• Three.js WebGPU と TSLシェーダーを使って約20秒以内にマップ全体を完成

Wave Function Collapse（WFC）アルゴリズム

• WFC は、隣接するタイルの**辺（edge）**が一致しなければならないという制約に基づいて地形を構成
• 六角形タイルは6本の辺を持つため、正方形より50%多い制約条件を持つ
• 各タイルは6方向の辺タイプと重み（weight）を定義し、たとえば3方向の道路交差点は道路と草地の辺を交互に持つ
• アルゴリズムは
  1. すべてのセルを取りうる全状態で初期化
  2. 最も制約の強いセルを選んで1つの状態に「崩壊」
  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 により各グリッドのタイルと装飾をまとめ、1回のドローコールでレンダリング
• すべてのメッシュは単一マテリアルを共有し、シェーダー状態の切り替えを最小化
• 結果として38個のBatchedMesh、4,100+セル、60fpsレンダリングを達成

主な数値と技術スタック

• 30種類のタイル、19グリッド、約4,100セル、500回のバックトラッキング、5回のLocal-WFC試行、20秒生成、100%成功率（500回テスト）
• Three.js r183、TSLシェーダー、Web Workers、Viteビルド、BatchedMesh、シード付きRNGを使用

体験とソース

• ライブデモ でマップの拡張と全体生成が可能
• GitHubソースコード を公開しており、50以上のパラメータでライティング・色・水面・WFC設定を調整可能

まとめ

• サイコロの代わりにアルゴリズムが世界を作る体験を提供し、毎回異なる地形や道路・川のつながりを探索できる
• 手続き型生成、グラフィックス最適化、シェーダー技術を組み合わせたWebGPUベースのマップ生成実験

[GN⁺]

Hacker Newsの意見

• 記事では backtracking を単純に500ステップに制限したとしているが、実際には制約プログラミングは非常に興味深く複雑な分野である
  Knuthの Algorithm X と dancing links を使えば、記事で言及されている「Layer 2」領域を86%より高い成功率で解ける気がする
  また、さまざまな ヒューリスティクス を適用すれば、単純な brute force よりはるかに高速に探索できる。Sudoku ソルバーを作ったことがある人なら、brute force がどれほど遅くなるかよく分かるはず

  • この種の 制約ベースの組合せ最適化問題 には、すでに専用ソルバーや高水準モデリング言語が数多く存在する
    たとえば MiniZinc は、複数のソルバーバックエンドをサポートする高水準モデリング言語を提供している
    自分でアルゴリズムを書くより、このような産業用ソルバーを使って問題をモデル化し、ソルバーにランダム探索または全探索で解を見つけさせるほうが効率的だ
    そうすればソルバー作成に時間を使うのではなく、問題定義を調整してより面白いマップを作ることに集中 できる

• 私のノートPC（第11世代 Core i5、Iris Xe、Chrome 最新版）では、デモは 5 FPS で動いている。GPU がボトルネックのようだ
  記事ではモバイルで 60 FPS で動くとしていたので、もう少し効率的だと思っていた
  マップは美しいが、WFC の タイル単位の制約 のため不自然な結果が生じる。非局所的な影響（non-local influence）を反映しにくいからだ
  タイルを1つずつ探索するゲームには向いているが、マップ全体の生成には適していない
  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 リンク

  • それは同名の ボードゲーム が元になっている。BoardGameGeek ページ 参照