Navmesh

A alternativa é uma grade, e grades ficam caras rápido: uma fase grande com resolução de um metro gera milhões de nós para buscar. Uma malha de navegação cobre o mesmo terreno com algumas centenas de polígonos convexos, convexos justamente para que o personagem possa andar em linha reta entre quaisquer dois pontos dentro de um deles sem checagens extras. O A* busca sobre polígonos em vez de células, e o resultado é suavizado depois num caminho contínuo.

As malhas quase sempre são geradas automaticamente a partir da geometria da fase, usando voxelização para marcar onde a inclinação é caminhável e a altura livre é suficiente. O Recast & Detour de Mikko Mononen (2009) é a implementação de referência aberta e está por baixo tanto da Unity quanto da Unreal. Os vínculos entre polígonos podem ter custo ou tipo, e é assim que se modelam pulos, escadas e portas que só alguns personagens podem usar.