問題タブ [a-star]

A* ヒューリスティックと Bresenham アルゴリズムの仕組みについて私が理解していることから、現在の状態と目標の状態のみがヒューリスティック関数に渡されるため、これは不可能な場合があります。しかし、誰かがこの問題に対する賢い解決策を持っているかもしれません。

A* を使用してグリッド上のパスを計画しています。現在の状態と目標または障害物を回避する次のターンの間に空きスペースがある場合に、最適なパスがブレゼンハムの線をたどるヒューリスティックが必要です。

問題を説明するためのいくつかの画像を次に示します。

マンハッタン距離:

ワールド内の動きがグリッド上のチェッカーのように機能する場合、これはまったく問題ありませんが、最終的には A* パスを連続平面上のモーションに変換するので、これは非常にうまく機能します。

ユークリッド距離:

改善されましたが、まだ完全ではありません。端の直線に注目してください。対角線は、私が望んでいるものと同じくらい簡単に対角線のままにすることができました。

私が欲しいもの:

Bresenham のラインは、次のターンまたはゴールに引き寄せられます。

ここで良いリソースを見つけましたhttp://theory.stanford.edu/~amitp/GameProgramming/Heuristics.htmlは、私が探しているものに触れていますが、最初からゴールまでブレゼンハムの線を引くためにしか機能しないようです。私が欲しいのは、ブレゼンハムの線が障害物を迂回して次のターンに引き寄せられることです。

この問題への良いアプローチのアイデアはありますか?

C をよりよく理解し、iOS 用に構築しているアプリのパフォーマンスを向上させるために、C でパス検索を実装することにしました。

コードはこちらから入手できます

コードでは、次の構造を作成して使用します。

• ノード: これはグラフの頂点で、座標と A* に関連するその他のデータがあります。
• NodeGraph: ノードのコレクション
• NodeHeap: オープン リスト (プライオリティ キュー) に使用されるヒープ

NodeGraph は、ノード メモリの管理を担当します。ノードへのアクセスが必要な他のすべてのものは、NodeGraph 内の特定のノードへのポインターを使用します。たとえば、NodeHeap は次のようなノード ポインターの単なるコレクションです。

ゲーム内では、複数のパス検索呼び出しに同じグラフ構造を使用するつもりです。同じ構造を解放して新しいものにメモリを割り当てるのではなく、同じ構造を再利用することでパフォーマンスが向上することを理解しています。

これは、Cでこのようなことをするべき方法ですか? 私が利用していない C コンストラクトはありますか、それとも完全に欠けているものはありますか?

昔遊んだウォークラフト3のカスタムゲームをリメイクしてiPhoneに入れています。基本的に、一定量のブロックから迷路を構築するのに一定の時間があり、クリープが迷路を実行するのに時間がかかるほど、より多くのポイントを獲得できます。

私はこれをすべて cocos2d を使ってエアプレイで行っており、現在は a* 経路探索アルゴリズムを入れています。私はJustin Heyes-Jones の実装を使用しており、現在ノード クラスに取り組んでいます。

ただし、いくつかのことが私を混乱させています。クラスは次のようになります。

GetCost の意味がわかりません。この例の迷路では、X は壁で、_ は歩行可能なエリアです。(3, 1) から (3, 2) に移動するコストは 0 になりますか? そして、(3, 1) から (4, 1) に移動するコストはいくらになるでしょうか? それは不可能なので?

そして、距離の式を使用して、GoalDistanceEstimate を実装するだけでよいと思いますよね。

次のA*検索の例に関して何か明確にしたいと思います。

赤い楕円で強調表示されているセクションは、私が理解していない領域です。（上記）{S,B} f=2+6=8から取得/移動/コピーされ、で使用されているようです。また、から取得/移動/コピーされ、で使用されているようです。Expand SExpand A{S,A,X} f=(1+4)+5=10Expand AExpand B

なぜこれが起こるのか誰かが親切に説明できますか？私はグラフを完全に読むことができ、それを解釈するのに問題はありません-それは、前述のパス/ルートが他の場所で複製された理由がわからないという事実にすぎません。

ありがとうございました。

学校の課題で、ラッシュアワー ゲームのソルバーを作成する必要があります。ラッシュ アワーに慣れていない場合は、次のリンクを確認してください: http://www.puzzles.com/products/rushhour.htm

