問題タブ [a-star]

少し前にJava2Dパスファインディングについて質問しました...パスファインディング2DJava ゲーム？

開発中のゲームは、テーマホスピタルのアイデアに基づいています。私の質問から選ばれた答え、A *パスファインディング、リンクは素晴らしく、とても役に立ちました。最終的にはこれをゲームに実装するようになりますが、それに関してさらにいくつかの質問/問題があります。

私のゲームでは、マップが変更されます。チュートリアルでは、マップが静的であると想定しています（私は思います）。私はコードを見てきましたが、うまくいく限り、パスファインディングコードでゲームマップを更新するために呼び出すメソッドを作成する必要があります。

次に、GameMapクラスが表示されます。私はすべてのタイルを収容するボードと呼ばれる私自身のクラスを持っています。GameMapのメソッドをBoardクラスに統合できると思います。右？

第三に、私はどの部屋もブロックされていると見なされるという推論に取り組んできました。つまり、部屋が覆っている正方形はすべてブロックされたものとして数えられます。人々が部屋に入る場所を前もって考えていました。その後、さまざまな場所に移動するために、これらの部屋を移動する必要があります。正方形ごとにBlockedブール値を反転するだけだと思っていましたが、2つの理由で機能しませんでした。1、部屋には隣接する壁があり、パスファインディングを台無しにする可能性があります。2、ブロックされた状態が単純に反転された場合、部屋の固体アイテムは、反転されたときに固体ではないと見なされ、壁に触れているときに問題が発生する可能性があります。

考えてみると、実際の正方形全体ではなく、正方形の辺をブロックしたほうがいいと思います。これは可能である必要がありますが、前の質問のチュートリアルを使用して取得しているだけで、これを行うためにA *を変更するか、ルームアイテムの問題の回避策に取り組む必要があるかわかりません。

これらの問題のいずれかについての考えや提案はありますか？今日は簡単なパスファインディングを実装していますが、自分の前で考えています。

私は単純な2Dグリッドベースのシミュレーションゲームを開発中であり、完全に機能するパスファインディングを持っています。

前の質問で見つかった回答を、A*パスファインディングを実装するための基礎として使用しました。（パスファインディング2D Javaゲーム？）。

私が本当に求めていることをあなたに示すために、私が作ったこのビデオスクリーンキャプチャをあなたに示す必要があります。私はちょうどその人がどのように場所に移動して戻ってくるかをテストしていました、そしてこれは結果でした...

http://www.screenjelly.com/watch/Bd7d7pObyFo

方向によってパスの選択が異なり、予期しない結果になります。何か案は？

A* 検索アルゴリズムの実装を作成しました。問題は、私が現在使用しているヒューリスティックが正方形のグリッドでのみ正確に機能することです。私のマップは等角図であるため、ヒューリスティックは実際のマップのレイアウトを考慮していないため、セル間の距離が考慮されていません。

更新:大規模なログ記録と分析の後 (平凡さを理解しようとして多くの時間を費やしていると読んでください)、現在のヒューリスティックが非常にうまく機能するという結論に達しましたが、1 つの小さな例外があります。斜め移動。

これは、アイソメsqrt(2)マップ上で実際には斜めの移動よりも何倍もコストがかかる直線の移動が、斜めの移動として計算されることを意味します。問題は、アイソメ レイアウトで正しい結果が得られるように現在のヒューリスティックを変更するにはどうすればよいかということです。を単純に置き換えたり、その逆を行ったりするだけでは機能しません。diagonalstraight

マリオ AI コンペティションの参加者が何をしているかを見ていましたが、そのうちの何人かは A* (A-Star) Pathing Algorithm を利用して非常に優れたマリオ ボットを作成しました。

( Mario A* ボットの動作のビデオ)

私の質問は、A-Star は Dijkstra と比べてどうですか? それらを見てみると、それらは似ているように見えます。

なぜ誰かが一方を他方よりも使用するのでしょうか? 特にゲームのパスのコンテキストでは?

