古典的な水差しの検索問題の場合、3 つ以上の水差しの場合でも、A* 検索アルゴリズムに使用できる許容関数はどれですか?

編集：

http://www.dave-reed.com/csc550.S02/HW/HW4.htmlについては知っていますが、その機能は明らかに一貫していません。

QuickGraph で A-star を使用して、ノード A からノード B への最短パスを、他のすべてのノードへの最短パスを生成せずに生成する方法 (ノード B が調査済みセットにある場合は停止) があるかどうかを尋ねたいと思います。

QuickGraph をゲームにプラグインしたいのですが、環境が課す時間制限から、すべてのパスを生成することはできません。

C＃で私の問題を解決するための他の提案は大歓迎です

事前に感謝します、Xtapodi

または同様の言語のバージョン。2D だけでなく、すべてのタイプのマップに対応するものです。

これは私のノードのグリッドです:

A* パスファインディング アルゴリズムを使用して、その上でオブジェクトを移動しています。通常は問題なく動作しますが、時々間違った動作をします:

• 3 から 1 に移動するときは 2 を経由しますが、1 から 3 に移動するときは 4 を経由します。
• 3 と 5 の間を移動する場合、6 を経由する短い方法ではなく、いずれかの方向に 4 を経由します。

何が間違っている可能性がありますか？これが私のコードです（AS3）：

NodeGridNode::distanceTo()

私は、ロボットがオブジェクトへの道を見つけ、そのオブジェクトに行くときにいくつかの障害を回避しなければならないプロジェクトに取り組んでいます。

問題は、ロボットとロボットが拾う必要のあるオブジェクトの両方が、パスファインダー内で 1 ピクセル幅であることにあります。実際には、それらははるかに大きいです。多くの場合、A* パスファインダーは、障害物の端に沿ってルートを配置することを選択します。これにより、障害物と衝突することがありますが、これは望ましくありません。

障害物に歩行不可能なフィールドを追加しようとしましたが、常にうまくいくとは限りません。それでも障害物と衝突し、歩けない場所にあまりにも多くのポイントを追加すると、実行できるパスがなくなります。

この問題について何をすべきかについて何か提案はありますか?

編集：

そこで、ジャスティン L が提案したように、障害の周りに多くのコストを追加して、次のようにしました 。

ここでは、障害物周辺のコストを確認できます。最初は、中央の 2 つの障害物がコーナーの障害物と同じように見えるはずですが、パスファインダーを実行すると、コストが上書きされているように見えます。

パスを持つグリッド http://sogaard.us/uploades/1_map_grid.png

写真で見つかったものを示す写真 http://sogaard.us/uploades/2_complete_map.png

上の写真は、写真で見つかったものを示しています。

見つかったパス http://sogaard.us/uploades/3_path.png

これは、私たちの問題が以前にもあったように、障害を抱えていることがわかった道です。

http://sogaard.us/uploades/4_mg_path.png 上のパスを含む前のグリッド

そして、パスがオンになっているコスト マップの別の写真。

私が奇妙に思うのは、なぜ A* パスファインダーがこれらの非常に高いフィールド コストを無効にしているのかということです。

開いているリスト内のノードを現在のフィールドで評価して、現在のフィールド パスが開いているリスト内のパスよりも短いかどうかを確認するときでしょうか?

そして、パスファインダーに使用しているコードは次のとおりです。

Pathfinder.cs: http://pastebin.org/343774

Field.cs および Grid.cs: http://pastebin.org/343775

A*を使用して始点と終点の間の最適なルートを計算することができます。現在、ポイントのすべての順列のペアにA *を適用することにより、開始ポイントと終了ポイントの間にウェイポイントを含めています。

例：

ポイント1からポイント4に行きたい。さらに、ポイント2と3を通過したい。

（1、2、3、4）の順列を計算します。

次に、順列ごとに、最初から2番目までのA *ルートを計算し、それを2番目から3番目、次に3番目から4番目までのルートに追加します。

順列ごとにこれを計算したら、ルートを距離で並べ替えて、最短を返します。

明らかに、これは機能しますが、多くの計算が必要であり、6つのウェイポイントがあると完全に崩壊します（8つのアイテムの順列は40320です:-)）

これを行うためのより良い方法はありますか？

この2D配列マップがあるとしましょう

ブロックされたタイルを定義する整数でいっぱいの HashSet があります。プレイヤーが立っている場所からマップの一部をクリックしたときに、適切な経路探索を行うにはどうすればよいでしょうか? A* (ノードなどを使用)? 何を指示してるんですか？

ありがとう。

