¿Cómo puedo hacer que A * termine más rápido cuando el destino es intransitable?

31

Estoy creando un juego 2D simple basado en mosaicos, que utiliza el algoritmo de búsqueda de rutas A * ("Una estrella"). Tengo todo funcionando bien, pero tengo un problema de rendimiento con la búsqueda. En pocas palabras, cuando hago clic en un mosaico intransitable, el algoritmo aparentemente recorre todo el mapa para encontrar una ruta al mosaico intransitable, incluso si estoy parado al lado.

¿Cómo puedo evitar esto? Supongo que podría reducir la búsqueda de ruta en el área de la pantalla, pero ¿tal vez me falta algo obvio aquí?

usuario2499946
fuente
2
¿Sabes qué mosaicos son intransitables o simplemente lo sabes como resultado del algoritmo AStar?
user000user
¿Cómo está almacenando su gráfico de navegación?
Anko
Si está almacenando nodos recorridos en listas, es posible que desee usar montones binarios para mejorar la velocidad.
ChrisC
Si es simplemente demasiado lento, tengo una serie de optimizaciones para sugerir, ¿o está tratando de evitar las búsquedas por completo?
Steven
1
Esta pregunta probablemente habría sido más adecuada para la informática .
Raphael

Respuestas:

45

Algunas ideas para evitar búsquedas que resultan en rutas fallidas por completo:

ID de la isla

Una de las formas más económicas de finalizar eficazmente las búsquedas A * más rápidas es no realizar ninguna búsqueda. Si las áreas son realmente impasibles por todos los agentes, las inundaciones llenan cada área con una identificación de isla única en la carga (o en la tubería). Al buscar rutas, verifique si la ID de la isla del origen de la ruta coincide con la ID de la isla del destino. Si no coinciden, no tiene sentido hacer la búsqueda: los dos puntos están en islas distintas y no conectadas. Esto solo ayuda si hay nodos verdaderamente intransitables para todos los agentes.

Límite superior

Limito el límite superior del número máximo de nodos que se pueden buscar. Esto ayuda a que las búsquedas intransitables se ejecuten para siempre, pero significa que se pueden perder algunas búsquedas pasables que son muy largas. Este número necesita ser ajustado, y realmente no resuelve el problema, pero mitiga los costos asociados con búsquedas largas.

Si lo que está encontrando es que está tardando demasiado , las siguientes técnicas son útiles:

Hágalo asíncrono y limite las iteraciones

Deje que la búsqueda se ejecute en un hilo separado o un poco en cada cuadro para que el juego no se detenga esperando la búsqueda. Visualice la animación del personaje rascándose la cabeza o estampando los pies, o lo que sea apropiado mientras espera que finalice la búsqueda. Para hacer esto de manera efectiva, mantendría el estado de la búsqueda como un objeto separado y permitiría la existencia de múltiples estados. Cuando se solicita una ruta, tome un objeto de estado libre y agréguelo a la cola de objetos de estado activo. En su actualización de búsqueda de ruta, extraiga el elemento activo del frente de la cola y ejecute A * hasta que A. se complete o B. se ejecute algún límite de iteraciones. Si está completo, vuelva a colocar el objeto de estado en la lista de objetos de estado libre. Si no se ha completado, colóquelo al final de las 'búsquedas activas' y pase a la siguiente.

Elija las estructuras de datos correctas

Asegúrese de usar las estructuras de datos correctas. Así es como funciona mi StateObject. Todos mis nodos están asignados previamente a un número finito, digamos 1024 o 2048, por razones de rendimiento. Utilizo un grupo de nodos que acelera la asignación de nodos y también me permite almacenar índices en lugar de punteros en mis estructuras de datos que son u16s (o u8 si tengo un máximo de 255 nodos, lo que hago en algunos juegos). Para mi pathfinding utilizo una cola de prioridad para la lista abierta, almacenando punteros a objetos Node. Se implementa como un montón binario, y clasifico los valores de coma flotante como enteros, ya que siempre son positivos y mi plataforma tiene comparaciones lentas de coma flotante. Utilizo una tabla hash para mi mapa cerrado para realizar un seguimiento de los nodos que he visitado. Almacena NodeIDs, no Nodes, para guardar en tamaños de caché.

