31

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

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

距離の計算に関しては、適切な言葉がないため、「鳥の道」であってはなりません。A と B の間に壁 (または他の遮断領域) がある場合、A と B の間のパスは長くなります。

どこから始めればよいかわかりません。コメントは大歓迎です。提案されたソリューションは疑似コードで優先されます。

編集：そうですね。gs のコードを調べた後、もう一度試してみました。Pythonではなく、今回はC++で書きました。それでも、Dijkstras アルゴリズム、フラッドフィル、およびHosam Alys ソリューションを読んだ後でも、重要な違いを見つけることができません。私のコードはまだ動作しますが、あなたが実行しているように見えるほど速くはありません。完全なソースはパスティにあります。唯一の興味深い行 (推測) は、78 ～ 118 行の Dijkstra バリアント自体です。

しかし、ここでの主な問題は速度ではありません。誰かがアルゴリズムの違いを指摘するのに十分親切であれば、私は本当に助けていただければ幸いです.

  • Hosam Alys アルゴリズムでは、すべてのノードではなく境界からスキャンする唯一の違いは?
  • ダイクストラスでは、歩いた距離を追跡して上書きしますが、フラッドフィルではそうではありませんが、それだけですか?
4

9 に答える 9

10

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

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(4nこれは2の順序である必要がありますが、)それでも FW と Dijkstra の両方よりも優れています。

注:すべての頂点が 4 つの境界のみを介して直接接続されているため、この問題には 塗りつぶしの方が適しています。マップの幅優先トラバーサルは、結果を比較的迅速に (わずか でO(n)) 生成できます。各ポイントは、その 4 つの隣接ポイントのそれぞれからのフラッド フィルでチェックされる可能性があると想定しているため、上記の式の係数です。

更新 2:このアルゴリズムに関して受け取ったすべての肯定的なフィードバックに感謝します。@Georgのレビューに感謝します。

PS コメントや訂正は大歓迎です。

于 2009-01-25T12:17:08.053 に答える
9

Floyd-WarshallまたはHosamAlyの単純なアルゴリズムに関する質問をフォローアップします。

両方の方法を使用できるテストプログラムを作成しました。これらはファイルです：

すべてのテストケースで、Floyd-Warshallは大幅に遅くなりました。これは、このアルゴリズムがこれを達成するのに役立つエッジの量が非常に限られているためと考えられます。

毎回、フィールドが4つになり、10フィールドのうち3フィールドが障害になりました。

サイズHosamAlyFloyd-Warshall
（10x10）0m0.002s 0m0.007s     
（20x20）0m0.009s 0m0.307s
（40x40）0m0.166s 0m22.052s
（80x80）0m2.753s-
（160x160）0m48.028s-

Hosam Alyの時間は二次式のように見えるので、そのアルゴリズムを使用することをお勧めします。また、Floyd-Warshallによるメモリ消費量はn 2であり、明らかに必要以上です。Floyd-Warshallが非常に遅い理由がわかれば、コメントを残すか、この投稿を編集してください。

PS：私は長い間CまたはC ++を書いていません、私はあまり多くの間違いをしていなかったと思います。

于 2009-01-25T19:15:34.407 に答える
6

グラフの直径で区切られた終点が必要なようです。かなり良くて計算しやすい近似は、ランダムな点を選び、そこから最も遠い点を見つけて、そこから最も遠い点を見つけることです。これらの最後の2つのポイントは、最大限に分離されている必要があります。

長方形の迷路の場合、これは、2回の塗りつぶしで、開始点と終了点のかなり良いペアが得られることを意味します。

于 2009-01-25T21:13:09.257 に答える
5

