☰

互いに最も遠い2点を見つけるアルゴリズム 質問する

tag-icon • tag-icon algorithm math path distance path-finding
互いに最も遠い2点を見つけるアルゴリズム 質問する

作成中のレーシング ゲームで使用するアルゴリズムを探しています。マップ/レベル/トラックはランダムに生成されるため、マップを最大限に活用できる 2 つの場所 (スタートとゴール) を見つける必要があります。

  • このアルゴリズムは2次元空間内で動作する。
  • 各ポイントから次のポイントに移動できるのは、上、下、左、右の4方向のみです。
  • ポイントはブロックされているかブロックされていないかのどちらかしか選択できず、ブロックされていないポイントのみを通過できる。

距離の計算に関しては、適切な言葉が見つからないため、「鳥の道」にはなりません。A と B の間に壁 (またはその他の遮蔽領域) がある場合は、それらの間の経路は長くなります。

どこから始めればよいかわかりませんが、コメントは大歓迎です。提案された解決策は疑似コードでお願いします。

編集：そうですね。gsのコードもう一度挑戦してみました。Pythonではなく、今回はC++で書きました。しかし、ダイクストラアルゴリズム、埋め立てそしてホサム・アリスの解決策、決定的な違いは見つかりませんでした。私のコードは動作しますが、あなたのコードほど速く動作しません。完全なソースはペースト興味深い行は（私が思うに）78 行目から 118 行目の Dijkstra 変種自体だけです。

しかし、速度はここでの主な問題ではありません。アルゴリズムの違いを指摘していただける方がいらっしゃいましたら、本当に助かります。

  • Hosam Alys アルゴリズムでは、すべてのノードではなく境界からスキャンする点だけが異なりますか?
  • Dijkstras では、歩いた距離を記録して上書きしますが、floodfill ではそうしませんが、それだけでしょうか?

ベストアンサー1

マップが長方形であると仮定すると、すべての境界ポイントをループし、塗りつぶしを開始して開始点から最も遠いポイントを見つけることができます。

bestSolution = { start: (0,0), end: (0,0), distance: 0 };
for each point p on the border
    flood-fill all points in the map to find the most distant point
    if newDistance > bestSolution.distance
        bestSolution = { p, distantP, newDistance }
    end if
end loop

これは に該当すると思いますO(n^2)。私が間違っていなければ、 です。ここで(L+W) * 2 * (L*W) * 4はL長さ、Wは地図の幅、(L+W) * 2は周囲の境界点の数、(L*W)は点の数、4は塗りつぶしが最大 4 回 (すべての方向から) 点にアクセスするという仮定です。 はn点の数に等しいので、これは に相当し、 2(L + W) * 8 * nよりも優れているはずです。 (地図が正方形の場合、次数は1.5になります。)O(n)O(16n)

アップデート：コメントによると、マップは迷路のようなものなので（私が最初に考えていたような単純な障害物があるものではなく）、上記と同じロジックを作成できますが、マップ内のすべてのポイントをチェックします（境界上のポイントのみではありません）。これはO(4n2)の順序になるはずですが、それでも FW と Dijkstra の両方よりも優れています。

注記： 洪水埋め立てこの問題には、すべての頂点が 4 つの境界のみで直接接続されているため、 がより適しています。マップの幅優先走査により、比較的迅速に ( でO(n)) 結果が得られます。各ポイントは、その 4 つの近隣ポイントのそれぞれから塗りつぶしでチェックされる可能性があると想定しているため、上記の式の係数は次のようになります。

アップデート2:このアルゴリズムに関していただいた肯定的なフィードバックに感謝しています。@Georgに特に感謝いたします。彼のレビュー。

PS コメントや訂正があれば歓迎します。

おすすめ記事