概要

• 本記事は 手続き型マップ生成 の技術的詳細を解説
• Wave Function Collapse (WFC) アルゴリズムの応用事例
• マルチグリッド構成や バックトラッキング による解決策
• 装飾や水表現 などWFC以外の技法も紹介
• Three.jsや WebGPU/TSLシェーダ の実装例

手続き型マップ生成へのこだわり

• すべてのマップが 異なる形状、かつ シード値に基づく決定論的生成
• AD&Dの ランダムダンジョン表 に影響を受けた体験
• Three.js WebGPU とTSLシェーダによる実装
• 約 4,100ヘックスセル を 19グリッド に分割し、約20秒で生成
• Carcassonneのような タイル配置 をコンピュータが自動で実施

Wave Function Collapse (WFC) アルゴリズムの概要

• Maxim Gumin 考案のWFCアルゴリズムを採用
• Carcassonneのように エッジ同士が一致 するタイルを配置
• ヘックスタイルは1枚につき 6辺 （通常の50%増し制約）
• 30種類のタイル、6回転、5段階の標高で 1セルあたり900状態

タイル定義とエッジマッチング

• 各タイルは 6辺の地形タイプ と重みを定義
• 例：3方向道路タイル { name: 'ROAD_D', ... edges: { NE: 'road', ... }, weight: 2 }
• ルールは 隣接辺が一致すること

WFCの進行手順

• 初期状態 ：全セルが全状態の重ね合わせ（純粋な可能性）
• 最も制約の厳しいセル を選び、ランダムに1状態へ コラプス
• 隣接セルへ 制約伝播、不一致の状態を除外
• 全セル解決まで繰り返し、失敗時はバックトラック

マルチグリッド問題とその解決

• 大規模グリッド ではデッドエンド発生率が急増
• 19個のヘックスグリッド に分割し、各グリッド独立解決
• 境界セルは 隣接グリッドの配置 を制約として固定
• バックトラッキング で最大500回まで巻き戻し可能

リカバリーシステム

• Layer 1: Unfixing 隣接セルの矛盾時、固定を解除し再解決
• Layer 2: Local-WFC 問題領域周辺だけを再WFC（半径2セル、最大19セル）
• Layer 3: Drop and hide 最終手段で問題セルを山タイルで隠蔽

三次元（標高）への拡張

• 5段階の標高 ：海・草原がレベル0、斜面や崖で上下移動
• 標高不一致で 道路や川が崖で途切れる 問題が発生
• 2次元制約から 3次元制約問題 へ拡張

自然なデバッグカラー

• 標高ごとに色分け し、TSLシェーダでパレット間をブレンド
• 低地は夏色、高地は冬色

ヘックス座標の難しさ

• 6方向 のため、単純なx,y座標では隣接計算が困難
• キューブ座標系(q, r, s=-q-r) を採用し、隣接セル計算を単純化
• WFC自体は エッジの一致 のみを気にするため、座標系は描画や配置にのみ使用

森や建物の配置はWFCに不向き

• WFCは 局所的なパターン 生成には強いが、 大域的な分布 には不向き
• Perlinノイズ で森や建物の密度を決定し、自然なクラスタリングを実現
• 建物は道路端や海岸、丘の上などに ロジック配置

水表現の工夫

• 海は アニメーション付きカースティック と 海岸波 を重ねて表現
• カースティック は小さなテクスチャ＋ノイズで低負荷化
• 海岸波 はマスク画像を使い、波の幅を地形に応じて調整
• 入り江問題 はCPUで「囲まれ度」を計算し、波を細くするマスクで解決

Blenderによるタイル作成

• KayKitの Medieval Hexagonパック をベースに、不足コネクタをBlenderで自作
• すべてのタイルは 2ワールド単位幅、エッジのUVも厳密に調整

ビジュアル強化とレンダリング

• Three.js + WebGPU/TSL でレンダリング
• TSLシェーダ でカスタム表現を実装
• ポストプロセスで GTAO などの効果を追加し、雰囲気あるビジュアルを実現

---

このように、 WFCによる地形生成 と ノイズやシェーダ表現 を組み合わせることで、手続き型で美しい中世風の島マップを効率的に生成する手法を実現しています。