Maillage de navigation Navmesh
Une carte polygonale simplifiée des endroits où un personnage peut réellement marcher dans le monde du jeu.
L'alternative, c'est la grille, et les grilles deviennent vite coûteuses : un grand niveau à un mètre de résolution donne des millions de nœuds à explorer. Un maillage de navigation recouvre le même terrain avec quelques centaines de polygones convexes — convexes précisément pour qu'un personnage puisse marcher en ligne droite entre deux points quelconques d'un même polygone sans autre vérification. A* cherche alors sur des polygones plutôt que sur des cellules, et le résultat est lissé ensuite en une ligne praticable.
Les maillages sont presque toujours générés automatiquement à partir de la géométrie du niveau, par voxélisation, pour repérer où la pente est franchissable et la hauteur libre suffisante. Recast & Detour de Mikko Mononen (2009) est l'implémentation de référence ouverte, présente sous Unity comme sous Unreal. Les liaisons entre polygones peuvent porter un coût ou un type, ce qui permet de modéliser les sauts, les échelles et les portes que seuls certains personnages ont le droit d'emprunter.