A*道を探すアルゴリズムの解説+ソースDEMOのデモ
6192 ワード
：http://download.csdn.net/detail/sun2043430/5907609( ) http://download.csdn.net/detail/sun2043430/5909315（ ）
https://github.com/sun2043430/A_Star_Algorithm (github ， ， ) ：http://blog.csdn.net/sunnianzhong/article/details/9899359最近は雲の風の本を復習して、A*が道の計算方法を探すことを見て、この計算方法も私がずっと学んで実現したいのです。週末の暇を利用して練習します。
ネット上でA*アルゴリズムに関する文章、コードと例はもうかなり多くなりました。たくさんの文章を書いています。ほかにもたくさんの外国のウェブサイトがJSでA*アルゴリズムの道探しの過程をダイナミックに示しています。私が見つけた資源は以下の通りです。
1 http://www.raywenderlich.com/zh-hans/21503/a%E6%98%9F%E5%AF%BB%E8%B7%AF%E7%AE%97%E6%B3%95%E4%BB%8B%E7%BB%8D
コメント：生き生きとした例で、説明がとても分かりやすく、上手になりやすい例です。（入門級）
2 http://theory.stanford.edu/~amatp/GamePrograamming/
コメント：長編大作。A＊アルゴリズムの原理、進化過程、発見式、アルゴリズムの実現、A＊実現における各種データ構造の優劣、A＊アルゴリズムの変種、実際にA＊アルゴリズムを使うと発生する問題を非常に詳細に紹介しました。（深いレベル）
3 http://www.ccg.leeds.ac.uk/people/j.macgill/xaStar/
コメント：Javaスクリプトを使って作成した動的デモA*道探しアルゴリズムのホームページです。古典的なA＊アルゴリズムとFdge A＊アルゴリズムの動的探索過程を実証した。（参考になる）
私はMFCを使って経典A*アルゴリズムの動態探索過程をシミュレーションしましたが、基本的にこのページを模倣しました。
以上の文章の作者と雲風の本に感謝します。
アルゴリズムの話もします
A*アルゴリズムはDijkstraアルゴリズムと贪欲アルゴリズムの総合であり、Dijkstraアルゴリズムの欠点は出発点全方位360から外向に向けて広さ優先検索を行うことであり、ノードが多すぎて、速度が遅いため、最適なパスを見つけることができるという点である。貪欲アルゴリズムはいつも最適に見えるコースを選んで前進します。長所はスピードが速いことです。欠点は落とし穴に落ちるかもしれません。むだ足を踏むことです。A＊アルゴリズムは発見的な方式を採用して、両者の長所を総合して、しかも依然として最適な経路を確保できる。
一番簡単な例でAアルゴリズムの発見的な道探しの過程を説明します。ついでにAアルゴリズムの概念を紹介します。
以上の図は例として、赤色が起点で、緑が終点です。私たちはそれぞれの四角形が直接にその上から下までの四つの四角しかないと仮定して、斜線を走ってはいけません。各ブロックには3つの値f，g，h（左上の角はf値、左下の角はg値、右下の角はh値）があります。
次に、f値が一番小さいブロック（右のブロック）を選んで、道を探し続けます。具体的なアルゴリズムは次の通りです。
A*アルゴリズムの具体的な過程
1は2つの空き行列OPENを開けて、CLOSE
2起点のg値を0にし、対応するh，f値を算出し、始点をOPENキューに入れる。
3 OPENキューからf値が一番小さいノードを取り出して仮キューTempQueに入れる（最初からスタート地点という点です。また、f値が一番小さいのは一つだけではないかもしれません。複数あれば取り出します）（OPENキューからこれらのノードを保存しないという意味です。）
4 TempQueの列が空であれば、OPENの列が空であることを意味し、完全な地図を遍歴していることを説明します。この時は道探しを終了するべきです。
5 TempQueのすべてのノードをCLOSEキューに追加します。
6はTempQueの中のすべてのノードノードノードNodeを遍歴します。
Nodeの各隣ノードNeighborを処理します。
NeighborがOPENキューでもCLOSEキューでもない場合、Neighborノードのg，h，f値（g値はNodeのg値に1単位加算）を計算し、Neighborの親ノードをNodeとし、NeighborをOPENキューに追加する。
NeighborがCLOSEのキューにいれば処理しない（ダイナミックなゲームでは状況を見て処理する必要があります。簡単な場合は処理しないでください。）
NeighborがOPEN列にある場合は、Neighbor前のf値と現在計算されたf値とを比較します。現在計算されたf値が小さい場合は、Neighborのf値を更新し、Neighborの親ノードをNodeに設定し直します。
Neighborが終点である場合、道探しは終了し、終点は親ノードの指示に従ってCLOSEキューの中から親ノードを探します。逆に完全な最短経路を作り出します。
7ステップ3に戻り処理を継続する。
A*アルゴリズムキーコード
void CAStar::FindPath()
{
m_bFind = false;
vector minVec;
while (!m_bFind)
{
minVec.clear();
GetMinFromOpen(minVec);
if (minVec.empty())
break;
m_close.insert(m_close.end(), minVec.begin(), minVec.end());
for (vector::iterator it = minVec.begin(); it != minVec.end(); it++)
DoNeighbors(*it);
if (m_bFind)
GetFinalShortestPath();
if (m_CallBack) m_CallBack(m_pArg);
}
}
DEMOプログラム運転画面は以下の通りです。
右の3つのラジオボタンの中から一つを選択して、左に始点、終点または障害物を設定します。
をクリックして道を探し始めたら、道を探す過程をダイナミックにデモンストレーションします。
その中:
赤い四角形を起点とします。
緑の方形が終点です。
青い四角はOPENの列の中の点です。
黄色の四角形はCLOSEの行列の中の点です。
紫のサイコロは最短パスです。
f，g，h値を計算したノードのf値は左上にある。g値は左下にあるh値は右下にある
本人の悪いMFCプログラミングを許してください。画面の前に表示するのはよくないです。どのメッセージで図形を描きますか？しかもダブルバッファを使っていませんので、画面のきらめきが激しいです。また、道を探す過程はマルチスレッドを使っていませんので、道を探している間に画面が詰まります。また、次のバージョンには斜め移動の機能を追加する予定です。
：http://blog.csdn.net/sunnianzhong/article/details/9899359
Update:(2013.8.12) 斜向移动功能
上传了第二版的代码，可在这里下载：http://download.csdn.net/detail/sun2043430/59093151 ， ， 5， 7。 。 。1
2
3
4
1または4の位置が障害物である限り、2から3までの斜め方向の移動は許されません。2 DC ， DC， BitBlt ， 。3 ， 。4 、 。 。