1

2 点間の最短経路に関する情報を提供するアルゴリズムが必要です。すべてのウェイポイント、すべてのターンには時間と時間がかかるため、パスのエッジはできるだけ少なくする必要があります。私の場合はコストがかかります。

パスは、特定の形状 (ほとんどが円形または長方形) の障害物を迂回するように計算する必要があります。

パスが格納されている情報は、パスのウェイポイントのデカルト座標または極座標のいずれかである必要があります (これは、私のユニットが実行するコマンドであり、角度アルファに回転し、距離 b を移動するなど)。ただし、各ウェイポイントのデカルト座標を好みます。

ナビゲーション ネットなどはなく、座標系と、障害物やその他の立ち入り禁止エリアの場所に関する情報だけがあり、そこから固定されているものもあれば、移動する可能性がある (そして移動する可能性が高い) ものもあります。

ああ、これはすべて .NET で何らかの方法で利用できるはずです。

ありがとう

//編集: 少しわかりやすくするために、ここに私がやろうとしていることの写真があります: https://dl.dropbox.com/u/8802336/path.png

4

2 に答える 2

2

あなたの質問は 2 つの方法で解釈できます。

1. エッジの数が最も少ないパスを選択して同点を解消し、最短パスを見つけたい

これを行うには、グラフのすべてのエッジの重みに非常に小さな数 ε を追加します。数は を満たす必要がありε < 1/numberOfEdgesます。これにより、すべてのパスの長さがエッジ * ε だけ増加します。つまり、短いパスが優先されます。これは、負の重みのエッジでも機能します。浮動小数点の不正確さに注意してください。

2. ターン数が最も少ないパスを見つけ、パスが最も短いパスを選択してタイを破りたい

これを行うには、グラフのすべてのエッジの重みに大きな数 E を追加します。数は を満たす必要がありE > sumOfAllEdgeWeightsます。これにより、エッジの数が可能な限り少ないパスのみが考慮されるようになります。これは、負の重みのエッジでは機能しません。整数オーバーフローに注意してください。

于 2013-03-13T23:57:42.113 に答える
0

目標が次の場合:

1) エッジの数を最小限に抑えます。

2) 距離を最小限に抑えます。

その順序で、次のように試すことができる1つのこと：

1) 最初から最後まで線を引きます。

2) ラインが衝突するすべてのオブジェクトを計算します。

3) これらのオブジェクトごとに、パスを 2 つのパス セグメントに分割できるオブジェクトに垂直な両方の点を計算します。長方形の場合、ラインを 2 つのセグメントに分割し、セグメント A では通過できる 4 つのコーナーのどれを確認し、セグメント B では通過できる 4 つのコーナーのどれを確認し、見つかるまですべての組み合わせを試すことで、これを行うことができます。最小変位を与える 2 つ。円の場合、その方法を忘れてしまいましたが、2 つのパス セグメントが円に面している両側に 1 つのソリューションしかないため、三角法または何かを使用してそれを行うことができます (私はそれを試してみます :) )

両方の新しいパスに対して、再帰的な分岐方式で 4) を呼び出します。

4) 生成した両方の線分について、衝突がなくなるまで計算を繰り返します。A* と同様に、最初に最適と思われるパスを計算する必要があります (残りの衝突が最も少ないか、それが難しすぎる場合は最初に最も浅いパスを実行します)。

5) 任意のメトリクスで最適なパスを選択します。A* のやり方では、メトリクスを介して最適なパスが一番上になるようにリストをソートしておく必要があります。そのため、最初のパスを選択して終了することができます。

これが常に機能することを頭の中で証明することはできませんが、以前に似たようなものを見たことがあります。

編集

円の周りの一方向で 2 つの線分の最も近いパスを計算するには、線分ごとに次のようにします。

-サイド A: 行頭 (または行末) xs,ys から円の中心 xc,yc まで、長さ = a

-サイド B: 中心 xc,yc から円周上のどこかに行くので、長さ = r

-サイド C: サイド B のエンドポイントから xs,ys (斜辺) に移動します。

A と B によって形成される角度は直角であり、A と B の長さはわかっているので、C の長さは sqrt(A^2+B^2) として計算できます。

最後に、C の長さ = A の長さ/sin(角度(B から C)) = B の長さ/sin(角度(A から C)) がわかります。つまり、三角法を実行して、A から C への角度と角度 B を見つけることができます。 Cに。

これにより、パス セグメントの片側を完全に構築できます。反対側についても繰り返します。パスが 2 つに分割され、両方のセグメントが円に対して同じ高さになります -> 追加される距離が最小化されます。

于 2013-03-13T23:53:39.080 に答える