Búsqueda de rutas (pathfinding)
Calcular cómo llega un personaje de A a B sin chocar con las paredes, y en una fracción de fotograma.
El problema tiene dos mitades. Primero hay que describir el mundo como un grafo: una rejilla de celdas libres y bloqueadas, una red de puntos de paso colocados a mano o una navmesh de polígonos transitables. Después se recorre el grafo, casi siempre con A* —publicado en 1968 por Peter Hart, Nils Nilsson y Bertram Raphael para el robot Shakey—, que es Dijkstra más una heurística que empuja la búsqueda hacia el objetivo.
El resto del campo es optimización y cosmética. La búsqueda jerárquica divide los mapas grandes en clústeres, los campos de flujo permiten que mil unidades compartan una sola búsqueda y el suavizado de rutas evita los zigzags. Un camino matemáticamente óptimo que parece de robot sigue contando como error.