ナビメッシュ

代替案はグリッドだが、グリッドはすぐに高くつく。広いレベルを1メートル刻みにすると、探索すべきノードが数百万になるのだ。ナビゲーションメッシュは同じ範囲を数百の凸ポリゴンで覆う。凸にするのは、ポリゴン内の任意の二点の間を、余計な判定なしに直線で歩けるようにするためだ。A* はセルではなくポリゴンを対象に探索し、結果は後から歩ける線へ滑らかに整えられる。

メッシュはほとんどの場合、レベルのジオメトリから自動生成される。ボクセル化によって、傾斜が歩ける範囲で頭上の空間が足りる場所に印を付ける。Mikko Mononen の Recast & Detour（2009年）はオープンソースの参照実装で、Unity と Unreal の両方の基盤にもなっている。ポリゴン間のリンクにはコストや種類を持たせられ、ジャンプ、はしご、特定のキャラクターしか通れないドアはこうして表現される。