example - a*algorithm java

Pathfinding en mapa grande

Question

Estoy creando un juego con un mapa de 10,000 por 10,000.
Me gustaría que un usuario pueda establecer una ubicación y que la computadora encuentre instantáneamente el mejor camino.
Sin embargo, dado que el mapa es de 10,000 por 10,000, hay 100,000,000 de nodos, y encontrar este camino a través de un método convencional como A * o Dijkstra''s requeriría una gran cantidad de memoria y mucho tiempo.
Entonces mi pregunta es: ¿Cómo puedo encontrar el mejor camino?
El algoritmo que estoy considerando dividiría el mundo en 100 secciones, cada una con 1,000,000 de nodos. Cada sección se dividiría entonces en 100 subsecciones. Esto se repetiría hasta que cada subsección contenga 100 nodos. El algoritmo luego encontraría la mejor ruta de las secciones, luego las subsecciones, luego las sub-sub secciones hasta que encuentre el mejor conjunto de nodos. ¿Funcionaría esto y hay una manera mejor?
También estoy considerando una búsqueda de puntos de salto, pero no lo sé, y sería un dolor aprender solo para encontrar que no puede hacerlo.

Edit: he intentado agregar A *. Sin embargo, tardó unos 5 segundos en ejecutarse, lo cual es aproximadamente 4 segundos más que lo ideal.

Answer 1

1. Asegúrese de que todos los datos del gráfico estén en la memoria
2. Utilice Dijkstra bidireccional, suponiendo que tenga varios núcleos
3. Busque en el uso de jerarquías de contracción, esto mejorará en gran medida el rendimiento.
4. Pre-calcule todo lo que pueda, tales como pesos de ruta.

Answer 2

Dado que el mapa es de 10.000 x 10.000, el número de nodos es de 100.000.000. Usar una implementación sencilla de A * no sería práctico y, por supuesto, no haría que el juego sea escalable en el tamaño de mapas.

Te recomendaría usar la siguiente solución, que es esencialmente lo que estabas pensando:

HPA * (ruta jerárquica A *). Este método crea diferentes jerarquías de mapa. Puede automatizar el proceso diciendo que cada bloque de 100x100 píxeles es una región. Luego, para cada bloque, necesitamos encontrar los bloques adyacentes y dónde están las entradas y salidas de cada bloque. Si la conexión entre los dos bloques es más que un nodo, entonces usamos dos nodos para representar el problema. Esta imagen explica el nuevo gráfico que estamos tratando de construir. (Negro = obstáculo y gris están conectando nodos entre bloques).

Este método proporciona buenos resultados, como se puede ver en una ejecución usando mapas del juego Baldur''s Gate con cada bloque de 10x10.

Para obtener más información, lea este artículo de Nathan Sturtevant (es uno de los investigadores más exitosos en la búsqueda de caminos cuando se trata de juegos). https://skatgame.net/mburo/ps/path.pdf

Para obtener una explicación de HPA, consulte esta conferencia de Sturtevant (min. 43:50 para HPA). https://www.youtube.com/watch?v=BVd5f66U4Rw

Además, si quieres ver el HPA * en acción, mira este video que hizo Sturtevant: https://www.youtube.com/watch?v=l7YQ5_Nbifo

Answer 3

Esto será un poco más largo de lo que cabe en un comentario, por lo tanto, una respuesta.

Su configuración requiere una aclaración. 10,000x10,000 está bien, pero esta declaración no lo es:

Ya que el mapa es 10,000 por 10,000, hay 100,000,000 nodos.

¿Por qué habría 1 nodo por cada unidad del sistema de coordenadas? No es así como funciona la búsqueda de rutas de los nodos, sino que se supone que los nodos son más dispersos, y por su existencia describen puntos individuales (dispersos) a lo largo de la ruta. Entre los puntos de nodo, el objeto maneja el movimiento por otros medios. En el peor de los casos (si no hay obstáculos), un sistema de búsqueda de rutas en la rejilla puede tener 100,000,000 puntos, pero como Q menciona los nodos , asumo que se trata de la búsqueda de rutas de los nodos.

100,000,000 nodos

100,000,000 nodos es 381 megabytes de memoria si es int32 y 763 mb si es float64. Además, hay conexiones de nodo. No tengo idea de cómo se establecerían en su caso, pero cada conexión requiere 2 enteros, por ejemplo, de 2 bytes cada uno. Es decir. Si hay tantas conexiones como nodos, se necesitan otros 381 mb. En general, terminamos con datos de gráficos más cercanos a un terabyte, y afirmo que, por supuesto, algo anda mal.

¿Cómo resolver el problema, siempre que todavía tengamos un gran gráfico de nodos / un área enorme? Probablemente lo simplificaría, creando cuadrantes más grandes (como mencionaste). Sin embargo, cada cuadrante sostendría nodos solo a lo largo de los 4 bordes , todos los nodos dentro de un cuadrante serían reemplazados por líneas rectas. De esta manera, uno resolvería los puntos de entrada / salida para cada cuadrante. Este sería un gráfico de nodo separado, para el cálculo aproximado. Luego, dentro de un cuadrante, siempre se cargaría el gráfico del nodo interno para ese cuadrante solo en el momento . Ofc habría algún tipo de error involucrado, pero bueno, eso es la vida real, ¿verdad? Si se trata del comportamiento humano, bueno, entonces no siempre está completamente optimizado.

Los cálculos previos, el caché, la velocidad y los datos pequeños son palabras clave en la codificación del juego.

