■

Googleでゲーム方面から探した結果。
http://www.ensemblestudios.com/age/journalmenu.html
Age of Empiresシリーズの開発元のページ。使ってるアルゴリズムなんかを詳しく解説してる。左下のほうのTerrain analysis。AoE2では大体60〜70%の時間を経路探索に使ってるらしい。

AoE2では３つの探索方法を状況に応じて使い分けている。

• MipMapを用いた探索。要するに低解像度にしたマップ。移動が長距離の場合の大まかなルート、移動の可不可を調べる。
• ポリゴンベース。探索領域内に動的にconvex hullsを作って探索。
• タイルベース。基本

理解がいまいちのため、うまく説明できず。特に後半の方。
たぶん、障害物が少ない所では動的に変化する凸ポリゴン集合を作っておいてポリゴンベースで探索、それ以外はタイルベースで探索するってことをいってるんだと思うんだが。
ただ、これだとpolygonal pathfinderが短距離用、tile-based pathfinderが短、中距離用っていう文中の説明と合ってない…もっかい後で読み直してみるか。

追記:リンク先消えてる。元はGDC2000の講演なのでそっちから探せば見つかるはず。題名はTerrain Analysis in Realtime Strategy Games。

http://www.gilgameshcontrite.com/Computer_AI/
RTS系のゲームAIについて。