■

http://pc2.2ch.net/test/read.cgi/gamedev/1079745509/
SRPGとかでよくある移動可能範囲を調べる問題について。ここ見ながら、どっかでみたことあるなと思って探したら
http://www-cs-students.stanford.edu/~amitp/Articles/RangeSighting.html
にそのまんまのが載ってた。要はダイクストラ法(Dijkstra's Algorithm)。A*でh()を0にしたものと一緒。
速度面で工夫する点としてはリンク先に書いてる通り、探索に使うMapのコスト配列は外で確保しとくのがよさそう。OPENリストにpriority queueは…どうなんだろ？OPENリストのサイズがどのくらいになるのかによるか。

たぶんこの用途ではこれが実用的で効率的なアルゴリズムのはず。経路探索の問題としては単一始点最短路問題(single-source shortest-path problem) (SSSP)に属していて、普通に実装したダイクストラ法での計算量オーダーは…？？？調べるの面倒なのでまた後で。
追記：やたらこのダイクストラの計算量についてGoogleで調べてくる人が多いので。http://d.hatena.ne.jp/riesling/20040508を追加。

SSSP問題は今でもいろいろ研究されていて1997年にMikkel Thorup氏によってこの問題を線形時間で解くアルゴリズムが考え出されたりしてます。
と、この論文(たぶん)見たのを思い出して調べた結果。計算量オーダーが線形時間…ありえねぇ。と思ってたのを覚えてる。なんにせよその実装による実験では、実用的な速度は得られなかった。ってのが結論だった気がする。暇な時に元のMikkel Thorup氏の論文読んでみよう。ってことでリンクをメモhttp://www.diku.dk/~mthorup/

http://www.futamura.info.waseda.ac.jp/~futamura/lecture/SoftConst/top.html
のPDF25章より。

• 単一始点最短路問題(single-source shortest-paths problem)
• 単一目的地最短路問題(single-destination shortest-paths ploblem)
• 単一点対最短路問題(single-pair shortest-path problem)
• 全点対間最短路問題(all-pairs shortest-paths problem)

とのこと。