経路探索
キャラクターが壁にぶつからずにAからBへ行く道筋を、1フレームのごく一部の時間で求めること。
問題は二段構えになっている。まず世界をグラフとして表す必要がある。通行可能・不可能なセルのグリッド、手で置いたウェイポイントの網、歩行可能なポリゴンからなるナビメッシュなどだ。次にそのグラフを探索するが、ほぼ例外なくA*が使われる。1968年にPeter Hart、Nils Nilsson、Bertram Raphaelがロボット「Shakey」のために発表したもので、ダイクストラ法に、ゴールへ探索を引き寄せるヒューリスティックを加えたものである。
残りは最適化と見栄えの話だ。階層型経路探索は大きなマップをクラスタに分け、フローフィールドは千体のユニットが一回の探索を共有できるようにし、パススムージングは結果のジグザグを取り除く。数学的に最短でもロボットのように見える経路は、やはりバグ扱いになる。