Búsqueda de ruta

Se denomina pathfinding en inglés, al trazado por una aplicación de computadora, del camino más corto entre dos puntos. Esta área de investigación está basada mayoritariamente en el Algoritmo de Dijkstra para la búsqueda de la ruta más corta.

El concepto de búsqueda de caminos jerárquica precede a su adopción por la industria de los videojuegos y tiene sus raíces en la investigación clásica de la inteligencia artificial. Una de las primeras descripciones formales aparece en el trabajo de Sacerdoti sobre ABSTRIPS (Abstraction-Based Stanford Research Institute Problem Solver|STRIPS) en 1974,^[1]​ que explora estrategias de búsqueda jerárquica en la planificación basada en lógica. Investigaciones posteriores, como la de Hierarchical A* por Holte et al., desarrollaron aún más la teoría de jerarquías de abstracción en problemas de búsqueda.^[2]​

En el contexto de los videojuegos, la necesidad de planificación eficiente en mapas grandes con tiempo de CPU limitado llevó a la implementación práctica de algoritmos de búsqueda de caminos jerárquicos. Un avance notable fue la introducción de Draft:Hierarchical Path-Finding A* (HPA*) por Botea et al. en 2004.^[3]​ HPA* divide el mapa en clústeres y precalcula caminos locales óptimos entre puntos de entrada de clústeres adyacentes. En tiempo de ejecución, planea un camino abstracto a través del grafo de clústeres y luego lo refina dentro de cada clúster. Esto reduce significativamente el espacio de búsqueda y permite una planificación casi óptima con un rendimiento mucho más rápido.

Partial-Refinement A* (PRA*), desarrollado por Sturtevant y Buro, toma un enfoque similar pero enfatiza la planificación y ejecución entrelazadas. En lugar de refinar todo el camino inmediatamente, PRA* refina solo los primeros pasos y continúa refinando el resto según sea necesario durante la ejecución. Esto es especialmente úctil en entornos dinámicos.

Técnicas similares incluyen el uso de navigation mesh es (navmesh), utilizadas para la planificación geométrica en juegos, y la planificación de transporte multimodal, como en variantes del problema del viajante que involucran múltiples tipos de transporte.

Un planificador jerárquico realiza la búsqueda de caminos en dos fases: primero, entre clústeres a un nivel alto; luego, dentro de los clústeres individuales a nivel bajo.^[4]​ Esta estructura permite una búsqueda local guiada con menos nodos, lo que da como resultado un alto rendimiento. El principal inconveniente es la complejidad de implementar y mantener capas de abstracción y refinamientos.