Caché lo que puedas

Cuando visite un nodo por primera vez y calcule la distancia al destino, guarde en caché el nodo almacenado en el objeto de estado. Si vuelve a visitar el nodo, use el resultado en caché en lugar de calcularlo nuevamente. En mi caso, ayuda no tener que hacer una raíz cuadrada en los nodos revisitados. Puede encontrar que hay otros valores que puede calcular previamente y almacenar en caché.

Otras áreas que podría investigar: utilice la búsqueda de ruta bidireccional para buscar desde cualquier extremo. No he hecho esto, pero como otros han señalado, esto podría ayudar, pero no sin sus advertencias. La otra cosa en mi lista para probar es la búsqueda de rutas jerárquicas o la búsqueda de rutas en clúster. Hay una descripción interesante en la documentación de HavokAI Aquí que describe su concepto de agrupación, que es diferente de las implementaciones de HPA * descritas aquí .

Buena suerte y cuéntanos qué encuentras.

Steven
fuente
Si hay diferentes agentes con diferentes reglas, pero no demasiados, esto puede generalizarse de manera bastante eficiente mediante el uso de un vector de ID, uno por clase de agente.
MSalters
44
+1 Para reconocer que el problema es probablemente áreas excluidas (no solo mosaicos impasibles), y que este tipo de problema se puede resolver más fácilmente con los primeros cálculos del tiempo de carga.
Slipp D. Thompson
Relleno de inundación o BFS en cada área.
wolfdawn
Las ID de isla no necesitan ser estáticas. Existe un algoritmo simple que sería adecuado en caso de que sea necesario unir dos islas separadas, pero no puede dividir una isla después. Las páginas 8 a 20 en estas diapositivas explican ese algoritmo particular: cs.columbia.edu/~bert/courses/3137/Lecture22.pdf
kasperd
@kasperd, por supuesto, no hay nada que impida que los ID de las islas se vuelvan a calcular, se fusionen en tiempo de ejecución. El punto es que los identificadores de la isla le permiten confirmar si existe una ruta entre dos nodos rápidamente sin hacer una búsqueda de astar.
Steven
26

AStar es un algoritmo de planificación completo , lo que significa que si existe una ruta al nodo, AStar está garantizado de encontrarlo. En consecuencia, debe verificar cada ruta fuera del nodo de inicio antes de que pueda decidir que el nodo objetivo es inalcanzable. Esto es muy indeseable cuando tienes demasiados nodos.

Formas de mitigar esto:

  • Si sabe a priori que un nodo es inalcanzable (por ejemplo, no tiene vecinos o está marcado UnPassable), regrese No Pathsin llamar a AStar.

  • Limite el número de nodos que AStar expandirá antes de terminar. Verifique el conjunto abierto. Si alguna vez se vuelve demasiado grande, termina y regresa No Path. Sin embargo, esto limitará la integridad de AStar; por lo que solo puede planificar rutas de una longitud máxima.

  • Limite el tiempo que AStar tarda en encontrar un camino. Si se le acaba el tiempo, salga y regrese No Path. Esto limita la integridad como la estrategia anterior, pero escala con la velocidad de la computadora. Tenga en cuenta que para muchos juegos esto no es deseable, porque los jugadores con computadoras más rápidas o más lentas experimentarán el juego de manera diferente.