Floyd-Warshallアルゴリズムを推奨する元の投稿を削除しました。:(

gsは現実的なベンチマークを実行し、何を推測しますか。FWは、一般的なマップサイズのHosamAlyの「フラッドフィル」アルゴリズムよりも大幅に低速です。したがって、FWはクールなアルゴリズムであり、密グラフのダイクストラよりもはるかに高速ですが、非常にまばらなグラフ（各頂点には4つのエッジしかない）が関係するOPの問題にはもうお勧めできません。

記録のために：

  • ダイクストラのアルゴリズムの効率的な実装には、E個のエッジとV個の頂点を持つグラフのO（Elog V）時間がかかります。
  • Hosam Alyの「フラッドフィル」は幅優先探索であり、O（V）です。これは、ダイクストラのアルゴリズムの特殊なケースと考えることができます。この場合、頂点の距離の推定値を修正することはできません。
  • Floyd-Warshallアルゴリズムは、O（V ^ 3）の時間がかかり、コーディングが非常に簡単で、密グラフ（頂点が通常他の多くの頂点に接続されているグラフ）では依然として最速です。しかし、それは非常にまばらなグラフを含むOPのタスクにとって正しい選択ではありません。
于 2009-01-25T20:17:57.853 に答える
3

Raimund Seidel は、彼の論文の最初のセクションで、行列乗算を使用して重み付けされていない無向グラフ (これはまさにあなたが望むものです) で全ペア距離行列を計算する簡単な方法を示しています。無向グラフ [pdf] .

入力は隣接行列で、出力は全ペア最短経路距離行列です。実行時間は、n 点の O(M(n)*log(n)) です。ここで、M(n) は行列乗算アルゴリズムの実行時間です。

このペーパーでは、必要に応じて、実際のパスを (同じランタイムで) 計算する方法も示しています。

実行時間がエッジの数に依存しないため、ザイデルのアルゴリズムは優れていますが、グラフがまばらであるため、ここでは実際には気にしません。ただし、すべてのペアの距離行列が必要な場合は、(実行時間が n^2 よりわずかに悪いにもかかわらず) これはまだ適切な選択であり、迷路でフラッドフィルよりも実装とデバッグが容易になる可能性があります。

擬似コードは次のとおりです。

Let A be the nxn (0-1) adjacency matrix of an unweighted, undirected graph, G

All-Pairs-Distances(A)
    Z = A * A
    Let B be the nxn matrix s.t. b_ij = 1 iff i != j and (a_ij = 1 or z_ij > 0)
    if b_ij = 1 for all i != j return 2B - A //base case
    T = All-Pairs-Distances(B)
    X = T * A
    Let D be the nxn matrix s.t. d_ij = 2t_ij if x_ij >= t_ij * degree(j), otherwise d_ij = 2t_ij - 1
    return D

最大距離のポイントのペアを取得するには、argmax_ij(d_ij) を返します。

于 2009-01-25T23:36:14.803 に答える
1

問題に対するダイクストラ ソリューションの python モックアップが完成しました。コードが少し長くなったので、別の場所に投稿しました: http://refactormycode.com/codes/717-dijkstra-to-find-two-points-furthest-away-from-each-other

私が設定したサイズでは、1 つのノードのアルゴリズムを実行するのに約 1.5 秒かかります。すべてのノードで実行するには数分かかります。

ただし、動作していないようです。常に左上隅と右下隅が最長のパスとして表示されます。58 タイル。もちろん、障害がない場合はそうです。しかし、ランダムに配置されたものをいくつか追加しても、プログラムはその 1 つを最も長いものとして検出します。より高度な形状がなければテストするのは難しいかもしれません。

しかし、少なくとも私の野心を示すことができるかもしれません。

于 2009-01-25T15:48:17.773 に答える
0

あなたの説明は、迷路のルーティングの問題のように思えます。Lee アルゴリズムを確認してください。VLSI 設計における配置配線の問題に関する書籍が役立つ場合があります。Sherwani の「VLSI 物理設計自動化のアルゴリズム」は優れています。また、Sait と Youssef による VLSI 物理設計自動化が役立つ場合があります (Google バージョンでは安価です... )

于 2009-01-25T12:01:27.570 に答える
0

オブジェクト (ポイント) が頻繁に移動しない場合は、O(n^3) 時間よりもはるかに短い時間でそのような計算を実行できます。

必要なのは、スペースを大きなグリッドに分割し、グリッド間の距離を事前に計算することだけです。次に、最も離れたグリッドを占めるポイント ペアを選択することは、単純なテーブル ルックアップの問題です。平均的なケースでは、オブジェクトの小さなセットのみをペアワイズ チェックする必要があります。

このソリューションは、距離メトリックが連続している場合に機能します。したがって、たとえばマップに (迷路のように) 多くの障壁がある場合、このメソッドは失敗する可能性があります。

于 2009-01-25T14:16:32.420 に答える