リアルタイムストラテジーの話

A*アルゴリズムの解説
http://www.geocities.com/jheyesjones/astar.html

アルゴリズムの部分だけ訳してみた↓

node_goal = ゴール状態
node_start = 初期状態
OPEN_listにnode_startを入れる
while ( OPEN_listが空でない ) {
　　node_current <- OPEN_list内の最小のfを持つノード
　　node_currentがnode_goalと同じなら終了
　　foreach （node_successor in ｛node_currentからたどれるノード集合｝) [
　　　　node_successor.g = node_current.g + (node_currentからnode_successorまでの移動コスト)
　　　　if (OPENリスト内にnode_successorがあり、かつ、そちらgの方が小さい) {
　　　　　　// リスト内のノードのほうがbetterな経路をたどっているので、
　　　　　　node_successorを破棄し、次へ
　　　　}
　　　　if (CLOSEリスト内にnode_successorがあり、かつ、そちらのgの方が小さい) {
　　　　　　// リスト内のノードのほうがbetterな経路をたどっているので、
　　　　　　node_successorを破棄し、次へ
　　　　}
　　　　node_successorをOPEN_listとCLOSE_listから削除する
　　　　node_successorの親ノードをnode_currentにする
　　　　node_successor.h = node_successorからnode_goalまでの移動コスト(適当なアルゴリズムで予想する)
　　　　node_successorをOPENリストに入れる
　　}
}

node_*.g ： スタート状態からそのノードまでの移動コスト
node_*.h ： そのノードからゴールまでの移動コスト（の予想値）
node_*.f ： node_*.g と node_*.h の合計
OPEN_list ： 判明しているノードの中でまだ探索していないノード
CLOSE_list ： 探索済みのノード

＞node_successor.h = node_successorからnode_goalまでの移動コスト(適当なアルゴリズムで予想する)
ここの移動コスト予想アルゴリズムがキモ。
まぁRTSで使うやつなら適当で言いと思うけど。

>>137
先生! それって自力で考えた経路探索アルゴリズムと全く同じであります!
何度でも車輪を再発明してやるぞｺﾞﾙｱ!

くやしいので最適化の所を纏めてみた。
0)GameGemに最適化手法がいくつか載ってるよ
1)OPEN/CLOSEリストでのnew演算が遅いみたいだから、自分で速いnew作った方が良いよ
2)OPENリストから高速にnodeを取り出すには、OPENリストをpriority queueで実装するといいよ
3)検索に時間をかけたくなかったらハッシュテーブルを使うといいよ
4)後ろ向きの探索はしない方が良いよ。元居たところにそのまま戻るのは絶対に最適解にはなら
ないから((3,4)→(4,4)→(3,4)と動くのは確実に最適解ではない)

以下は僕の私見。
1)に関して:vector等であらかじめでっかい領域を確保しておけばいいように思う
2)に関して:priority queueはSTLの中に入ってる。最上位の要素だけ取り出せればよいのだから、
vectorを常にheapに保っておくのもよいかも(この二つは本質的に同じだが)
3)に関して:hash_mapやhash_setはSTLportやSGI STLの中に入ってる。hasher作るのが面倒とか
3rdパーティ製STLのインストールが面倒ならmap/setで十分と思われ。2Dの升目マップが相手なら
ば、hashなんて遠回りな事をせずに、マップの大きさを持った 2次配列をOPEN/CLOSEリストに使
うのがもっとも高速

僕なら、OPENリストは"heapで管理したvector"と"hash_map"で、CLOSEリストは2次元配列で作るかな。

ようやく良スレの予感age

A*の面白い特性。
移動コストの予想値が常に実際の最小コスト以下ならば、最短の移動経路を求めることができる。
例えば、予想値の重みを0(すなわち無視)にすると確実に最短移動経路が得られる。遅くて無駄も多いが。
だから、
・高速な検索をしたいときには予想値を素早く得て、重み付けも多くつける
・高精度な検索をしたいときにはなるべく正確な予想値を得て、あまり重み付けはあまり重くしない
ということやね。"アホな敵"をシミュレートしたいならこのあたりを工夫すればそれっぽくなりそう。