土地が「隣り合っている」状態はどう表現する？

[きょろ]

今、Ｃ＋＋で戦略ゲームを作ろうとしています。イメージとしては、すずぬーとさんの「都道府県対戦」やParadox社の「Hearts of Iron」シリーズです。
そして、まず初めに、土地のシステムをどうしようかと考えました。領土の最小単位一つ一つの事を「プロヴィンス」として話していきたいのですが（都道府県一つ一つのようなものです）、
早速壁にぶち当たりました。プロヴィンス情報をどのように処理するかです。
戦略ゲームでは、とあるプロヴィンスから別のプロヴィンスへ、侵攻、移動、援助などに行きますが、直接行くには隣り合っていないといけません。
そこで、「プロヴィンスＡとプロヴィンスＢは隣り合っている」という状態を取得する必要があると思うのですが、その方法に全く見当がつかないんです。
オセロの様な盤であれば、「縦と横は隣り合っている、斜めは隣り合わない」と明言できますが、土地というのは、隣り合うプロヴィンスが一個だったり、５個や６個とつながっていたり、様々です。
なので、そういった単純なアルゴリズムでは難しいと思い、色々と考えたのですが、これといったものがありません。
ネットでも出来る限り探してみたのですが、地形をランダム生成など、あまり関係のない記事ばかりで中々参考になるサイトが見つけられませんでした。
プロヴィンス一つ一つについて、隣り合うプロヴィンスを書いていってもいいのですが、もし後になって、「大きな川があって渡れない」「プロヴィンスを一つ増やそう」と思ったときに、直すのがとても面倒だと思うんです。

質問としては、「どのようにして隣り合う状態を表現するか」という事になるのですが、どなたかご教授よろしくお願いいたします。

[hide]

各点（ノードとよく表現されますね）それぞれに、つながる先の参照の配列を持つ感じですかね。
星型だったら
星を５つの地点で表現するとしたら、てっぺんから時計回りにp1, p2, p3, p4, p5と名前をつけるとして、
p1 がつながる先は [p3, p4]
p2 がつながる先は [p4, p5]
p3 がつながる先は [p5, p1]
p4 がつながる先は [p1, p2]
といった感じで。

[きょろ]

誤って捉えていたらすみません。
ひょっとして、図形の書き方の事を仰っていますか？

[hide]

いえ、図形の書き方に限定しているわけではなく、データの持ち方の話ですよ。

[hide]

星型、というのがお気に召さなかったのであれば、都道府県でも良いです。

北海道は　[青森] へのつながりを持つ
青森は [岩手, 秋田, 北海道] へのつながりを持つ
秋田は [青森,岩手, 山形] へのつながりを持つ
岩手は [青森, 秋田, 宮城] へのつながりを持つ
...

みたいなデータを持っておけば、
岩手は [青森, 秋田, 宮城] に移動することができる。
のような形で表現できますよね

[白い変人]

こういうアルゴリズムの問題は個人的に好きですね。

私の見解を言うならば、基本的には、
>プロヴィンス一つ一つについて、隣り合うプロヴィンスを書いていってもいいのですが
この考え方を基本とするべきだとは思います。

プロヴィンス一つ一つに隣接するプロヴィンスのIDに相当するものを格納する配列等を用意しておけば良いでしょう。
追加削除したければ、寧ろ、その配列の情報を追加削除するだけで対応出来るという意味では楽と言えるでしょう。
また、この方法だと、地理的には不可能な場所とリンクさせる事も可能になるので、例えば、クリアした後の裏モードなんかも視野に入れているのなら、寧ろこの方法の方が良いのかもしれません。

ただ、それすらも億劫だというのなら、マップ全体が2次元のユークリッド空間で表現されている場合には、その処理を自動化するアルゴリズムも構築可能でしょう。

但し、そのアルゴリズムを使用して厳密に正解に導く為には、プロヴィンスを図形とみなした場合の角数×プロヴィンス数をNとした場合、O(N^4)程度の高い時間計算量を要する事になるかもしれません。

このアルゴリズムのヒントとなるキーワードを記すなら「凸包」。


もう一つアルゴリズムとして、上記2次元のユークリッド空間上の要素に、どの座標がどのプロヴィンスかという情報も含まれているのなら、縦方向と横方向で異なるプロヴィンスになる箇所を探す様に走査すれば、マップの面積程度の時間計算量で算出可能でしょう。


前者のアルゴリズムはマップが広い場合向け。
後者のアルゴリズムはマップが狭い場合向け。

個人的には、マップが広くても縮尺されたマップ上で後者のアルゴリズムを使った方が、アルゴリズムをシンプルに出来て良いかなと。

前者はアルゴリズムを教えても混乱するプログラマが続出しそうだし、時間計算量だけじゃなくて、空間計算量も食うし。

[usao]

内容的に他の方の説明の繰り返しにしかならない感じですが，

データ構造については「グラフ」で調べると良いかと思います．
（「データ構造　グラフ」などで検索すればいいかな？）

隣接関係のデータ生成の自動化が必要な場合は画像処理的なアプローチが簡単かもしれません．
隣り合う県が絵的にも隣接することが前提ですが
各県を個別の色で塗り分けた地図の絵でも作れば，隣接画素間の色関係から簡単に求まるでしょう．

[きょろ]

hideさん
白い変人さん

返信が遅くなり申し訳ありません。

なるほど、逆に変に自動化しようとすると更に面倒になるんですね。
途中に川を作っても、リンク情報は変えずに、「川があったら進めない」という条件分岐を作ればなんとかなりそうです。

一度それで作ってみようと思います！
ありがとうございました。