mklingen
fuente
13
Me gustaría señalar que cambiar la mecánica de su juego dependiendo de la velocidad de la CPU (sí, la búsqueda de rutas es una mecánica del juego) puede ser una mala idea porque puede hacer que el juego sea bastante impredecible y, en algunos casos, incluso imposible de jugar. en computadoras dentro de 10 años. Por lo tanto, preferiría limitar A * limitando el conjunto abierto que por tiempo de CPU.
Philipp
@Philipp. Modificó la respuesta para reflejar esto.
mklingen
1
Tenga en cuenta que puede determinar (razonablemente eficiente, O (nodos)) para un gráfico dado la distancia máxima entre dos nodos. Este es el problema de la ruta más larga y le proporciona un límite superior correcto para la cantidad de nodos que debe verificar.
MSalters
2
@MSalters ¿Cómo se hace esto en O (n)? ¿Y qué es 'razonablemente eficiente'? Si esto es solo para pares de nodos, ¿no estás simplemente duplicando el trabajo?
Steven
Según Wikipedia, desafortunadamente, el problema del camino más largo es NP-hard.
Desty
21
  1. Ejecute una búsqueda doble A * desde el nodo de destino en reversa también al mismo tiempo en el mismo bucle y cancele ambas búsquedas tan pronto como una se encuentre sin solución

Si el objetivo solo tiene 6 fichas accesibles a su alrededor y el origen tiene 1002 fichas accesibles, la búsqueda se detendrá en 6 iteraciones (duales).

Tan pronto como una búsqueda encuentre los nodos visitados de la otra, también puede limitar el alcance de búsqueda a los nodos visitados de la otra y terminar más rápido.

Stephane Hockenhull
fuente
2
Implementar una búsqueda de estrella A bidireccional es más de lo que implica su declaración, incluida la verificación de que la heurística sigue siendo admisible en estas circunstancias. (Enlaces: homepages.dcc.ufmg.br/~chaimo/public/ENIA11.pdf )
Pieter Geerkens el
44
@StephaneHockenhull: Habiendo implementado un A- * bidireccional en un mapa del terreno con costos asimétricos, le aseguro que ignorar el bla bla bla resultará en una selección de ruta defectuosa y cálculos de costos incorrectos.
Pieter Geerkens
1
@MooingDuck: el número total de nodos no ha cambiado, y cada nodo solo se visitará una vez, por lo que el peor caso de división de mapa exactamente por la mitad es idéntico a A- * unidireccional.
Pieter Geerkens
1
@PieterGeerkens: en el clásico A *, solo la mitad de los nodos son accesibles y, por lo tanto, visitados. Si el mapa se divide exactamente por la mitad, cuando busca bidireccionalmente, toca (casi) cada nodo. Sin embargo
Mooing Duck el
1
@MooingDuck: hablé mal; los peores casos son gráficos diferentes, pero tienen el mismo comportamiento: el peor caso para unidireccional es un nodo objetivo completamente aislado, que requiere que se visiten todos los nodos.
Pieter Geerkens
12

Asumiendo que el problema es que el destino es inalcanzable. Y que la malla de navegación no es dinámica. La forma más fácil de hacer esto es tener un gráfico de navegación mucho más disperso (lo suficientemente escaso como para que un recorrido completo sea relativamente rápido) y solo use el gráfico detallado si es posible la ruta.

Trueno clásico
fuente
66
Esto es bueno. Al agrupar los mosaicos en "regiones" y comprobar primero si la región en la que se encuentra su mosaico se puede conectar a la región en la que se encuentra el otro mosaico, puede tirar los negativos mucho más rápido.
Konerak
2
Correcto - generalmente cae bajo HPA *
Steven
@ Steven Gracias Estaba seguro de que no fui la primera persona en pensar en este enfoque, pero no sabía cómo se llamaba. Hace que aprovechar la investigación preexistente sea mucho más fácil.
ClassicThunder
3

Usa múltiples algoritmos con diferentes características

A * tiene algunas características excelentes. En particular, siempre encuentra el camino más corto, si existe. Desafortunadamente, también ha encontrado algunas malas características. En este caso, debe buscar exhaustivamente todas las rutas posibles antes de admitir que no existe una solución.

El "defecto" que está descubriendo en A * es que desconoce la topología. Es posible que tenga un mundo 2-D, pero no lo sabe. Por lo que sabe, en el rincón más alejado de su mundo hay una escalera que lo lleva justo debajo del mundo a su destino.

