前回、制約ベースのWave Function Collapse (WFC)アルゴリズムでマップの自動生成を試したが、戦略的なマップは生成できなかった。

今回は、グラフベースの手法を試す。

戦略グラフ

グラフベースの手法は、本拠地、争奪エリアのようなノードと、ノードをつなぐエッジで構成される。事前にゲームとして戦略的になるグラフを構築してから、制約ベースなどの手法で生成を行う。

あらかじめプレイヤーがどこで戦い、どう移動し、何を取り合うかを表現するため、ゲームとして公平で戦略的なマップが生成できる。

バイブコーディング

Pythonでグラフベースでマップ生成を行うスクリプトを生成した。

レトロターン制戦略ゲームのマップを自動生成するツールを作成したい。

マップのフォーマットは、mapsに実際のマップデータがある。

地形の種類には、
plain
mountain
forest
road
beach
river
bridge
sea
があり、建物には、
capital
factory
city
port
airport
がある。
建物には、ownerがあり、占領状態を表す。
capitalは、redとblueで、それぞれ1つずつという制約がある。

ゲームのルールは、design/deep-research-report.mdに記載している。

ゲームのマップは戦略性が重要なため、グラフベースの手法と制約ベースを組み合わせて実現したい。

参考として、生成手法の初期調査レポートは、design/map-generation.mdにある。

まずは、実現可能な実装方針を立ててください。

海の中に川ができたりしたため、いくつか制約を加えたことで、以下のようなマップが生成できるようになった。

改善

未拠点の拠点が少なく、首都が近距離で向かい合っているマップが多かったため、より戦略的なグラフが生成できるように、生成→確認→修正指示を繰り返した。

以下のようなマップが生成できるようになった。

争奪エリアが複数配置されており、ゲームとして遊べるマップになっている。拠点間の導線も確保されている。

まとめ

グラフベース手法を用いて、戦略性を考慮したマップを生成する手法を試した。制約ベースと組み合わせることで不自然な地形を改善し、実用的なマップ生成が可能になった。

空港のあるマップで未占領の空港がなかったり、島のマップの地形が単調だったりと、改良の余地はまだあるが、いったん遊べる形になったので、ゲームに組み込むつもりである。

以下は、Codexで生成したアルゴリズムの解説である。

マップ自動生成アルゴリズム実装詳細

概要

本プロジェクトのマップ生成器は、design/map-generation.md の方針に沿って、以下の4段階で動く。

既存 maps コーパスを分析して、サイズ分布・HQ配置帯・中立施設比率などの事前分布を作る。
生成対象の ARCHETYPE と CAPITAL_LAYOUT に応じて、戦略グラフ (StrategyGraph) を組み立てる。
戦略グラフをヘクスマップ上の骨格地形へ落とし込み、施設・道路・海域・障害地形を配置する。
後処理で制約違反を修復し、戦略ノードが失われないように安定化させ、最後に validator で検証する。

実装の中心は hf_map_gen/generator.py にあり、グローバル戦略性は戦略グラフ層、局所的な整形は builder / repair 層、既存マップ分布への追従は corpus.py が担当する。

主要モジュール

`hf_map_gen/generator.py`

生成アルゴリズム本体。以下を持つ。

生成対象定義
- ARCHETYPES
- CAPITAL_LAYOUTS
戦略グラフのデータ構造
- StrategyNode
- StrategyEdge
- SeaRegionPlan
- HQPositionBand
- ObjectiveTheatre
- StrategyGraph
グリッド編集用の GridBuilder
アーキタイプ別の graph 生成
stacked / side_by_side それぞれの骨格生成
中立施設配置
道路生成
海・川・橋・港・海岸の修復
archipelago 系の専用安定化

`hf_map_gen/corpus.py`

既存 maps を統計化し、生成時の prior を作る。

主に次を集計する。

サイズ頻度
地形比率
HQ の cross-axis / rear-depth 帯
レイアウト別の中立施設比率
中立施設の帯域分布
中立施設の front cluster profile

`hf_map_gen/validate.py`

完成マップの静的制約を検証する。

主な検証項目は以下。

red / blue の capital がそれぞれ1つずつ存在すること
建物の capturePoints と owner 整合
factory は必ず所有者を持つこと
beach は必ず sea に接すること
river は sea に3辺以上接しないこと
port は十分大きい sea 連結成分に接すること
bridge の左右が許可地形集合に入ること
高海率マップに応じた land component 数上限

