概要

• 本記事は手続き型マップ生成の技術的詳細を解説
• **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による地形生成とノイズやシェーダ表現を組み合わせることで、手続き型で美しい中世風の島マップを効率的に生成する手法を実現しています。