Considere crear un segundo algoritmo que conozca la topología. Como primer paso, puede llenar el mundo con "nodos" cada 10 o 100 espacios, y luego mantener un gráfico de conectividad entre estos nodos. Este algoritmo encontraría nodos accesibles al inicio y al final, e intentaría encontrar un camino entre ellos en el gráfico, si existe.

Una manera fácil de hacer esto sería asignar cada mosaico a un nodo. Es trivial mostrar que solo necesita asignar un nodo a cada mosaico (nunca puede tener acceso a dos nodos que no estén conectados en el gráfico). Luego, los bordes del gráfico se definen en cualquier lugar donde dos fichas con diferentes nodos son adyacentes.

Este gráfico tiene una desventaja: no encuentra la ruta óptima. Simplemente encuentra un camino. Sin embargo, ahora le ha demostrado que A * puede encontrar una ruta óptima.

También proporciona una heurística para mejorar sus subestimaciones necesarias para que funcione A *, porque ahora sabe más sobre su paisaje. Es menos probable que tenga que explorar completamente un callejón sin salida antes de descubrir que necesita retroceder para seguir adelante.

Cort Ammon - Restablece a Monica
fuente
Tengo razones para creer que algoritmos como los de Google Maps funcionan de manera similar (aunque más avanzada).
Cort Ammon - Restablece a Mónica el
Incorrecto. A * es muy consciente de la topología, a través de la elección de heurística admisible.
MSalters
Re Google, en mi trabajo anterior analizamos el rendimiento de Google Maps y descubrimos que no podía haber sido A *. Creemos que usan ArcFlags u otros algoritmos similares que dependen del preprocesamiento de mapas.
MSalters
@MSalters: Esa es una línea fina interesante para dibujar. Sostengo que A * desconoce la topología porque solo se refiere a los vecinos más cercanos. Yo diría que es más justo decir que el algoritmo que genera la heurística admisible conoce la topología, en lugar de A * en sí. Considere un caso donde hay un diamante. A * toma un camino por un momento, antes de retroceder para probar el otro lado del diamante. No hay forma de notificar a A * que la única "salida" de esa rama es a través de un nodo ya visitado (guardando el cálculo) con la heurística.
Cort Ammon - Restablece a Mónica el
1
No puedo hablar por Google Maps, pero Bing Map usa una estrella A bidireccional paralela con puntos de referencia y desigualdad de triángulos (ALT), con distancias precalculadas desde (y hasta) un pequeño número de puntos de referencia y cada nodo.
Pieter Geerkens
2

Algunas ideas más además de las respuestas anteriores:

  1. Resultados de la caché de la búsqueda A *. Guarde los datos de ruta de la celda A a la celda B y reutilícelos si es posible. Esto es más aplicable en mapas estáticos y tendrá que trabajar más con mapas dinámicos.

  2. Caché a los vecinos de cada celda. La implementación de A * necesita expandir cada nodo y agregar sus vecinos al conjunto abierto para buscar. Si estos vecinos se calculan cada vez en lugar de almacenarse en caché, podría ralentizar drásticamente la búsqueda. Y si aún no lo ha hecho, use una cola de prioridad para A *.

usuario55564
fuente
1

Si su mapa es estático, puede hacer que cada sección separada tenga su propio código y verifique esto primero antes de ejecutar A *. Esto puede hacerse al crear el mapa o incluso codificarse en el mapa.

Los mosaicos intransitables deben tener una bandera y, al moverse a un mosaico como ese, puede optar por no ejecutar A * o elegir un mosaico al lado que sea accesible.

Si tienes mapas dinámicos que cambian con frecuencia, no tienes suerte. Debe tomar su decisión de detener su algoritmo antes de completarlo o hacer que las verificaciones en las secciones se cierren frecuentemente.

Madmenyo
fuente
Esto es exactamente lo que estaba sugiriendo con una identificación de área en mi respuesta.
Steven
También podría reducir la cantidad de CPU / tiempo utilizado si su mapa es dinámico, pero no cambia con frecuencia. Es decir, podría volver a calcular las ID de área cada vez que se desbloquea o bloquea una puerta cerrada. Como eso generalmente ocurre en respuesta a las acciones de un jugador, al menos excluiría las áreas bloqueadas de una mazmorra.
uliwitness
1