`hf_map_gen/metrics.py`

生成結果の戦略的な要約指標を計算する。

収入差
中立都市までの歩兵距離差
空港・港までの距離
capital 間の陸路有無
sea / mountain 数
chokepoint 数

`hf_map_gen/cli.py`

CLI の analyze, generate, validate を提供する。

データモデル

`StrategyNode`

戦略上意味を持つ地点を表す。kind と coord、必要なら side を持つ。

現在使っている代表的な node 種別:

hq
frontier_hub
contested_neutral_cluster
approach_neutral_cluster
strategic_objective
sea_region_anchor
beach_landing_zone
central_island_objective
secondary_island_objective
forward_staging_island
island_chain
naval_neutral_slot
home_island_anchor
home_neutral_cluster
lane_hub
open_field_pocket
cover_belt
soft_barrier
flank_pressure_zone
urban_core
city_belt
industrial_pocket
road_junction
bridge_chokepoint
pass_chain
highland_basin

`StrategyEdge`

ノード間の軍事的関係を表す。経路そのものではなく、経路の意味を持つ。

代表例:

support_relation
contested_front
secondary_route
advance_lane
screen_line
delay_barrier
flank_route
sea_lane

`ObjectiveTheatre`

中立施設や争奪地帯を、単なる座標1点ではなく「戦域」として扱うための構造。

保持する情報:

role
anchor
slot_coords
neutral_budget
land_radius
required_land_tiles
required_slot_count

この構造により、graph が要求する施設数に見合う land capacity を先に地形へ反映できる。

コーパス分析の使い方

生成器は完全ランダムではなく、既存マップから抽出した分布を prior として使う。

サイズ選択

choose_size() は、ユーザーが width / height を指定しない場合、コーパスで頻度が高いサイズから選ぶ。

HQ 位置帯

HQPositionBand は、capital の位置を固定座標ではなく帯域として表す。

stacked
- 横方向のばらつき
- 上下配置時の後方深度
side_by_side
- 縦方向のばらつき
- 左右配置時の後方深度

この帯は corpus.py で既存マップの 10〜90 パーセンタイルから求めている。

中立施設の prior

中立施設に関しては以下を使う。

neutral_ratio_by_layout
neutral_band_weights_by_layout
neutral_axis_weights_by_layout
neutral_front_cluster_profile_by_layout

これにより、単純な均等散布ではなく、既存 maps の front/approach/edge 分布に近い budget 配分ができる。

生成パイプライン詳細

1. エントリポイント

generate_map() が乱数 seed と引数を受け取り、まずサイズを決める。

その後、以下のどちらかへ分岐する。

_generate_stacked_map()
_generate_side_by_side_map()

2. 戦略グラフ生成

_build_strategy_graph() が各アーキタイプに応じた graph を組み立てる。

2.1 共通で決めるもの

naval_weight
naval_profile
port_policy
layout_policy
blue_hq
中立施設 budget
contested cluster order / profile
objective theatre

2.2 `layout_policy`

現在の policy は以下。

strict_symmetric
offset_symmetric
balanced_asymmetric

ただし一部 archetype、特に island_invasion / stacked は専用 policy を使い、正面近距離対峙を避ける。

2.3 `blue_hq` の決定

red_hq を先にサンプルし、blue_hq は layout と policy に応じて決める。

ここで以下のルールを課している。

近距離の軸正面対峙を避ける
stacked / side_by_side ごとに対角寄りの配置も許す
island_invasion / stacked では diagonal separation を強める

2.4 中立施設 budget

_neutral_budget() が、マップ面積と corpus 由来の neutral ratio から次を決める。

contested_neutral_budget
approach_neutral_budgets
neutral_factory_budget

注意点として、既存 maps に未占領 factory は存在しないため、現在は中立 factory を生成しない。

3. archetype ごとの graph

`central_plains`

陸戦主体。以下の node を重視する。

frontier_hub
contested_neutral_cluster
approach_neutral_cluster
lane_hub
open_field_pocket
cover_belt
soft_barrier
flank_pressure_zone

意図は、平地一色ではなく、突破路・遮蔽帯・緩い遅滞地形を graph として先に置くこと。

`mountain_divide`

中央山脈や分断地形を持つ陸戦型。主戦線を峠・谷で制御する。

`river_bridge_chokepoints`

