ファンネルアルゴリズム

ナビメッシュ上のA*が返すのは経路ではなく三角形のリストである。各三角形の中心を単純につなぐと、無駄に長いジグザグになる。ファンネルアルゴリズムは、隣り合う三角形が共有する辺をポータルの列とみなし、左右の辺の間にじょうご（ファンネル）を張る。そして辺ごとにじょうごを絞り込み、左右の辺が交差した時点で最も内側の角にウェイポイントを置き、そこから新しいじょうごを始める。回廊に通した紐をぴんと引っ張るような効果が得られる。

理論的な土台はHershbergerとSnoeyink（1994年）の研究だが、ゲーム界ではMikko Mononenのコンパクトな「simple stupid funnel algorithm」として知られる。三角形の探索と、エージェントが実際に歩く線との間に挟む後処理として、定番の存在である。