¿Cómo puedo hacer que A * concluya más rápidamente que un nodo es intransitable?

Perfile su Node.IsPassable() función, descubra las partes más lentas, agilícelas.

Al decidir si un nodo es pasable, coloque las situaciones más probables en la parte superior, de modo que la mayoría de las veces la función regrese de inmediato sin molestarse en verificar las posibilidades más oscuras.

Pero esto es para acelerar la comprobación de un solo nodo. Puede realizar un perfil para ver cuánto tiempo se dedica a consultar nodos, pero parece que su problema es que se están verificando demasiados nodos.

cuando hago clic en un mosaico intransitable, el algoritmo aparentemente recorre todo el mapa para encontrar una ruta al mosaico intransitable

Si el mosaico de destino en sí es intransitable, el algoritmo no debería verificar ningún mosaico en absoluto. Antes incluso de comenzar a buscar rutas, debe consultar el mosaico de destino para verificar si es posible y, si no, devolver un resultado sin ruta.

Si quiere decir que el destino en sí es transitable, pero está rodeado de mosaicos intransitables, de modo que no hay camino, entonces es normal que A * verifique todo el mapa. ¿De qué otra manera sabría que no hay camino?

Si este es el caso, puede acelerarlo haciendo una búsqueda bidireccional, de esa manera la búsqueda que comienza desde el destino puede encontrar rápidamente que no hay ruta y detener la búsqueda. Vea este ejemplo , rodee el destino con muros y compare la dirección bidireccional frente a la única.

Superbest
fuente
0

Haz la búsqueda del camino hacia atrás.

Si solo su mapa no tiene grandes áreas continuas de mosaicos inalcanzables, esto funcionará. En lugar de buscar en todo el mapa accesible, la búsqueda de ruta solo buscará en el área inalcanzable cerrada.

aaaaaaaaaaaa
fuente
Esto es aún más lento si las fichas inalcanzables superan en número a las fichas alcanzables
Mooing Duck
1
@MooingDuck The fichas inaccesibles conectadas que quieres decir. Esta es una solución que funciona con prácticamente cualquier diseño de mapa cuerdo, y es muy fácil de implementar. No voy a sugerir nada más elegante sin un mejor conocimiento del problema exacto, como cómo la implementación de A * puede ser tan lenta que visitar todos los mosaicos es realmente un problema.
aaaaaaaaaaaa
0

Si las áreas que el jugador está conectado (sin teletransportes, etc.) y las áreas inalcanzables generalmente no están muy bien conectadas, simplemente puede hacer la A * comenzando desde el nodo al que desea llegar. De esa manera, aún puede encontrar cualquier ruta posible hacia el destino y A * dejará de buscar rápidamente áreas inalcanzables.

ent
fuente
El punto era ser más rápido que el A * normal.
Heckel
0

Cuando hago clic en un mosaico intransitable , el algoritmo aparentemente recorre todo el mapa para encontrar una ruta al mosaico intransitable, incluso si estoy parado al lado.

Otras respuestas son geniales, pero tengo que señalar lo obvio: no debe ejecutar la búsqueda de ruta a una ficha infranqueable en absoluto.

Esto debería ser una salida temprana del algo:

if not IsPassable(A) or not IsPasable(B) then
    return('NoWayExists');
Kromster dice que apoya a Mónica
fuente
0

Para verificar la distancia más larga en un gráfico entre dos nodos:

(suponiendo que todos los bordes tengan el mismo peso)

  1. Ejecute BFS desde cualquier vértice v .
  2. Use los resultados para seleccionar un vértice más alejado v, lo llamaremosd .
  3. Ejecute BFS desde u .
  4. Encuentra el vértice más alejado u, lo llamaremosw .
  5. La distancia entre uy wes la distancia más larga en el gráfico.

Prueba:

                D1                            D2