Answer 4

Mi comprensión inicial de la declaración del problema fue la siguiente. Hay ubicaciones de terminales predefinidas en el mapa. El usuario selecciona una ubicación en el mapa, y se debe encontrar la ruta mejor / más corta a la más cercana de esas ubicaciones.

Si mi entendimiento es correcto, entonces puede calcular las rutas más cortas para todas las ubicaciones en su mapa a través de una sola aplicación del algoritmo BFS. Puede almacenar esa información de manera eficiente utilizando solo 2 bits por nodo (el valor asociado con cada nodo indicará en qué dirección debe moverse desde ese nodo para permanecer en la ruta más corta).

Sin embargo, como ha comentado tobias_k , el problema puede definirse de manera diferente: el jugador selecciona una ubicación arbitraria en el mapa y se debe encontrar la mejor ruta desde la ubicación actual hasta esa ubicación. El enfoque descrito anteriormente puede ser utilizado de nuevo, siempre que

1. El jugador no se mueve por el mapa demasiado rápido y
2. Se puede tolerar alguna inexactitud.

Luego, el algoritmo ya descrito se ejecuta para encontrar las rutas más cortas desde cualquier ubicación en el mapa hasta una pequeña circunferencia centrada en la ubicación actual del jugador. Luego, durante un corto período de tiempo, esos datos se pueden usar para encaminar rápidamente el camino casi más corto hacia cualquier ubicación en el mapa. Cuando el jugador, mientras se mueve, se acerca demasiado al límite de ese círculo, el algoritmo se ejecuta preventivamente para la nueva ubicación del jugador.

La desventaja de este enfoque es que consume una gran cantidad de recursos de CPU. La ventaja es su simplicidad.

Answer 5

Si su mapa tiene un peso uniforme (excepto los obstáculos, por supuesto), puede tener un mejor rendimiento con:

1. Un algoritmo que procesa la cuadrícula en un gráfico, colapsando espacios grandes y vacíos en un solo nodo. Las mallas de navegación dividen el área transitable en polígonos convexos, cada uno de los cuales se puede recorrer en un solo paso. El buscador de ruta L1 agrupa los obstáculos, reduciéndolos a un gráfico de visibilidad, calcula la ruta sobre eso.

2. Un algoritmo que no expande todos los nodos. La búsqueda de punto de salto aprovecha la simetría entre diferentes rutas, expandiendo solo los nodos adyacentes a los obstáculos, mientras que A * expandirá cada nodo a lo largo de la ruta más corta.

Answer 6

Un concepto de alto nivel podría ser encontrar los puntos de inicio y final (por ejemplo, punto (0,0) y punto (10000, 10000) y hacer una estimación preliminar de un camino que va de principio a fin (en este caso sería correr en diagonal todo el camino hacia arriba y hacia la derecha) Luego comience a verificar si puede llegar exitosamente (si hay obstáculos en ese camino o no). Si luego hay programados rutas similares, o alternativamente encuentra dónde falla la ruta y comienza allí e intenta iterar hasta que funcione, puede que no sea el 100% más rápido, pero obtendrás resultados mucho mejores que encontrar todas las formas posibles. entonces deduciendo el camino más corto de eso.

Implementación

• Método para encontrar la ruta más corta inicial
• Corre para ver si funciona.
  • Si falla, entonces intente una ruta similar o comience desde la falla

Answer 7

Entonces, aunque podría haber n^4 rutas más cortas en un cuadrado n por n mapa. almacenar todas las rutas no requiere necesariamente espacio O(n^4) . La idea es que si se tienen en cuenta dos ubicaciones objetivo diferentes en el mapa y sus árboles de ruta más cortos, y cuanto más cerca estén esos puntos del mapa, más elementos comunes tendrán los árboles de ruta más corta. Esto es especialmente cierto cuando se usa un mapa plano como una cuadrícula con obstáculos.

Por lo tanto, la idea es almacenar solo algunos árboles de ruta más cortos completos para un conjunto pequeño de ubicaciones objetivo (incluso puede ser solo una ubicación objetivo). Para el resto de las ubicaciones de destino, solo se almacena la diferencia de su árbol de ruta más corto a uno de los árboles de ruta más cortos previamente almacenados.

Luego, el algoritmo para encontrar la ruta más corta desde una ubicación a un destino es cargar un árbol de ruta más corto completamente almacenado y luego aplicarle algunas diferencias para obtener el árbol de ruta más corto de la ubicación de destino. Entonces, solo la posición actual del jugador debe encontrarse en el árbol de la ruta más corta, que es O(n^2) complejidad.

No tengo datos concretos sobre cuánto espacio de almacenamiento se necesita para almacenar los árboles de ruta más cortos y sus diferencias, pero esto podría estar en el rango O(n^2 log(n^2)) . La carga de uno y la aplicación de las diferencias solo pueden tener una complejidad de tiempo de O(n^2) .

El árbol de ruta más corto para una ubicación de destino representa la ruta más corta desde cada ubicación en el mapa hasta la ubicación de destino.

Esta solución también puede mantener el árbol de ruta más corto usado en la memoria y aplicar diffs según sea necesario para obtener el nuevo árbol de ruta más corto a utilizar. Entonces, la complejidad de obtener el árbol de la ruta más corta no está limitada por el tamaño del mapa, sino solo por el tamaño de las diferencias que se aplicarán. Este escenario podría funcionar bien para juegos como el Sagrado original o el Diablo.