問題タブ [a-star]

A* パスファインディング アルゴリズムのシンプルで最適化された実装のコードをすべての言語で投稿してもらうことはできますか?

これは主に楽しみのためであり、stackoverflow 自体ができることを試すためのものです...ただし、実際にはこれの ActionScript 3 バージョンを取得することに興味があります。

しかし、この「質問」は、さまざまなプログラミング言語が作成されたとしても、将来にわたって永遠に更新され続けるという考えです!

疑似コードが多くの (ましてやすべての) 異なる言語に "翻訳" されているオンラインの場所を私は知りません。これは価値のあるリソースのように思えます。必ずしもこのサイトが設計された目的ではありませんが、試してみて、stackoverflow を使用できる価値があるかどうかを確認することに害はありません!

AI の本の 1 つで、よく知られている「15 パズル」を解決するために、シミュレーションやゲームでパスを見つけるための一般的なアルゴリズム (A-Star、Dijkstra) も​​使用されていることを読みました。

これらのアルゴリズムの1つを適用できるように、15パズルをノードとエッジのグラフに縮小する方法について、誰かが私にいくつかの指針を与えることができますか?

グラフの各ノードをゲームの状態として扱うとしたら、そのツリーは非常に大きくなりませんか? それとも、それはそれを行うための方法ですか？

A* パス検索アルゴリズムの定義を調べていますが、場所によって定義が多少異なっているようです。

違いは、ノードのサクセサーを通過するときに実行されるアクションと、サクセサーがクローズド リストにあることを見つけることです。

• 1 つのアプローチ (ウィキペディアとこの記事で提案) は、次のように述べています。
• 別のアプローチ (たとえば、こことここで推奨) は次のように述べています。現在計算されているスコアよりも高い場合は、今後の調​​査のためにクローズド リストからアイテムを削除します。

私は混乱しています - どの方法が正しいですか? 直感的には前者の方が分かりやすいのですが、定義の違いが気になります。定義の 1 つが間違っていますか、それとも何らかの形で同形ですか?

私は（ごくわずかな）自由な時間にローグライクゲームに取り組んでいます。各レベルは基本的に、パスで接続されたいくつかの長方形の部屋になります。でも、部屋の間の小道は自然に見えて風が強いようにしたいと思います。たとえば、私は次の自然な見た目を考慮しません。

私は本当にこのようなものが欲しいです：

これらのパスは、いくつかのプロパティを満たす必要があります。

1. 私はそれらが境界を定められている領域を指定できなければなりません、
2. 私は彼らがどれほど風が強くて長いかをパラメータ化できなければなりません、
3. 線は、一方のパスで開始し、もう一方のパスで終了したように見えるべきではありません。たとえば、上記の最初の例は、Aで始まり、Bで終わるように見えます。これは、基本的に、Bと並ぶまで方向を繰り返し変えてから、そこにまっすぐ進むためです。

A *を使用したいと思っていましたが、正直なところ、ヒューリスティックがどうなるかわかりません。遺伝的アルゴリズムの使用も検討しましたが、その方法がどれほど実用的かはわかりません。

私の質問は、私が望む結果を得るための良い方法は何ですか？「A*」や「ダイクストラのアルゴリズム」のような方法を指定するだけでなく、優れたヒューリスティックの支援も必要です。

A* 検索アルゴリズムの Erlang 実装が必要です。ポインタはありますか？

パス検索に A-star (A*) を使用するゲームに取り組んでいますが、1 つのグリッド スクエアよりも大きなオブジェクトがいくつかあるところまで来ました。

16*16px のグリッドで実行しています。壁のセグメントは 16*16 であるため、1 つの正方形は通行できません。私の悪役の何人かは 32*32 で、隙間を通り抜けるには少なくとも 2 グリッドの正方形の隙間があることを確認する必要があります。

デザインには薄い壁 (16 ピクセル) が必要であり、16*16 の正方形を 1 つしか占有しない小さな悪者がいくつかあるため、単純にグリッドを 32*32 にすることはできません。

このマルチ解像度環境を実装するにはどうすればよいですか? A-star は今でも使用する正しいツールですか?

A-star は、グラフの開始ノードと終了ノードの間の最短経路を見つけるために使用されます。ターゲットの状態が具体的に知られておらず、代わりにターゲットの状態の基準しかない場合、何かを解決するためにどのアルゴリズムが使用されますか?

たとえば、Astar のようなアルゴリズムで数独パズルを解くことはできますか? 最終状態がどのように見えるか (どの数字がどこにあるか) はわかりませんが、数独のルール (勝利状態の基準) は知っています。したがって、開始ノードと終了ノードの基準だけがあります。どのアルゴリズムを使用すればよいですか?

AS3 に A* アルゴリズムを実装しましたが、1 つのことを除いてうまく機能します。多くの場合、結果のパスは、ターゲットへの最も「自然な」またはスムーズなルートをたどりません。私の環境では、オブジェクトは、水平または垂直に移動できるのと同じくらい安価に斜めに移動できます。これは非常に簡単な例です。開始点は S でマークされ、終了 (または終了) 点は F でマークされます。

ご覧のとおり、最初の検索ラウンドでは、ノード [0,2]、[1,2]、[2,2] がすべて N のスコアを持つため、可能なノードのリストにすべて追加されます。私が抱えている問題は、続行するノードを決定しようとしている次の時点で発生します。上記の例では、次のノードを選択するために possibleNodes[0] を使用しています。これを possibleNodes[possibleNodes.length-1] に変更すると、次のパスが得られます。

そして、 possibleNextNodes[Math.round(possibleNextNodes.length / 2)-1] で

これらのパスはすべて同じ数のステップを含むため、コストは同じですが、この状況では、最も賢明なパスは次のようになります...

数学的に正しいだけでなく、パスをより賢明に見せるための正式に受け入れられた方法はありますか?

make_heap/push_/pop_A* 操作の優先度キューにstd::vector を使用するよりも、std::set を使用する方が効率的 (wrt 時間) になるのはいつですか? 私の推測では、開いているリストの頂点が小さい場合は、ベクトルを使用する方が良いオプションです。しかし、これを経験した人はいますか？

過大評価/過小評価という用語について混乱しています。A *アルゴリズムがどのように機能するかは完全に理解できますが、過大評価または過小評価するヒューリスティックを使用した場合の影響についてはよくわかりません。

あなたが直接の鳥の視点の線の二乗を取るとき、過大評価はありますか？そして、なぜそれがアルゴリズムを不正確にするのでしょうか？すべてのノードに同じヒューリスティックが使用されます。

直接バードビューラインの平方根を取るとき、過小評価されていますか？そして、なぜアルゴリズムはまだ正しいのですか？

わかりやすく説明している記事が見つからないので、ここの誰かが良い説明をしてくれることを願っています。