■

以下　http://theory.stanford.edu/~amitp/GameProgramming/のImplementation notes　を参考に書いた。

A*の実装について。A*は「OPEN」と「CLOSED」この二つのノード集合の操作によって探索を進めるわけだけど、このノード集合をどんな形で内部に保持するかが問題となる。
「OPEN」側に必要な操作は以下の３つ。

• member あるノードがその集合に属しているかどうかを調べる
• insert ノードをその集合の適切な位置に挿入する
• remove-best コストが最小のノードをとってきて、その集合から削除する

以上、この３つの操作が主。priority queueと同じような操作。
あと一つ、上の３つより行われる頻度は少ないけれど必要な操作。開いたノードが既に「OPEN」に含まれていて、記録されていたｆコストより新しいｆコストのほうがよかった場合。このとき、ノードのdeleteと新しいｆコストでノードのinsert、この２つの操作を行う必要がある。

何かそのまま訳しただけっぽくなってしまった…元の文章が簡潔にまとめられてるから要約する余地がない…ともかく、これらの操作についての計算時間量オーダーを小さくするにはどんなデータ構造にすればよいのか、について述べられている。

priority queueについては他の所も調べてみたけど、特に使えそうなものはなし。上のリンク先にのってるデータ構造でほとんど網羅してる感じ。まあ、ゲームに使うのはせいぜいノード数、100×100程度だろうから、あんまり複雑な実装しても遅くなるだけだろう。