川線と橋前線を主役にする。橋を局所 chokepoint として graph に持ち、骨格では river / bridge を先に固定する。

`dense_city_war`

都市帯と道路網を主役にする。urban_core, city_belt, industrial_pocket, road_junction を graph に持つ。

`highland_passes`

高地塊と複数の pass を作る。pass_chain と highland_basin が主役。

`strait_invasion`

海峡型海戦 map。単一固定ではなく variant を持つ。

naval_assault
coastal_pressure
blocked_strait

variant ごとに port_policy と naval_weight が異なる。

`coastal_logistics`

海はあるが主戦場は沿岸補給線。port は存在しても、海軍主戦場に寄せすぎない。

`island_invasion`

最も専用処理が多い archetype。

graph 上で以下を持つ。

sea_region_anchor
beach_landing_zone
forward_staging_island
island_chain
central_island_objective
secondary_island_objective
naval_neutral_slot
home_island_anchor
home_neutral_cluster

ここでは、capital のある home island と、中央 objective island、側面 objective island を別の戦域として扱う。

4. objective theatre と coverage

strategic_objective は中央1点ではなく、複数の sector を使うように設計されている。

4.1 `_default_objective_theatres()`

land map 向けの標準 theatre を作る。

4.2 `_build_island_objective_theatres()`

island_invasion 専用。landing, central, flank, counter_flank に budget と必要 land capacity を与える。

4.3 `_augment_objectives_with_coverage()`

graph が map の一部しか使っていない場合、coverage candidate から追加 objective を補う。

この層により、特定 archetype だけではなく、全体として map の使用領域が広がるようにしている。

5. 骨格地形生成

戦略グラフを作った後、layout ごとの骨格 builder が地形に落とす。

stacked

_generate_stacked_map() が担当する。

大まかな順序:

戦略グラフ生成
archetype 別 builder で初期骨格生成
mirror / finalize
中央地形や archetype 装飾を適用
blue 側 home cluster の再配置
neutral / road / bridge / river / port 修復
archipelago 系後処理

side_by_side

_generate_side_by_side_map() が担当する。

stacked と同じ責務だが、中央 strait や coast の向きが異なるため、side 専用 builder と修復を使う。

6. 地形 painter の役割

graph を tile へ落とすとき、いくつかの汎用 painter を使う。

_paint_terrain_disc()
_paint_terrain_strip()
_paint_island_region()
_draw_road_path()
_carve_center_strait()
_carve_center_vertical_river()
_carve_center_mountain_divide()

重要なのは、単なるノイズ埋めではなく、graph node / edge に対応する corridor や region を直接描いている点である。

7. neutral 配置

中立施設は後付けランダムではなく、graph budget から配置される。

通常 map

_place_neutral_facilities() が以下の順で置く。

objective theatre に紐づく neutral
contested cluster の neutral
approach cluster の neutral
まだ足りなければ contested cluster を再走査

`island_invasion`

archipelago_assault では、通常の contested / approach に加えて、objective theatre と home island 用の neutral を持つ。

_place_objective_neutral_facilities()
_place_archipelago_home_neutrals()

これにより、中央 island だけでなく home island にも neutral city を持たせられる。

8. road 生成

_paint_roads() は capital 間を安易に直結しないように設計されている。

基本方針:

HQ -> approach -> frontier -> contested lane を局所的につなぐ
敵 HQ 側の幹線と無条件には合流させない
archetype によっては専用 road painter を使う

例:

dense_city_war は都市帯用の道路を追加
highland_passes は峠用道路を追加

9. archipelago 系の後処理

island_invasion は後処理の責務が重い。

9.1 目的

home port を残す
capital 間の land path を断つ
central / flank objective を残す
home island を痩せさせすぎない
neutral theatre を消さない

9.2 主な関数

_enforce_island_invasion_objectives()
_stabilize_island_home_ports()
_stabilize_stacked_naval_ports()
_stabilize_side_naval_ports()
_ensure_archipelago_capital_separation()
_stabilize_archipelago_strategic_fragments()
_materialize_archipelago_home_islands()
_restore_archipelago_home_rear()

9.3 recent fix の考え方

home island については、単なる early paint だと final sea-corridor stabilization に削られる。そこで現在は以下の二層に分けている。

graph が home_island_anchor / home_neutral_cluster を持つ
後段で rear shelf と rear-only restore を使い、port や中央海路を壊さずに home island の基底面積を戻す

この設計により、capital の島を広く保ちつつ、port と capital separation の制約も守れる。

