Pathfinding es un término en informática e inteligencia artificial que significa que un programa de computadora determina la ruta mejor y óptima entre dos puntos.
Pathfinding en el contexto de los juegos de computadora se refiere al camino que toma un objeto en movimiento para sortear los obstáculos. Muy a menudo, la tarea de encontrar un camino surge en las estrategias en tiempo real , en las que el jugador instruye a las unidades del juego (unidades) para moverse a través del nivel del juego , que contiene obstáculos. Además de las estrategias, la tarea de encontrar un camino, de un modo u otro, se encuentra hasta cierto punto en la mayoría de los géneros de juegos modernos . A medida que los juegos se vuelven más complejos, la búsqueda de caminos también evoluciona y evoluciona con ellos.
Los juegos de estrategia en tiempo real suelen contener grandes áreas con terreno abierto, en las que la búsqueda de caminos suele ser una tarea sencilla. Sin embargo, en la mayoría de los casos, no solo una unidad se mueve por el mapa, sino varias, lo que crea la necesidad de algoritmos de búsqueda de rutas diferentes y mucho más complejos para evitar atascos de tráfico en áreas estrechas del paisaje del juego. En las estrategias, el nivel del juego se divide en mosaicos ( tiles ingleses ), que actúan como nodos ( nodos ingleses ) en el algoritmo de búsqueda de caminos [1] [2] .
El género de disparos en 3D utiliza espacios mucho más limitados que no se dividen fácilmente en nodos. Aquí, en lugar de nodos, se utilizan los llamados puntos de ruta (literalmente del inglés - "puntos de ruta"). Los waypoints son nodos irregulares y configurados manualmente que contienen información sobre a qué otros nodos se puede llegar desde uno determinado.
En esencia, el algoritmo de búsqueda de rutas busca en el gráfico , comenzando en un punto (de inicio) y explorando los nodos adyacentes hasta que se alcanza el nodo de destino (nodo final). Además, los algoritmos de búsqueda de rutas en la mayoría de los casos también tienen el objetivo de encontrar la ruta más corta. Algunos métodos de búsqueda de gráficos, como la búsqueda primero en amplitud, pueden encontrar una ruta si se les da suficiente tiempo. Otros métodos que "exploran" el gráfico pueden llegar al destino mucho más rápido. Aquí puedes dibujar una analogía con una persona caminando por una habitación. Una persona puede, antes de comenzar el viaje, explorar de antemano todas las características y obstáculos en el espacio, calcular la ruta óptima y solo entonces comenzar el movimiento directo. En otro caso, una persona puede ir inmediatamente en la dirección aproximada o prevista de la meta y luego, ya durante el viaje, hacer ajustes en su movimiento para evitar colisiones con obstáculos.
Los algoritmos de búsqueda de rutas más famosos y populares incluyen los siguientes algoritmos [3] [4] :