Tengo un enemigo jefe que busca caminos y busca al jugador usando el algoritmo A *. Es un entorno bastante complejo, y lo estoy haciendo en Flash, por lo que la búsqueda puede ser un poco lenta cuando se busca a largas distancias. Si el jugador estaba parado, podría buscar solo una vez, pero en este momento estoy buscando en cada cuadro. Esto lleva tanto tiempo que mi framerate está sufriendo.
¿Cuál es la solución habitual a esto? ¿Hay alguna manera de "volver a planificar" A * sin rehacer toda la búsqueda? ¿Debería buscar un poco con menos frecuencia (cada medio segundo o segundo) y aceptar que habrá un poco de imprecisión en el camino?
fuente
Puede usar la detección de proximidad para ejecutar el algoritmo cada pocos fotogramas si la distancia es muy grande (porque en la mayoría de los casos si la distancia es grande, la ruta objetivo no cambiará drásticamente de fotograma a fotograma). Por ejemplo:
Esto supone que hay una distancia donde ejecutar A * cada cuadro tiene un rendimiento que aún es aceptable. En resumen, elegiría tu segunda opción. Especialmente si lo que tienes está funcionando, evitaría volver a implementar algo más si puedo reducir lo que funciona bien. La conclusión es que tendrás que probarlo para ver si funciona para tu juego.
fuente
Realmente no responde a su pregunta exacta, pero ... si está dispuesto a "hacer trampa", puede hacer que el jugador deje "migas de pan" y que el jefe las siga. Si el camino de migas de pan se cruza, siga el más reciente (esto hace que el jefe evite bucles y otros caminos que pueden ser demasiado largos, sin mencionar que no sigue el camino exacto del jugador)
Esto funcionaría bien si el jefe es algún tipo de animal con un buen sentido del olfato. Esto funcionaría mucho como seguir el aroma del jugador :)
fuente
Su caso es más o menos lo que HPA * se inventó para abordar. Sin embargo, si parece excesivo, tendería a pensar que la búsqueda de caminos cada medio segundo debería funcionar bastante bien.
fuente
Si es un entorno estático, puede calcular previamente la ruta más corta de todos los pares.
fuente
Creé un juego para una competencia de 48 juegos donde un personaje A * sigue al jugador alrededor de un nivel. Como mi implementación de A * era lenta (no podía ejecutarse en cada cuadro), puse el intervalo en un retraso de tres segundos. Esto tuvo el resultado no deseado de permitir que el jugador "engañara" a la IA por unos momentos. Realmente hizo el juego más divertido.
Más tarde, mejoré el rendimiento de la implementación de A * e intenté ejecutarlo en cada cuadro. El juego dejó de ser divertido porque el enemigo siempre buscaría perfectamente al jugador.
Eso fue inesperado y una buena experiencia de aprendizaje.
fuente
A menos que desee (o necesite) usar A *, también puede echar un vistazo a los Comportamientos de dirección . Como no hay una planificación de ruta completa por trama involucrada, debería ser mucho más ligero en el procesamiento.
fuente