ナビゲーション・メッシュとは単位多角形(普通は三角形)同士がリンクしたデータのことです。この上で、始点と目的地を指定してA*アルゴリズムを走らせると、最短パスが導かれます。ナビゲーション・メッシュに地形の地表情報が埋め込んでおくと、状況に応じて地表の状況を考慮に入れたパス検索を行うことが可能になります。例えば、水のあるメッシュ、砂のメッシュ、崖近くのメッシュ、など様々な地形情報をメッシュ埋め込んでA*検索のコストに盛り込むことで、地形を考慮に入れた「知性的なパス」を導くことが可能となります。デモの途中で、埋め込まれたデータを色を分けて表示しています。(CEDEC2006「クロムハウンズにおける人工知能開発から見るゲームAIの展望」三宅陽一郎)
http://cedil.cesa.or.jp/session/detail/50