ノード生成およびハニカムマップ生成アルゴリズム

Sep 9, 2025 15 min

前提

  • 六角形グリッド
  • ノードセル：最大6ポート
  • エッジセル：最大2ポート（入口・出口）
  • hex_cond パラメータ
    • seed: 乱数初期化（再現性保証）
    • par: START → UnlockHatch → HATCH の最短距離
      • 推奨: par ≤ volume - 2（volume が小さい場合は調整）
    • volume: マップ規模
    • entropy: 分岐・クラスタの乱れ具合（枝ルート・迷路複雑度）

設計の概要

  1. UnlockHatch の配置は、最短距離だけでなく複数候補セルを抽出し、距離・枝ルート接続数・一般ノード接続率などを加味したスコアリングで最適なセルを選択。
  2. CA（Cellular Automata）は、隣接禁止・生存確率だけでなく、隣接ノード数や利用可能ポート数から動的に生存確率を調整し、孤立リスクが高いセルは自動補正。
  3. パフォーマンス向上のため、BFS/A*の結果はキャッシュし、差分更新を活用。枝ルート生成や孤立ノード補正時は部分探索のみで対応し、全ルート生成においてはseed依存の乱数生成を適用して再現性を保証。

生成手順

1. BSP（骨格生成）

  • マップ全体の連結性・大枠構造を保証するため、矩形領域に分割しノード候補を割り当てる。
  • START/HATCHノードの分布を決定し、乱数seedで再現可能にする。
  • BSPは大局的なノード分布制御を担当。

2. UnlockHatch配置

  • メインルート上に中間ノードを配置し、par制約を満たす。
  • 複数候補セルを列挙し、距離・枝ルート接続数・接続率を加味してスコアリング。
  • parは直線経路でなくてもよく、ジグザグ経路も許容。

3. CA（クラスタ形成・孤立禁止）

  • BSPで生成した領域に初期ノードを散布。
  • CAルール適用（複数ステップ）。
    • 隣接禁止：六角隣接セルを空ける。
    • 生存確率：entropyに応じて調整。
    • 隣接ノード数や残り容量に応じて動的調整。
    • 孤立リスクが高いセルは自動補正。
  • DFSで孤立ノード検出 → 最短ブリッジで強制接続。
  • START / UnlockHatch / HATCHは削除対象外。

4. メインルート生成

  • BFS/A*で START → UnlockHatch → HATCH 経路を算出。
  • par以上の距離を満たすルートを採用。
  • 複数ルート存在時は乱数(seed依存)で選択。
  • ルート上のノードは必ずノードセル。

5. 枝ルート生成（entropy反映）

  • entropyに応じて分岐数・長さを制御。
  • 分岐発生セルは必ずノードセルに昇格。
  • ループは必ずノード経由で閉じる（エッジセルだけで閉じない）。
  • 枝ルート生成前にDFSで「エッジセルだけで閉じるループ」が発生しないか確認し、安全性を担保。

6. エッジセル補完

  • ノード同士を六角距離最短経路で接続。
  • エッジセルは最大2ポートのみ使用可能（入口・出口）。
  • セル重複禁止（重ね置き不可）。
  • 接続経路が既存セルに衝突した場合は迂回探索。
  • Edgeセルは入口・出口方向のみOccupied。

7. 最終チェック

  • DFSで全ノードが単一連結か検証。
  • 孤立ノードがある場合は強制ブリッジで接続。
  • セル重複なし、par保証を確認。
  • 不可の場合はパラメータ調整またはリトライ。

パフォーマンスと再現性

  • 六角距離で探索範囲を限定。
  • 通行不可セルは事前に除外。
  • 差分更新アルゴリズムで部分更新。
  • 経路探索結果をキャッシュ（メモ化）。
  • BFS/A*探索回数・ステップ上限設定。
  • seed依存の乱数生成で再現性と多様性を両立。

備考

  • BSP → CA → メインルート → 枝ルート → エッジ補完 → 最終検証の順で生成。
  • hex_cond(seed, par, volume, entropy)で再現性と多様性を両立。
  • 六角形グリッドの特性を活かした自然な探索経路設計。
  • 分岐・枝ルート・ループはentropyで制御可能。
  • ノードセル：最大6ポート、エッジセル：最大2ポート（入口・出口）。

~Yu Tokunaga