8 パズルは、9 つ​​の位置を持つ正方形のボードで、8 つの数字のタイルと 1 つの隙間で埋められます。いつでも、ギャップに隣接するタイルをギャップに移動して、新しいギャップ位置を作成できます。つまり、ギャップは隣接する (水平方向および垂直方向に) タイルと交換できます。ゲームの目的は、タイルの任意の構成から始めて、ボードの周囲を走るか、左上に 1 を付けて左から右に並べるか、昇順で配置された番号のタイルを取得するようにそれらを移動することです。・手の位置。

この問題を解決するにはどのようなアプローチが効率的でしょうか?

パズル ゲーム Flood-It をプレイするのが好きです。このゲームは次の URL でオンラインでプレイできます。

https://www.lemoda.net/javascript/flood-it/game.html

iGoogle ガジェットとしても利用できます。目的は、連続するフラッド フィルの数を最小限に抑えてボード全体を埋めることです。

このパズルを最適に解決できるプログラムを作成しようとしています。この問題にアプローチする最善の方法は何ですか? 理想的にはA*アルゴリズムを使用したいのですが、残りのステップ数を推定する関数がどうあるべきかわかりません。塗りつぶされた領域を最大化するために深さ 4 のブルート フォース検索を実行するプログラムを作成しました。それはかなりうまく機能し、パズルを解くことで私を打ち負かしましたが、私はそのアルゴリズムに完全に満足していません.

助言がありますか？前もって感謝します。

ツリー構造で幅優先検索と A* を使用する方法は理解していますが、次のグラフが与えられた場合、どのように実装されますか? 言い換えれば、検索はどのようにグラフを横断するのでしょうか? S は開始状態です

グラフはこちら

頻繁に呼び出されるかなり大きな A* パスファインディング関数があり、別のスレッドに配置する必要があります。そうしないと、ゲームが途切れてしまうからです。私は Java のバックグラウンドを持っており、最近、HashMap (本質的には NSDictionary と同等) の速度と、使用できるさまざまな実装についての議論を読みました。私は NSDictionary がどれだけ速いか、また多くの即時および一時的なオブジェクトの割り当てを処理するための実行可能なオプションであると誰かが知っているかどうか、またはそれには遅すぎるかどうかに興味があります。

現在、私は A* アルゴリズムのオープン リストとクローズ リストに NSMutableArray を使用しています。O(1) setObject:forKey と removeObject:forKey により、クローズ リストを NSMutableDictionary に置き換え、「公開リストをミラーリングします。パス データは大きな NSMutableArray に格納されます。インデックス アクセスは (もちろん) 十分に高速であるため、これをそのままにしておきます。

だから私の質問は...これは顕著な速度の改善ですか、それとも独自のリストやマップを展開する必要がありますか? NSDictionary が何をするかわからないので、知りたいです。

マルチスレッドの A* 検索を行う良い方法はありますか? （たとえば）Artificial Intelligence: A Modern Approach に示されているように、シングル スレッドはかなり簡単ですが、優れたマルチスレッド バージョンに出会ったことがありません。

Java、C#、または Lisp のような、スレッド プールと作業ブロック、そしてもちろんガベージ コレクションを備えた健全な言語を想定します。

ウィキペディアは、A *の複雑さについて次のように述べています（リンクはこちら）。

時間計算量よりも問題なのは、A*のメモリ使用量です。最悪の場合、指数関数的な数のノードも記憶する必要があります。

これが正しいとは思えません。理由は次のとおりです。

後続のB、C、およびDとともにノードAを探索するとします。次に、B、C、およびDを開いているノードのリストに追加します。それぞれにAへの参照が付いており、Aを開いているノードから閉じているノードに移動します。ノード。

ある時点で、Aを経由するパスよりも優れたBへの別のパス（たとえば、Q経由）を見つけた場合、必要なのは、BのAへの参照を変更してQをポイントし、実際のコストg（そして論理的にf）。

したがって、ノードにその名前、参照ノード名、およびそのg、h、fスコアを格納すると、格納されるノードの最大数はグラフ内の実際のノード数になりますね。アルゴリズムが最適な（最短）パスの長さに対して指数関数的な量のノードをメモリに格納する必要がある理由を、私は本当に理解できません。

誰か説明してもらえますか？

編集あなたの答えを読んでいると理解しているので、私は問題の間違った観点から推論していました。私は与えられたグラフを当然のことと思っていましたが、指数関数的な複雑さは、「分岐係数」によってのみ定義される概念的なグラフを指します。