Rendimiento lento en una implementación A * en un juego de torre de defensa

9

Estoy haciendo un juego de Tower Defense en Flash sin una ruta predefinida.

Aunque mi cuadrícula es 40x40 (¿pequeña?), A * tiene problemas cuando recalcula cada vez. Así que hice mi propia modificación para facilitar el recálculo y el recuento de células tocadas se redujo a alrededor de 900 (al modificar cerca de la raíz). Todavía se congela por un tiempo muy corto, pero detectable, cuando se coloca una nueva torre.

¿Es este un problema de implementación, o 40x40 es demasiado?

Editar:

La estructura de mi código:

  • Todos los datos se guardan en una matriz 2D de celdas.
  • Cada celda contiene su padre en la dirección de la ruta (1-8 en el sentido de las agujas del reloj) y la matriz codificada en bits de sus hijos en la ruta (cada bit representa un hijo).
  • La búsqueda es realizada por A * con la estimación de la distancia euclidiana.
Dani
fuente
Tendrás que ser mucho más específico aquí. No tenemos idea de cómo se ve su código, cómo está estructurado, etc., por lo que no podemos sacar conclusiones sobre lo que lo está haciendo lento.
Sean James
1
Cuando implementé A * por última vez, recuerdo que se ejecutó a través de una cuadrícula de 64x64 en un máximo de 1 ms. Entonces, sí, parece ser un problema con su implementación. Sugiero publicar su código o la esencia de este para que podamos ayudarlo más.
Marc Müller
Mira la edición que agregué
Dani
1
Si 40x40 es demasiado lento, es muy probable que estés haciendo algo muy mal. Publique su código o perfílelo. Alternativamente, escale y vea qué sucede: si una cuadrícula de 80x80 tarda más de cuatro veces más, tiene algo extremadamente roto allí.
ZorbaTHut
¿Puede el título ser un poco más informativo, por favor?
Tenpn

Respuestas:

4

No puedo comentar, pero el primer perfil en Flex, todo lo demás es una conjetura.

Jonathan Fischoff
fuente
¿Como puedo perfilar un proyecto flash en flex?
Dani
Si y no. No creo que cargues el proyecto flash directamente. Creo que es posible que pueda perfilar el swf sin fuente y aún así obtener información de nivel de función. Haría una búsqueda en Google para "perfilar un proyecto flash en flex" o similar. Lo hice y obtuve esto: flexblog.edchipman.ca/… que parece prometedor.
Jonathan Fischoff
Gracias, realmente me ayudó a encontrar la parte problemática (no estaba en el algoritmo, vea el comentario sobre la pregunta)
Dani
13

Supongo que TD es 'Tower Defense'

Creo que A * se está exagerando un poco por esto.

Al comienzo del juego, inunda el área del juego desde los puntos de salida para crear un mapa de movimiento:

 |---------|
 |5|4|3|3|3|
 |5|4|3|2|2|
->5|4|3|2|1->
 |5|4|3|2|2|
 |5|4|3|3|3|
 |---------|

y el movimiento es siempre hacia un cuadrado con un valor más bajo.

Cuando el jugador coloca una torre, actualice cada una de las ocho casillas adyacentes: para cada casilla, establezca su valor de movimiento en uno más que el valor adyacente más bajo. Si el valor cambia, repita el proceso centrado en el cuadrado actualizado. Luego, para verificar que la ruta a la salida no esté bloqueada, asegúrese de que todos los cuadrados estén adyacentes a un cuadrado de menor valor.

Cuando el jugador retira una torre, establece el valor del movimiento en uno más que el cuadrado adyacente más bajo y repite el proceso anterior.

Un enfoque más simple sería volver a hacer el relleno de inundación.

Skizz
fuente
66
Volver a hacer el relleno de inundación es más costoso que hacer A * para un pequeño número de unidades, aproximadamente, la longitud de la placa, al menos en términos algorítmicos (y dado que esto es Flash, las constantes no algorítmicas como el diseño de memoria probablemente puedan ' t ser usado de manera muy efectiva). Sin embargo, este es un muy buen modelo para muchas unidades comunicantes, y se llama difusión colaborativa: scalablegamedesign.cs.colorado.edu/wiki/Collaborative_Diffusion .
@ Joe Wreschnig: wow bonito enlace. He usado esa técnica antes, pero nunca supe cómo se llamaba. Gracias.
Tenpn
@ Joe, mientras haya al menos algunas barreras en el mapa, no creo que esto sea más ineficiente que llamar a A *. Es decir, creo que solo para un mapa abierto, casi sin barreras y con pocas unidades, podría ser peor.
edA-qa mort-ora-y
@edA: Por definición, un relleno de inundación eventualmente debe tocar cada punto accesible en el mapa; A * proporciona límites superiores probados a cuántos puntos debe tocar, que es, como máximo, cada punto accesible en el mapa y, por lo general, mucho menos. El relleno de inundación es un algoritmo más simple para optimizar cosas como el diseño de la memoria, pero como dije, en Flash, eso probablemente no importa.
@ Joe, eso es lo que estoy discutiendo es que incluso con solo un puñado de torres, la A * probablemente tocará casi todos los espacios. Pero para N monstruos solo necesita exceder total_squares / N para ser menos eficiente que el relleno de inundación.
edA-qa mort-ora-y
2

Extraño, pensé que había respondido a esto, pero la respuesta parece haberse ido. Haga que su algoritmo de búsqueda se pueda actualizar en varios pasos, de modo que cuando coloque una torre y reproduzca una animación, pueda hacer un poquito cada fotograma y tendrá entre medio segundo y un segundo para actualizar su A * sin una pausa notable. Es latencia: si no puedes acelerarlo, busca la forma de ocultarlo. Reproducir una animación mientras se coloca una torre sería natural para un juego y es un buen lugar para esconderlo.

Kaj
fuente
Esta es una buena idea en general, pero mala para esta pregunta específica. A * en una cuadrícula tan pequeña debería ser casi instantánea, sin tomar una cantidad significativa de tiempo.
davr
Lo suficientemente justo. Es la única respuesta que podría dar que resolvería el problema sin conocer los detalles de implementación que causarían la desaceleración.
Kaj
0

Para empezar, podría cambiar su matriz a un vector, debería darle algunas mejoras de velocidad. Publique el código y podríamos sugerir más optimizaciones.

Iain
fuente
0

Supongo que su ralentización se debe a que está calculando una ruta para todos los personajes simultáneamente. Calcular un camino para un personaje es rápido, pero si hay dos docenas de personajes en la escena, eso puede empantanarse.

En su lugar, debe distribuir la carga en unos pocos fotogramas. Alterne sus actualizaciones de IA para que diferentes personajes actualicen su camino en diferentes marcos. Sería realmente notable si un personaje no reaccionara hasta un segundo después, pero solo un cuadro no va a causar malas reacciones.

jhocking
fuente
Esto fue respondido hace casi un año, y solo fue rechazado debido al trabajo de edición de Grace. (No tenía nada que ver con demasiados caracteres)
Gracias por hacérmelo saber. No me di cuenta de las fechas.
jhocking