(v)---------------------------r_1-----------------------------(u)
                               |
                            R  | (note it might be that r1=r2)
                D3             |              D4
(x)---------------------------r_2-----------------------------(y)
  • Digamos la distancia entre yyx es mayor!
  • Entonces de acuerdo a esto D2 + R < D3
  • Luego D2 < R + D3
  • Entonces la distancia entre vy xes mayor que la de vyu ?
  • Entonces uno habría sido elegido en la primera fase.

Crédito al prof. Shlomi Rubinstein

Si está utilizando aristas ponderadas, puede lograr lo mismo en tiempo polinómico ejecutando Dijkstra en lugar de BFS para encontrar el vértice más alejado.

Tenga en cuenta que estoy asumiendo que es un gráfico conectado. También estoy asumiendo que no está dirigido.


A * no es realmente útil para un simple juego basado en fichas 2d porque si entiendo correctamente, suponiendo que las criaturas se mueven en 4 direcciones, BFS logrará los mismos resultados. Incluso si las criaturas pueden moverse en 8 direcciones, el BFS perezoso que prefiere nodos más cercanos al objetivo seguirá obteniendo los mismos resultados. A * es una modificación Dijkstra que es mucho más costosa desde el punto de vista computacional que usar BFS.

BFS = O (| V |) supuestamente O (| V | + | E |) pero no realmente en el caso de un mapa de arriba hacia abajo. A * = O (| V | log | V |)

Si tenemos un mapa con solo 32 x 32 mosaicos, BFS costará como máximo 1024 y un A * verdadero podría costarle la friolera de 10,000. Esta es la diferencia entre 0.5 segundos y 5 segundos, posiblemente más si tiene en cuenta el caché. Por lo tanto, asegúrese de que su A * se comporte como un BFS perezoso que prefiera mosaicos que estén más cerca del objetivo deseado.

A * es útil para los mapas de navegación donde el costo de los bordes es importante en el proceso de toma de decisiones. En un juego simple basado en fichas, el costo de los bordes probablemente no sea una consideración importante. Si es así, (diferentes fichas cuestan de manera diferente), puedes ejecutar una versión modificada de BFS que posponga y penalice las rutas que pasan a través de las fichas que ralentizan al personaje.

Entonces sí BFS> A * en muchos casos cuando se trata de mosaicos.

Wolfdawn
fuente
No estoy seguro de entender esta parte "Si tenemos un mapa con solo 32 x 32 mosaicos, BFS costará como máximo 1024 y un verdadero A * podría costarle la friolera de 10,000" ¿Puede explicar cómo llegó a los 10k número por favor?
Kromster dice que apoya a Mónica el
¿Qué quiere decir exactamente con "BFS perezoso que prefiere nodos más cercanos al objetivo"? ¿Te refieres a Dijkstra, BFS simple o uno con una heurística (bueno, has recreado A * aquí, o cómo seleccionas el siguiente mejor nodo de un conjunto abierto)? Eso log|V|en la complejidad de A * realmente proviene de mantener ese conjunto abierto, o el tamaño de la franja, y para los mapas de cuadrícula es extremadamente pequeño, sobre log (sqrt (| V |)) usando su notación. El registro | V | solo aparece en gráficos hiperconectados. Este es un ejemplo donde la aplicación ingenua de la complejidad del peor de los casos da una conclusión incorrecta.
congusbongus
@congusbongus Esto es exactamente lo que quiero decir. No utilice una implementación vainilla de A *
wolfdawn
@KromStern Suponiendo que utiliza la implementación de A * de vainilla para un juego basado en mosaicos, obtiene V * logV complejidad, V es el número de mosaicos, para una cuadrícula de 32 por 32 es 1024. logV, siendo aproximadamente el número de bits necesario para representar 1024, que es 10. Así que terminas corriendo por más tiempo innecesariamente. Por supuesto, si se especializa en la implementación para aprovechar el hecho de que se está ejecutando en una cuadrícula de mosaicos, superará esta limitación, que es exactamente a lo que me refería
wolfdawn el