10. repair の役割

repair は「戦略性を決める層」ではなく、「制約違反や局所破綻を除去する層」である。

代表的な処理:

_repair_bridges()
_repair_rivers()
_repair_beaches()
_repair_ports()
_repair_small_land_fragments()

graph が不十分な場合に repair だけで帳尻を合わせると壊れやすいので、最近の実装では objective theatre や home island などの戦略的要件は graph に上げ、repair は safety net にとどめている。

11. validation とメトリクス

cmd_generate() は生成後に必ず以下を行う。

summarize_map() で地形・建物内訳を出力
compute_metrics() で戦略指標を出力
validate_map() で静的制約を検証

これにより、生成アルゴリズムは「map を作る」だけでなく、「ゲーム的に許容されるか」を同時にチェックする。

12. 現在の実装方針の要点

強み

タイル単位ランダム生成ではなく、戦略グラフ先行
コーパス prior を用いた HQ / neutral 分布調整
archetype ごとの専用 graph grammar
objective theatre による複数争奪点の管理
archipelago での home island / objective island の分離
validator による強い制約チェック

意図的な設計判断

中立 factory は生成しない
port は graph が要求した海域でのみ成立させる
bridge は横断前提で左右地形制約を持つ
beach / river / port は既存 maps の観察を基に静的制約を持つ
非対称配置は許すが、戦略グラフが追従する形にする

今後の改善余地

static metrics に加えて簡易 simulation を導入する
archetype ごとの reject / reroll 基準を明示的にする
income gap や objective distance による graph-level reject を強化する
code volume が大きい generator.py を archetype / repair / neutral / naval 単位に分割する

13. 実行フローのまとめ

最後に、generate コマンドの実行フローを簡潔にまとめる。

cli.py がコーパスを分析する。
generate_map() がサイズ、layout、archetype を決める。
_build_strategy_graph() が HQ、frontier、objective、sea region、neutral budget を決める。
layout 別 builder が graph をヘクス地形へ落とす。
neutral, road, port, river, beach, bridge を graph-aware に整える。
validate_map() と compute_metrics() で結果を確認し、JSON を保存する。

この構成により、現行実装は「既存 maps に寄せた prior を持つ graph-based + constraint-aware generator」として整理できる。

戦略グラフ

バイブコーディング

改善

まとめ

マップ自動生成アルゴリズム実装詳細

概要

主要モジュール

hf_map_gen/generator.py

hf_map_gen/corpus.py

hf_map_gen/validate.py

hf_map_gen/metrics.py

hf_map_gen/cli.py

データモデル

StrategyNode

StrategyEdge

ObjectiveTheatre

コーパス分析の使い方

サイズ選択

HQ 位置帯

中立施設の prior

生成パイプライン詳細

1. エントリポイント

2. 戦略グラフ生成

2.1 共通で決めるもの

2.2 layout_policy

2.3 blue_hq の決定

2.4 中立施設 budget

3. archetype ごとの graph

central_plains

mountain_divide

river_bridge_chokepoints

dense_city_war

highland_passes

strait_invasion

coastal_logistics

island_invasion

4. objective theatre と coverage

4.1 _default_objective_theatres()

4.2 _build_island_objective_theatres()

4.3 _augment_objectives_with_coverage()

5. 骨格地形生成

stacked

side_by_side

6. 地形 painter の役割

7. neutral 配置

通常 map

island_invasion

8. road 生成

9. archipelago 系の後処理

9.1 目的

9.2 主な関数

9.3 recent fix の考え方

10. repair の役割

11. validation とメトリクス

12. 現在の実装方針の要点

強み

意図的な設計判断

今後の改善余地

13. 実行フローのまとめ

`hf_map_gen/generator.py`

`hf_map_gen/corpus.py`

`hf_map_gen/validate.py`

`hf_map_gen/metrics.py`

`hf_map_gen/cli.py`

`StrategyNode`

`StrategyEdge`

`ObjectiveTheatre`

2.2 `layout_policy`

2.3 `blue_hq` の決定

`central_plains`

`mountain_divide`

`river_bridge_chokepoints`

`dense_city_war`

`highland_passes`

`strait_invasion`

`coastal_logistics`

`island_invasion`

4.1 `_default_objective_theatres()`

4.2 `_build_island_objective_theatres()`

4.3 `_augment_objectives_with_coverage()`

`island_invasion`