0

問題

簡単な1DRTSゲームを書いて、次のパスファインディングの問題があります。1次元の線がたくさんあり、線の間を移動するだけでなく、現在の線の内部を移動するために使用できるテレポーターがどこにでもあります。テレポーターは、回線間を移動する唯一の方法です。行li1の位置po1からli2のpo2までの最短経路を決定するために使用できるアルゴリズムまたは擬似コードは何ですか？ゼロのコストで相互に接続されたテレポーターTのセット（それぞれにpoとliがあります）があります。

なぜA*またはダイクストラアルゴリズムではないのですか？

これは、1Dではやり過ぎだと思うからです。

明確化

  • 少し二次元に聞こえるかもしれませんが、1行で左または右にしか移動できないためではありません。
  • テレポーターへの移動には費用がかかりますが、ある場所から別の場所へのテレポートには費用がかかりません。このアスキーアートを参照してください：
    ... 0 .... s..0
    ......0.x..。

ここで、最短は開始sからターゲットxまでの方法です。

  • 正しいテレポーターに行く
  • 1行下にテレポートします（この図のみ。実際には飛行機は順序付けられていません）
  • そして目標に向かって右に行きます（最終コスト= 5）
4

3 に答える 3

2

あなたは他のどのテレポーターからでも行くことができますか？その場合、可能な方法は2つだけです。開始位置から右と左です。テレポーターに到達したら、目的地に最も近いテレポーターに移動します。終わり。わかりました。目的地に最も近いテレポーターがわからない場合は、すべて同じ平面で試してみてください。

于 2010-09-01T19:43:24.043 に答える
0

左または右に移動すると、他の1つのテレポートしかヒットできないため、基本的に、すべてのテレポートは、テレポートの両側で、その左右のテレポートに接続されていると見なすことができます。したがって、各テレポートは他の4つのテレポートに接続されます。

これにより、各ノードが最大4つのエッジを持つグラフが作成されます。したがって、そのグラフをメモリ内に作成し、ダイクストラのアルゴリズムを使用して問題を解決します（これは、もはや1次元ではないため、やり過ぎではありません）。これは、@Jakobによって提案されたブルートフォースアルゴリズムよりもはるかに高速になります。

于 2012-06-14T17:18:41.370 に答える
0

始点からの検索と終点からの検索を組み合わせることで、ヤコブの答えを改善できると思います。

最初のステップでは、開始点から開始して、2つの検索パスを検討します。左に行く道と右に行く道

各反復は、パスの1つになるまで、両方のパスでステップを実行します...

  1. ... xを押します（検索、これが最短経路です）
  2. ...テレポーターを叩く

（2）の場合、まだテレポーターに当たっていないパスにマークを付けます。

ここで、終点xから開始し、2つのパスでも検索を開始します。したがって、左右に移動し、反復ごとに1ステップずつ実行します。ここでも、2つの可能な結果があります。

  1. マークされたスポットに到達->最短経路は、開始からマークの方向に進み、テレポーターなしで終了に到達します。
  2. テレポーターにぶつかる->最短経路は、ステップ（2）で開始からテレポーターに移動し、次にステップ（4）でテレポーターから終了xに向かって移動します。

これにより、2nステップで最短パスが検出されます。ここで、nはそのパスの長さです。（あなたは常に2つの方向を見ているので）。

于 2017-03-24T12:56:18.173 に答える