問題タブ [path-finding]

長方形の海があるとしましょう。それはかなり大きいです - 10000x20000。

島もあります。簡単にするために、それらも長方形であると仮定しましょう。私たちは彼らの正確な場所（座標）を知っています。

地図上のどこかに船がある場合、(x1, y1)、どの島も越えずに地図上の別の地点 (x2, y2) への最短経路を見つけるにはどうすればよいでしょうか?

更新:これまでのところ、船または海の制約はありません。いくつか追加することで物事を単純化 (および高速化) できれば、これは大歓迎です。

パスは最高である必要はありません。たとえば、10% オフにすることもできます。完全に受け入れられます。

ウィキペディアの擬似コードからA*を実装しようとしていますが、奇妙な結果が得られています。

実装は、最初は適切なパスのように見えるものを見つけますが、さらに詳しく見ると、常に同じパスが生成されます。

誰かが何か間違ったことを見つけることができますか？コードはPython3.1で記述されており、pygameを使用しています。

疑似コードステートメントをステートメントごとに実装したと思うので、実際には手がかりがありません。

スクリーンショットもあります：http： //andhen.mine.nu/uploads/astar.dib

ありがとう！

私は簡単なゲームをコーディングしていて、現在AIの部分をやっています。NPCは彼が訪問する必要がある彼の「興味のあるポイント」のリストを取得します。各ポイントには、マップ上の座標があります。キャラクターが与えられたすべてのポイントを訪れるための最速のパスを見つける必要があります。

私が理解している限り、このタスクは「強く接続された重み付き無向グラフで最速のトラバースパスを見つける」と説明できます。

それを計算するためのアルゴリズムの名前を取得するか、名前がない場合は、自分でプログラミングする際のいくつかのキーポイントを取得したいと思います。

前もって感謝します。

重み付きグラフGとその最短経路距離の行列デルタが与えられます。したがって、delta（i、j）は、iからjへの最短経路の重みを示します（iとjはグラフの2つの頂点です）。デルタは最初に最短経路の値を含めて与えられます。エッジEの重みが突然WからW'に減少します。O（n ^ 2）のdelta（i、j）を更新する方法は？（n =グラフの頂点の数）問題は、O（n ^ 3）の複雑さが最も高い全ペア最短経路を再度計算しないことです。問題はデルタの更新であるため、すべてのペアの最短パスを再計算する必要はありません。

より明確に：私たちが持っているのはグラフとそのデルタ行列だけです。デルタ行列には、最短経路の値だけが含まれます。次に、グラフの変更に応じてデルタ行列を更新します。エッジの重みが減少します。O（n ^ 2）で更新する方法は？

私は現在、A *パスファインディングアルゴリズムを使用して、無限グリッド上のパスを計算しています（GridworldのUnboundedGridを使用して、AP CSのケーススタディを使用しています）。エンドノードが完全に壁に囲まれているために有効なパスが存在しない場合を除いて、すべてがうまく機能します。予想どおり、アルゴリズムは無限に検索を続け、エンドノードを見つけることはありません。

これに対する可能な解決策は、パスファインディング領域全体の周りに非表示の（ユーザーには表示されないがアルゴリズムには表示される）壁を配置し、開始ノード、終了ノード、およびすべての壁ノードがこれらの範囲内にあることを確認することです。壁、2〜3スペースのパディングなど。何かのようなもの：

...最終的にすべてのノードがクローズドリストに追加され、オープンリストが空になり、その時点で有効なパスが存在しないことがわかります。

これは問題の合理的な解決策のように見えますか？これがうまくいかない可能性がある方法はありますか？別の解決策は、同時にエンドから逆方向にパスファインドすることであることを理解していますが、これは、特にエンドノードがそれほど緊密に囲まれていない場合、潜在的にコストがかかる可能性があるようです。

免責事項: 私は主に C# 開発者であるため、Java のバックグラウンドはほとんどありません。

A* アルゴリズムの Java 実装が必要です。
はい、オンラインで同じバージョンをたくさん見ましたが、どれかを選ぶことができません。

アルゴリズムを高速化する Java のすべての新機能を使用する A* アルゴリズムの実装を探しています (少しでも)。その理由はMMO、パフォーマンスが最優先事項であるなどのパス検索を実装しているためです。

ポインターはありますか (少なくともどこを見るべきか)?

タイルベースのマップと経路探索用の A* アルゴリズムを備えた小さなゲーム エンジンを作成しました。しかし、2 つのオブジェクトが衝突してウェイポイントをブロックすると、問題が発生します。彼らは反対方向から来ているので、もう動くことができず、次のウェイポイントに到達することはありません. 私はいくつかの可能な解決策を考えました

• 可動オブジェクトは他の可動オブジェクトと衝突できません
• ブロックされたタイルにフラグを立てるパスを再計算します
• 次の空きウェイポイントへのパスを計算し、移動可能なオブジェクトを含むすべてのタイルにブロックされたものとしてフラグを立てます

私は本当に最初の可能性をやりたくありません.それはアクションゲームのようなエンジンではないため、少し粗末です. 最後の 2 つの可能性は、マップ上に移動可能なオブジェクトが多数ある場合、非常に遅くなる可能性があります。どうすればいいと思いますか？ちなみに、最初の可能性は「Stronghold」に実装されており、残りの 2 つは新しい戦略ゲームで見つけることができます。

このような点の密なグラフを取り、それを接続された凸多角形のグラフに変えようとしています。接続を維持しながら、ポリゴンはできるだけ大きくシンプルにする必要があります。結果のグラフは経路探索に使用されます。誰かが私を正しい方向に向けることができますか?

私は、ソリティアゲームを可能な限り最高のスコアで解決するプログラムを設計しています。ゲームは次のポイントシステムで採点されます。

デッキからのカードは一度に1枚ずつ裏返され、プレイヤーはデッキを無制限に裏返すことができます（ただし、-20ポイントの控除は引き続き適用されます）。

Windowsソリティアゲーム用のクロンダイク戦略ガイドのようなさまざまな戦略ガイドを見つけましたが、これらのガイドは、テーブルカードが知られていない実際のソリティアゲーム用です。

私は、デッキが配られる前にデッキの知識を持っている、私が「フェイスアップ」ソリティアゲームと呼んでいるものを解決するためのアルゴリズムを作成しようとしています。編集：以下の回答で与えられた論文から、このゲームは「思慮深いソリティア」と呼ばれているようです。

これまでのところ、私の考えは次のとおりです。すべての可能な動きが試されてスコアリングされる、ある種のブルートフォーシング。各列を個別に調べて、可能な限り「最良の」移動を試みる単純なアルゴリズム。そして最後に、パスファインディングに似たある種のアルゴリズムで、各動きがスコアリングされ、最適な「パス」が検出されます。

ブルートフォーシングの問題は、移動を無限に繰り返すことができるため、（文字通り）永遠にかかることです。単純なアルゴリズムでは、2つの列を再配置して、すべてのハートとクラブ（たとえば）を配置して、1つのハートの8つを解放するなどのトリッキーなことはできませんでした。私が見ることができることから、パスファインディングは機能しますが、その種の実装がどのように機能するかについては迷っています。

C# で A* パスファインディングを正常に実装しましたが、非常に遅く、その理由がわかりません。openNodes リストをソートしないようにしましたが、それでも同じです。

マップは 80x80 で、10 ～ 11 個のノードがあります。

ウィキペディアから擬似コードを取得しました

そして、これは私の実装です:

私が使用しているヒューリスティックは次のとおりです。

私は何を間違っていますか？同じコードを見続けるのは丸一日です。