ゲームマップ（Python）の有向グラフを構築するための良い戦略は何ですか？

Question

Pythonで手続き的に生成されたゲームワールドを開発しています。世界の構造は、有向グラフとして配置された部屋と出口のMUD / MUSHパラダイムに似ています（部屋はノードであり、出口はエッジです）。 （これは必ずしも非循環グラフではないことに注意してください。ただし、非循環ソリューションを検討します。）

ワールド生成アルゴリズムでは、異なる種類の部屋は各部屋の「タグ」によって区別されます。属性（一連の文字列）。インスタンス化されると、タグ（シングルタグ、タグ交差点、タグ結合、最適な候補）によって部屋を照会および選択できます。

テンプレートオブジェクトとファクトリーメソッドの栄光に満ちたシステムを使用して、特定の種類の部屋を作成します。現在の実装はおそらく選択した戦略に合わせて変更されるため、ここでは詳細は重要ではないと思います。 （たとえば、タグとタグクエリをルームテンプレートシステムに追加することができます。）

例として、これらの種類の部屋を用意します：

side_street, main_street, plaza, bar, hotel, restaurant, shop, office

最後に、質問：これらの部屋をインスタンス化および配置して、特定のルールに対応するグラフを作成するための優れた戦略は何ですか？

一部のルールには以下が含まれます。人口10,000人あたり1つのプラザ。 main_street は plaza に接続します。 side_street は main_street または side_street に接続します。 hotel は main_street または plaza の接続を優先し、それに応じてさらにタグを受け取ります。など。

提案された戦略がデータ駆動型の実装を可能にする場合のボーナスポイント。

Answer 1

最初に、場所の感覚が必要です。さまざまなオブジェクトがある程度の座標空間を占有します。

これらのさまざまなことをどの程度定期的に行うかを決める必要があります。些細なケースでは、それらを単純な長方形（または長方形の立体）として座標空間にドロップして、計画を立てやすくすることができます。

物事が不規則で、密集している場合、人生はやや複雑です。

場所を含むマップを定義します。各場所には座標のスパンがあります。単純な長方形を使用する場合、各場所に（左、上、右、下）タプルを含めることができます。

特定のスペースに誰が住んでいるのか、スペースに何が隣接しているかなどを判別するためのメソッドがマップに必要になります。

その後、すべてをマップにドロップし、競合しない、隣接するなどのいくつかの基本的な健全性チェックに合格できる、固定した一連の場所を使用してこれを単体テストできます。

---

次に、一種の「迷路ジェネレータ」が必要です。単純に接続された迷路は、指定されたスペースに折り畳まれたツリー構造として簡単に生成されます。

迷路/ツリーには「ルート」があります;迷路の中心となるノード。必ずしも空間の物理的な中心とは限りませんが、ルートノードは迷路構造の中央になります。

理想的には、このノードからの1つのブランチには1つの「入口」が含まれます。スペース全体に。

このノードのもう一方のブランチには、1つの「終了」が含まれます。スペース全体から。

誰かが入口から出口までさまよい、多くの「行き止まり」を訪れます。途中の場所。

ルートノード用の一種のスペースを選択します。マップスペースにドロップします。

これには1- n の入り口があり、それぞれがルートノードと1- n の入り口を持つサブツリーです。ツリーをこの構造に自然に適合させるのは、この複数の入り口を持つビジネスです。また、到達できない孤立したセクションが存在しないという点で、適切なツリーは常に適切に接続されています。

ルートノードからファンアウトし、場所を選択し、利用可能なスペースにドロップします。

これを単体テストして、スペースを適切に満たすことを確認します。

---

残りの要件は、迷路ジェネレーターが場所を選択する方法を微調整します。

最も簡単なのは、重みとランダムな選択肢のテーブルを用意することです。乱数を選択し、重みと比較して、どの種類の場所が特定されるかを確認します。

---

スペースの定義は2Dまたは3Dにできます。どちらもかなり合理的です。ボーナスクレジットについては、正方形ではなく六角形でタイル張りの2D空間を実装する方法を検討してください。

この＆quot; geometry＆quot;さまざまなアルゴリズムへの Strategy プラグインにすることができます。正方形の2Dを六角形の2Dに置き換えることができれば、オブジェクト指向デザインはうまくできています。

Answer 2

MUDコネクタに関する議論をチェックしてください-世界のレイアウトと生成に関する素晴らしい議論があります。 「高度なコーディングと設計」のさまざまなタイプの座標/ナビゲーションシステム（または同様の）フォーラム。