Share
En este tutorial explicaré campo de vectores pathfinding y sus ventajas sobre los algoritmos de búsqueda de rutas más tradicionales, como el de Dijkstra. Una comprensión básica tanto del algoritmo de Dijkstra como de los campos potenciales le ayudará a entender este artículo, pero no es obligatorio.
Pathfinding es un problema con muchas soluciones, y cada una tiene sus pros y sus contras. Muchos algoritmos de búsqueda de rutas funcionan calculando una ruta hacia el objetivo de cada búsqueda, lo que significa que la búsqueda de rutas tomará el doble de tiempo para calcular con el doble de buscadores de rutas. Esto es aceptable en muchas situaciones, pero cuando se trabaja con miles de exploradores, es posible un enfoque más eficiente.
Conocido como campo de vectores pathfinding, este enfoque calcula la ruta desde el objetivo a cada nodo en el gráfico. Para consolidar esta explicación de la búsqueda de rutas de campos vectoriales, explicaré el algoritmo usando mi implementación particular como ejemplo..
Nota: El pathfinding del campo vectorial se puede resumir en nodos y gráficos en general; solo porque lo explique usando mi enfoque basado en mosaico y cuadrícula no significa que este algoritmo esté limitado a mundos basados en mosaico!
El pathfinding del campo vectorial está compuesto por tres pasos..
Este video le muestra los resultados finales, y luego le da una visión general de los conceptos presentados en el tutorial completo a continuación:
El mapa de calor almacena la distancia del camino desde el objetivo a cada mosaico en el mapa. La distancia del camino es distinta de la distancia euclidiana en que es un cálculo de la distancia entre dos puntos que solo pasa por un terreno transitable. Un GPS, por ejemplo, siempre calcula la distancia del camino, siendo las carreteras el único terreno transitable..
A continuación, puede ver la diferencia entre la distancia de la trayectoria y la distancia lineal desde el objetivo (marcado en rojo) a un mosaico arbitrario (marcado en rosa). Los azulejos no transitables se dibujan en verde. Como puede ver, la distancia del camino (que se muestra en amarillo) es 9, mientras que la distancia lineal (mostrada en azul claro) es aproximadamente 4.12.
Los números en la parte superior izquierda de cada mosaico muestran la distancia del camino al objetivo calculado por el algoritmo de generación de mapas de calor. Tenga en cuenta que hay más de una distancia de trayectoria posible entre dos puntos; En este artículo, solo nos interesa el más corto..
El algoritmo de generación de mapas de calor es un algoritmo de frente de onda. Comienza en la portería con un valor de 0, y luego fluye hacia afuera para llenar toda la región transitable. Hay dos pasos para el algoritmo de frente de onda:
Accentsconagua
0.distancia del camino de la baldosa anterior + 1.Nota: El algoritmo de frente de onda simplemente ejecuta una amplia búsqueda en la cuadrícula y almacena los pasos necesarios para llegar a cada ficha en el camino. Este algoritmo a veces también se llama algoritmo de brushfire.
Ahora que se ha calculado la distancia de ruta de cada baldosa a la meta, podemos determinar fácilmente la ruta que se debe tomar para acercarse a la meta. Es posible hacer esto en el tiempo de ejecución para cada buscador de cada cuadro, pero a menudo es mejor calcular un campo vectorial una vez y luego hacer que todos los buscadores se refieran al campo vectorial en tiempo de ejecución.
El campo vectorial simplemente almacena un vector que apunta hacia abajo el gradiente de la función de distancia (hacia la meta) en cada casilla. Aquí hay una visualización del campo vectorial, con los vectores apuntando desde el centro de la baldosa a lo largo del camino más corto hacia la meta (nuevamente se muestra en rojo).
Este campo vectorial se genera una ficha a la vez mirando el mapa de calor. Los componentes x e y del vector se calculan por separado, como se muestra en el pseudocódigo a continuación:
Vector.x = left_tile.distance - right_tile.distance Vector.y = up_tile.distance - down_tile.distance
Nota: La variable de distancia de cada baldosa almacena la distancia de la ruta hacia el objetivo calculada por el algoritmo de frente de onda anterior.
Si alguna de las fichas a las que se hace referencia (izquierda / derecha / arriba / abajo) no es transitable y, por lo tanto, no tiene almacenada una distancia utilizable, la distancia asociada con la ficha actual se usa en lugar del valor faltante. Una vez que el vector de ruta se ha calculado aproximadamente, se normaliza para evitar inconsistencias más adelante.
Ahora que el campo vectorial se ha calculado, es muy fácil calcular el movimiento de un explorador. Suponiendo que vector_field (x, y) devuelve el vector que calculamos anteriormente en el mosaico (x, y), y que la ciudad_vista deseada es un escalar, el pseudocódigo para calcular la velocidad de una partícula en la baldosa (x, y) Se ve como esto:
velocity_vector = vector_field (x, y) * desired_velocity
Las partículas simplemente necesitan comenzar a moverse en la dirección indicada por el vector. Esta es la forma más sencilla de hacerlo, pero se pueden implementar sistemas de movimiento más complicados utilizando campos de flujo..
Por ejemplo, las técnicas explicadas en Comprender los comportamientos de la dirección podrían aplicarse al movimiento del buscador de caminos. En tal situación, el velocity_vector los cálculos anteriores se utilizarían como la velocidad deseada y los comportamientos de dirección se utilizarían para calcular el movimiento real en cada paso de tiempo.
Al calcular el movimiento, hay un problema que a veces puede ocurrir, conocido como optima local. Esto ocurre cuando hay dos caminos óptimos (los más cortos) para llegar al objetivo desde una ficha determinada.
Este problema se puede ver en la imagen de abajo. La baldosa (que se muestra en rosa) inmediatamente a la izquierda del centro de la pared tiene un vector de trayectoria cuyas componentes (x e y) son iguales a 0.
Los optimos locales hacen que los exploradores se atasquen; se referirán al campo vectorial que no indicará la dirección a seguir. Cuando esto suceda, los exploradores permanecerán en la misma ubicación a menos que se implemente una solución.
La forma más elegante (que he encontrado) de solucionar el problema es subdividir el mapa de calor y el campo vectorial una vez. Cada mosaico único de mapa de calor y vector se ha dividido ahora en cuatro mosaicos más pequeños. El problema sigue siendo el mismo con una cuadrícula subdividida; Sólo se ha minimizado ligeramente..
El verdadero truco que resuelve el problema del óptimo local es agregar inicialmente cuatro nodos de objetivo, en lugar de solo uno. Para hacer esto simplemente tenemos que modificar el primer paso del algoritmo de generación de mapas de calor. Cuando solíamos agregar solo un objetivo con una distancia de ruta de 0, ahora agregamos las cuatro casillas que están más cerca del objetivo.
Hay varias formas de elegir las cuatro fichas, pero la forma en que se eligen es en gran medida irrelevante, siempre que las cuatro fichas sean adyacentes (y atravesables), esta técnica debería funcionar..
Aquí está el pseudocódigo alterado para la generación de mapa de calor:
0.distancia del camino de la baldosa anterior + 1.Y ahora, aquí están los resultados finales, que muestran claramente que el problema de los óptimos locales se ha eliminado:
Aunque esta solución es elegante, dista mucho de ser ideal. Su uso significa que calcular el mapa de calor y el campo vectorial toma cuatro veces más tiempo debido al mayor número de fichas.
Otras soluciones requieren hacer verificaciones y luego determinar qué dirección tomar en cada caso, lo que ralentiza significativamente los cálculos de movimiento de partículas. En mi caso, subdividir los mapas fue la mejor opción..
Esperemos que este tutorial le haya enseñado a implementar la búsqueda de caminos basada en objetivos en un mundo basado en mosaicos. Tenga en cuenta que este tipo de búsqueda de caminos es, en esencia, simple: las partículas siguen el gradiente de la función de distancia hacia la meta.
La implementación es más compleja, pero se puede dividir en los siguientes tres pasos manejables:
Espero ver a la gente ampliar las ideas presentadas aquí. Como siempre, si tiene preguntas, no dude en preguntarlas en los comentarios a continuación!
