ドワーフフォートレスというゲームをやっています。そして、私にとっての主な課題は、要塞のレイアウトを効率的に設計することです。つまり、移動距離を最小限に抑えるために、各業界の流れは可能な限り密集する必要があります。
例として、食品産業があります
。灰色の各楕円は、1 つの建物を表します。それぞれの白い四角形は、建物の製品を表しています。
私の目標は、それらの建物間の距離がどのように接続されているかという意味で最小になるように、2D グリッド上に建物を配置するアルゴリズムを見つけることです。つまりfishery、 とloomは離れていてもかまいませんがloom、 とfarmer'sはできるだけ近づける必要があります。
現時点では、レイアウトをシミュレートするためにいくつかの既製のソフトウェアを使用することを検討していますが、アルゴリズムに関するいくつかのヒントは問題ありません。
現在、強制指向のアルゴリズムを検討していますが、離散グリッドの要件についてはわかりません。
質問の形式化: 離散座標で機能する Force Draw Graph アルゴリズムはありますか?
更新: AS3 で強制描画アルゴリズムの実装を見つけました (Web には JS バージョンも含まれています)。ディスクリート版に変換してみます。しかし、うまくいくかどうかは疑問です...
UPDATE2: コメントでさらにいくつかの制限が要求されました。各建物は、仮想グリッド上の単一のセルを占有します。建物は隣接するセルに配置できます。建物を重ねたり重ねたりすることはできません。(PS: ゲームでは、各建物には通常 3x3 のサイズが定義されていますが、より多くのアプローチを可能にするために、問題をより一般的なものにしたいと考えています)。