このソルバーでは、A* 検索アルゴリズムを使用する必要があります。インターネットを少し調べたところ、アルゴリズムがどのように機能するかをよく理解できたと思います..ソルバーでそれを実装する方法が本当にわかりません。 . また、車のグリッドをどのように構築する必要があるか.. 誰かがこれに関するヒント/ヘルプを教えてもらえますか? 完全な解決策ではありません..

ねえ、私はAI学生です。グラフをトラバースするために、A*アルゴリズムの実装である宿題を試してみます。私はc++コードを使用していますが、今のところ作成したのは、Graphクラス+insertedgeおよびvertices関数のみであるコードの下です。しかし今、私はコスト関数を定義する方法について混乱しています（f = h（n）+ g（n））..。

また、コードの参照や、グラフに対してA*がどのように機能するかを説明することも役に立ちます。私がグーグルで見つけたのは、a *を介したパスファインディングに関するものであり、トラバーサルグラフには何もありません。

まず、知らない人のために-Anytime Algorithmは、実行可能な時間を入力として取得するアルゴリズムであり、その時間に可能な最善のソリューションを提供する必要があります。

重み付けされたA*はA*と同じですが、f関数に1つの違いがあります。

（ここで、gはノードまでのパスコストであり、hはゴールに到達するまでのパスの終わりまでのヒューリスティックです）

私のいつでもアルゴリズムは、制限時間に達するまで、1から0.5までの重みを減らしてWeightedA*を実行します。

私の問題は、ほとんどの場合、これが解決策に到達するまでにかなりの時間がかかることです。10秒のようなものが与えられた場合、通常は解決策が見つかりませんが、ビームのような他のアルゴリズムは0.0001秒で解決策を見つけます。

何をすべきかアイデアはありますか？

この質問を新しい質問の基礎として使用するという明らかな伝統に従って、私も可能な限りエレガントに解決しようとしている問題を抱えています。

私はそのように六角形の地図を実装しました：

（ここに画像を挿入したいのですが、新品のため許可されていません...上記のリンクをご覧ください）

しかし、今、これらのタイプの座標を使用して、このタイプのマップにA *を（エレガントに）実装する方法を考えています。私は典型的な正方形のグリッド（デカルトグリッドだと思いますか？）でA *を使用した経験があり、そこでの処理方法はこの座標系と互換性がないようです。

通常、バイトの2D配列を生成します。配列のインデックスはグリッド座標に対応し、そのインデックスの値はそのノードの「重み」を示します。（0は通行不能であり、数値が大きいほど、数値が小さいよりも重くなります）。

例： sbyte[,] pathGrid = new sbyte[5, 5] { {0,0,1,0,0}, {9,5,1,3,0}, {9,5,1,3,0}, {9,5,1,3,0}, {0,0,1,0,0} };

0が通行不能である場合、1は簡単にトラバースでき、数値が大きいほどトラバースに「コスト」がかかります。（フォーマットについて申し訳ありません。私はスタックオーバーフローですnewb：P）この配列は、マップの構成に基づいて生成され、パスファインディングアルゴリズムに入力されます。パスファインディングアルゴリズムは、ノードのリスト（パス）を吐き出します。または、パスが見つからなかった場合はnullを返します。

ただし、このタイプのグリッドを使用すると、負の座標（明らかに配列では機能しない）とグリッドが'と同じルールに従わないため、（少なくとも一見すると）不可能です。典型的な'グリッド。

私のA*メソッドを使用してこれを解決する方法はいくつかあると思いますが、それらはすべてかなりずさんで（グリッド座標の変換と空のノードの使用）、誰かがこれをエレガントに行う方法を考えているのではないかと思いました。

とにかく読んでくれてありがとう:)（ところで私はそれが価値があるもののためにC＃/。netでこれをやっています）

ウィキペディアの記事でこの疑似から A* 検索アルゴリズムを実装しています。

f 値が最も低い openSet のノードを取得するように求められている行に行き詰まっています。openSet はいつ満たされましたか? ものによって？最初の実行で開始する必要がありますか？

また、再構築パスの擬似も理解していません：

その擬似命令はどのように実装する必要がありますか?