A*道探しアルゴリズムについての浅薄な研究と実現
ことばを引く
最近いつも古い本を掘ることが好きで、前に勉強したことがあるあるいは駆け足で花を見たことがあるいくつかの経典の計算方法を取り出して研究して、実現します;図アルゴリズムの中のDijkstraを復習するアルゴリズムをきっかけに、このアルゴリズムがノードを拡張する時に絶えず膨張する環状パスを見ているようにしましょう.続いて、Aアルゴリズムによって収集された研究資料を紹介します.自分の未来のゲーム開発の夢に役立つように.ミスがあったら指摘してください.本当のゲーム業界の開発者が貴重な意見を出すことを望んでいます.
余計なことを言わないで、先にDEMOを放出します.
方眼のA*道探しアルゴリズムDEMO
その中で、横方向の1マスの散逸は1で、斜め方向の1マスの散逸は1.4で、緑の塊は進入可能なエリアで、黒いブロックは進入できないエリアです.右側は道を探す時間を見て、啓発関数を選ぶことができます.
DEMOはAS 3.0を利用してFlashdevelope環境の下でプログラミングして、後で便利に拡張するために、大体次のように設計されています.
A*アルゴリズム
いくつかの不正規用語:
ノード:経路で到達可能な点
親ノード:特定の経路のうちのノードの前のノード
後継ノード:ノードが到達可能な任意のノード
出発点:道を探して始まるノード
終点:到着したいノード
openリスト:チェックノード集合
クローズドリスト:チェックノードの集合
現在の散逸g:特定の経路における起点から現在のノードへの権能値
散逸を推定するh:現在のノードから終点までの推定値は、啓発関数hによって求められる.
パス散逸f:あるノードの特定のパスにおける権利値、f=g+h
アルゴリズムの説明:
A*アルゴリズムの可能な改善
四角格子で実現することを例にとって、A＊アルゴリズムの改善点を見てみよう.
以下の主な参考は http://www.cs.auckland.ac.nz/~burkhard/Reports/2003_SS_DanielWichmann 2.pdf
和 http://www.policyalmanac.org/games/binaryHeaps.htm
及び『人工知能——一種の現代方法』
隣接領域の選択:
上の図からも分かるように、隣接領域選択は4、8、または16の近傍領域を有し、求められた経路は逐次平滑化されているが、対応する計算コストは大きい.
ヒント関数の選択:
伝統的な啓発関数は主にマンハッタンの距離、ヨーロッパの距離と対角の距離があります.DEMOでは具体的な効果が得られます.
マンハッタン距離は、計算がプラスマイナスにしか及ばないので、計算が速いです.その最大の欠陥は非4近傍領域の場合に散逸を過大に推定し,最短経路に到達できない可能性があることである.しかし、一般的なゲームの中では道を探すことに対して、最適ではないが、良いパスであれば、要求を満たすことができます.だから、マンハッタンの距離は実用性が高いです.
洋式距離は、計算が乗と開方に関係するので、計算速度が思わしくなく、かつ過小な推定散逸は、任意の近隣の状況で得られる経路を最適にすることができるが、より多くのノードを遍歴して道を探す速度をさらに低下させる必要がある.非格子の場合は、欧風距離にも良い適用性がある(座標があれば距離がある).
対角線距離は、上記の2つの特徴を組み合わせて、4、8の近傍領域で最適なパスを得ることができ、計算速度がヨーロッパ式距離よりもやや高くなります.
データ構造の改善:
道を探す過程の中で、openとclosedのだんだん増大することに従って、この2つの時計の空間と計算時間を遍歴するのは巨大で、openとclosedの改善から着手します.
ヒープ構造の使用は、ループ毎にオーブリストから散逸値が最小のノードを選択するため、オーブリストを最小のヒープに維持し、その動作の時間の複雑さを低減することができる.
openリストは記憶サイズを制限し、同時に記憶空間と計算時間を下げることができますが、支払いの代価は完全性の損失であり、すなわち最適解を見つけることができるとは限りません.
散逸最大値を捨て、上述した構成に基づいて、新しいノードを追加する必要があるたびに、最も散逸が大きいノード(すなわち、最も拡張不可能なノード)を捨てて、リストサイズを変更しないようにする.同様に完全性を備えておらず、具体的なデータ構造を考慮する必要があります.
散逸値はカットオフされ、各サイクルにおいて、リストに参加する資格があるノードは、カットオフ値を満たす散逸値を有し、リストサイズを小さくし、完全性を備えていない.各サイクルのカットオフ値は、前回のサイクルでカットオフ値を満たすノードの中で最小の散逸値が望ましい.(ちょっと言いにくいです.)
ほとんどのデータ構造、または道を探す戦略の改善は、完全性を捨てることを代価としているが、リアルタイム性が高いゲームにとっては、これは受け入れられる.
マルチスケールの方法:
大きな,比較的簡単な地図に対して,マルチスケール法は選択かもしれない.(デモの中の細部の迷路は不適切です)
原図を比例的に縮小して、サイズが小さいが、基本的に特徴のある地図を得ることができます.小さいサイズで道探しアルゴリズムを実行すれば、計算速度が大幅に向上することができます.得られたパスポイントを元の地図に戻します.同様に、サイズの変化によって、いくつかの詳細が捨てられることが予想され、この方法には必然的に不完全性がある.
地図構造の改良
主な参考はhttp://www.ai-blog.net/archives/000152.html
過去(これは過去にさかのぼります.仙剣1時代にさかのぼります.)の多くのゲームは、現在のレジャーゲームや、ラウンドゲーム(SLG)ゲームなども、基本的な地図構造として正方形のグリッドを使用しています.四角格子は自動分布の特徴があり、実現しやすい.しかし、下図のような地形に対しては、正方形のメッシュは効果的にフィットしにくい、あるいはキャラクターの進行経路がおかしくないように、単位メッシュの数が非常に多いです.
したがって、このような問題を初歩的に解決するために、way−points法があり、四角格子は、図に示すように、この方法の特殊な形であると考えられ得る.
この方法は複雑な地形をより良くフィッティングできるが,同じように不思议でないために,分布するノードの数は巨大である.
実際には、平坦な地域にノードを分布させることはしばしば不要であり、直線に沿って完全に走ることができるので、より科学的なnavigationn-meshがあり、次の図を示す.
エッジにだけノードを設ける必要があります.地図は複数の多角形を組み合わせて、多角形内を自由に歩くことができます.これにより、道を探すために必要なノード数が大幅に減少しました.
すべては順理成章で完璧に見えますが、肝心な点はナビゲーション・パネルで道を探す実現方法は相対的に複雑で、幾何学的な知識が含まれています.ノードの制約がなくなっているが、ノードが提供する明確な前駆的後継関係もない.
後記
各種のゲームの中で、道を探すアルゴリズムはすべて広範な用途を持っていて、しかし道を探す問題は完全に解決していません.個人の感覚は実際の需要によって考慮して、ゲームの種類、ゲームの体験、地図を含んで特徴を描写して場所によって適切な実現のA*が道の計算方法を探すことができます.本文には釈迦に説法の疑いがあります.間違いがあれば、一緒に勉強するためです.
編集待ち
最近いつも古い本を掘ることが好きで、前に勉強したことがあるあるいは駆け足で花を見たことがあるいくつかの経典の計算方法を取り出して研究して、実現します;図アルゴリズムの中のDijkstraを復習するアルゴリズムをきっかけに、このアルゴリズムがノードを拡張する時に絶えず膨張する環状パスを見ているようにしましょう.続いて、Aアルゴリズムによって収集された研究資料を紹介します.自分の未来のゲーム開発の夢に役立つように.ミスがあったら指摘してください.本当のゲーム業界の開発者が貴重な意見を出すことを望んでいます.
余計なことを言わないで、先にDEMOを放出します.
方眼のA*道探しアルゴリズムDEMO
その中で、横方向の1マスの散逸は1で、斜め方向の1マスの散逸は1.4で、緑の塊は進入可能なエリアで、黒いブロックは進入できないエリアです.右側は道を探す時間を見て、啓発関数を選ぶことができます.
DEMOはAS 3.0を利用してFlashdevelope環境の下でプログラミングして、後で便利に拡張するために、大体次のように設計されています.
A*アルゴリズム
いくつかの不正規用語:
ノード:経路で到達可能な点
親ノード:特定の経路のうちのノードの前のノード
後継ノード:ノードが到達可能な任意のノード
出発点:道を探して始まるノード
終点:到着したいノード
openリスト:チェックノード集合
クローズドリスト:チェックノードの集合
現在の散逸g:特定の経路における起点から現在のノードへの権能値
散逸を推定するh:現在のノードから終点までの推定値は、啓発関数hによって求められる.
パス散逸f:あるノードの特定のパスにおける権利値、f=g+h
アルゴリズムの説明:
： ， ，open，closed；
open， f ；
while(open ) {
open f ；
if( == )
break；
for each {
f ；
open closed ：
if( open || closed f f )
continue;
else
open || closed open
}
closed
}A*アルゴリズムの可能な改善
四角格子で実現することを例にとって、A＊アルゴリズムの改善点を見てみよう.
以下の主な参考は http://www.cs.auckland.ac.nz/~burkhard/Reports/2003_SS_DanielWichmann 2.pdf
和 http://www.policyalmanac.org/games/binaryHeaps.htm
及び『人工知能——一種の現代方法』
隣接領域の選択:
上の図からも分かるように、隣接領域選択は4、8、または16の近傍領域を有し、求められた経路は逐次平滑化されているが、対応する計算コストは大きい.
ヒント関数の選択:
伝統的な啓発関数は主にマンハッタンの距離、ヨーロッパの距離と対角の距離があります.DEMOでは具体的な効果が得られます.
マンハッタン距離は、計算がプラスマイナスにしか及ばないので、計算が速いです.その最大の欠陥は非4近傍領域の場合に散逸を過大に推定し,最短経路に到達できない可能性があることである.しかし、一般的なゲームの中では道を探すことに対して、最適ではないが、良いパスであれば、要求を満たすことができます.だから、マンハッタンの距離は実用性が高いです.
洋式距離は、計算が乗と開方に関係するので、計算速度が思わしくなく、かつ過小な推定散逸は、任意の近隣の状況で得られる経路を最適にすることができるが、より多くのノードを遍歴して道を探す速度をさらに低下させる必要がある.非格子の場合は、欧風距離にも良い適用性がある(座標があれば距離がある).
対角線距離は、上記の2つの特徴を組み合わせて、4、8の近傍領域で最適なパスを得ることができ、計算速度がヨーロッパ式距離よりもやや高くなります.
データ構造の改善:
道を探す過程の中で、openとclosedのだんだん増大することに従って、この2つの時計の空間と計算時間を遍歴するのは巨大で、openとclosedの改善から着手します.
ヒープ構造の使用は、ループ毎にオーブリストから散逸値が最小のノードを選択するため、オーブリストを最小のヒープに維持し、その動作の時間の複雑さを低減することができる.
openリストは記憶サイズを制限し、同時に記憶空間と計算時間を下げることができますが、支払いの代価は完全性の損失であり、すなわち最適解を見つけることができるとは限りません.
散逸最大値を捨て、上述した構成に基づいて、新しいノードを追加する必要があるたびに、最も散逸が大きいノード(すなわち、最も拡張不可能なノード)を捨てて、リストサイズを変更しないようにする.同様に完全性を備えておらず、具体的なデータ構造を考慮する必要があります.
散逸値はカットオフされ、各サイクルにおいて、リストに参加する資格があるノードは、カットオフ値を満たす散逸値を有し、リストサイズを小さくし、完全性を備えていない.各サイクルのカットオフ値は、前回のサイクルでカットオフ値を満たすノードの中で最小の散逸値が望ましい.(ちょっと言いにくいです.)
ほとんどのデータ構造、または道を探す戦略の改善は、完全性を捨てることを代価としているが、リアルタイム性が高いゲームにとっては、これは受け入れられる.
マルチスケールの方法:
大きな,比較的簡単な地図に対して,マルチスケール法は選択かもしれない.(デモの中の細部の迷路は不適切です)
原図を比例的に縮小して、サイズが小さいが、基本的に特徴のある地図を得ることができます.小さいサイズで道探しアルゴリズムを実行すれば、計算速度が大幅に向上することができます.得られたパスポイントを元の地図に戻します.同様に、サイズの変化によって、いくつかの詳細が捨てられることが予想され、この方法には必然的に不完全性がある.
地図構造の改良
主な参考はhttp://www.ai-blog.net/archives/000152.html
過去(これは過去にさかのぼります.仙剣1時代にさかのぼります.)の多くのゲームは、現在のレジャーゲームや、ラウンドゲーム(SLG)ゲームなども、基本的な地図構造として正方形のグリッドを使用しています.四角格子は自動分布の特徴があり、実現しやすい.しかし、下図のような地形に対しては、正方形のメッシュは効果的にフィットしにくい、あるいはキャラクターの進行経路がおかしくないように、単位メッシュの数が非常に多いです.
したがって、このような問題を初歩的に解決するために、way−points法があり、四角格子は、図に示すように、この方法の特殊な形であると考えられ得る.
この方法は複雑な地形をより良くフィッティングできるが,同じように不思议でないために,分布するノードの数は巨大である.
実際には、平坦な地域にノードを分布させることはしばしば不要であり、直線に沿って完全に走ることができるので、より科学的なnavigationn-meshがあり、次の図を示す.
エッジにだけノードを設ける必要があります.地図は複数の多角形を組み合わせて、多角形内を自由に歩くことができます.これにより、道を探すために必要なノード数が大幅に減少しました.
すべては順理成章で完璧に見えますが、肝心な点はナビゲーション・パネルで道を探す実現方法は相対的に複雑で、幾何学的な知識が含まれています.ノードの制約がなくなっているが、ノードが提供する明確な前駆的後継関係もない.
後記
各種のゲームの中で、道を探すアルゴリズムはすべて広範な用途を持っていて、しかし道を探す問題は完全に解決していません.個人の感覚は実際の需要によって考慮して、ゲームの種類、ゲームの体験、地図を含んで特徴を描写して場所によって適切な実現のA*が道の計算方法を探すことができます.本文には釈迦に説法の疑いがあります.間違いがあれば、一緒に勉強するためです.
編集待ち