まず、これはゴーストではなくパックマンの AI です。

アイコンの周りでパックマンを再生する Android ライブ壁紙を作成しています。画面タッチによるユーザーの提案をサポートしていますが、ゲームの大部分は AI によってプレイされます。ゲームのプログラミングはすべて 99% 完了しましたが、パックマン自身の AI はまだ非常に弱いです。パックマンの次の移動方向を判断するための優れた AI の開発について、助けを求めています。

私の最初の計画はこれでした：

1. 各方向のスコア カウンターをゼロの値で初期化します。
2. 現在の位置から開始し、BFS を使用して、可能な最初の 4 つの方向をキューに追加することで外側にトラバースします。

3. 要素をキューからポップし、まだ「見られていない」ことを確認し、それが有効なボード位置であることを確認し、対応する初期方向スコアに現在のセルの値を以下に基づいて追加します。

   1. ドットあり: プラス 10
   2. パワーアップあり：プラス50
   3. 果物がある: プラス果物の値 (レベルによって異なります)
   4. ゴーストがパックマンに向かって移動している: 200 を引く
   5. ゴーストがパックマンから離れていく: 何もしない
   6. ゴーストが垂直に移動している: 50 を引く
   7. セルまでのステップ数に基づくパーセンテージをセルの値に掛けます。最初の方向からのステップが多いほど、セルの値はゼロに近づきます。

   現在のセルから可能な 3 つの方向をキューに入れます。

4. キューが空になったら、4 つの可能な最初の方向のそれぞれについて最高スコアを見つけ、それを選択します。

紙の上ではいいように聞こえましたが、幽霊はパックマンを非常に急速に取り囲み、パックマンは同じ2つまたは3つのセルで前後にぴくぴく動き、1つが到達するまで. ゴーストの存在の値を調整しても役に立ちません。私の最も近いドット BFS は、ゲームが終了する前に、少なくともレベル 2 または 3 に到達できます。

適切な AI を開発するためのコード、考え、および/またはリソースへのリンクを探しています。できれば前者の 2 つです。今週末には市場に出したいので少し急いでいます。どんな助けでも大歓迎です。

参考までに、これは手動でGameDev.StackExchangeにクロスポストされました。

ゴースト AI ではなく、パックマン自身の iPhone 用のパックマン AI を作成しようとしています。私は経路探索に A* を使用しており、壁を避けてゲーム ボード上の 2 つのタイル間の最短経路を計算する非常に単純なアプリを実行しています。

したがって、1 つの関数を実行して 2 点間のパスを計算するのは簡単です。関数が goalNode に到達したら、各タイルの「parentNode」プロパティを介してパスを逆方向にたどり、必要なアニメーションを作成できます。しかし、実際のゲームでは、状態は常に変化しているため、パスとアニメーションも変化する必要があります。私はゲームプログラミングが初めてなので、これを実装する最良の方法がよくわかりません。

バックグラウンドで実行され、goalNode と、ゲームの現在の状態を考慮してそこへの最適なパスを常に計算する NSOperation を作成する必要がありますか? このスレッドは、特定の時点でメイン スレッドに通知し、情報を提供する必要もあります。問題は何ですか？

どの時点でメインスレッドに通知する必要がありますか?

メインスレッドに通知するデータは何ですか?

...または私はすべて一緒に離れていますか?

どんなガイダンスも大歓迎です。

2 つの状態間の最短経路を見つけるためのA* 検索アルゴリズムを実装しました。アルゴリズムは、訪問した状態の既知の最適な距離を格納するためにハッシュ マップを使用します。そして、最短経路の再構築に必要な親子関係を格納するための 1 つのハッシュマップ。

これがコードです。アルゴリズムの実装は一般的です (状態は「ハッシュ可能」および「比較可能」である必要があるだけです) が、この特定のケースでは、状態は int のペア (ベクトル) であり[x y]、特定のハイトマップ内の 1 つのセルを表します (隣接するセルにジャンプするためのコストは依存します)身長差について）。

質問は、パフォーマンスを向上させることが可能かどうか、そしてその方法は? おそらく、1.2 または将来のバージョンのいくつかの機能を使用したり、アルゴリズム実装のロジックを変更したり (たとえば、パスを格納する別の方法を使用する)、またはこの特定のケースで状態表現を変更したりすることでしょうか?

このマップのJava 実装は瞬時に実行され、Clojure 実装には約 40 秒かかります。もちろん、これにはいくつかの自然で明白な理由があります: 動的型付け、永続的なデータ構造、プリミティブ型の不要な (アン) ボックス化...

トランジェントを使用しても大きな違いはありませんでした。