Estoy tratando de crear un juego de tower defense en Javascript.Mass astar pathfinding
Todo va bien, aparte de la búsqueda de caminos ..
estoy usando el código Astar de este sitio web: http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript que utiliza una pila binaria (que creo que es bastante óptimo)
El problema i estoy teniendo es que quiero permitir que la gente bloquee el camino de los "atacantes". Esto significa que cada "atacante" necesita poder encontrar su camino hacia la salida por sí mismo (ya que alguien podría cortar un solo "atacante" y necesitaría encontrar su propio camino hacia la salida). Ahora, 5/6 atacantes pueden encontrar una ruta en cualquier momento sin problemas. Pero dicen que el camino está bloqueado para más de 10 atacantes, los 10 tendrán que disparar su script de pathfinding al mismo tiempo, lo que simplemente reduce el FPS a aproximadamente 1/2 por segundo.
Esto debe ser un problema común para cualquiera que tenga muchas entidades buscando caminos en cualquier momento, así que imagino que debe haber una forma mejor que mi enfoque.
Así que mi pregunta es: ¿Cuál es la mejor manera de implementar el algoritmo de ruta masiva para múltiples "bots" de la manera más eficiente.
Gracias,
James
parece que el 'findGraphNode' en ese código se lleva en tiempo lineal, mientras que debería estar tomando un tiempo constante (con una tabla hash), por lo que la implementación está lejos de ser óptima. –
Voy a ver si puedo acelerarlo un poco. Pero creo que incluso con una búsqueda de ruta más eficiente, seguiré con la velocidad de fotogramas lenta si intento localizar los bots. Estoy empezando a pensar que mi mejor opción es, en realidad, encontrar todo el mapa una vez por fotograma y luego establecer una dirección en cada bloque aceptable para que los bots sigan ... – james
@james si esto se parece a la mayoría de las defensas de la torre, con aproximadamente una pantalla de mapa y sin colisiones complejas (es decir, los bots no colisionan entre sí u otros objetos en movimiento, o maneja esto por separado), entonces sí, creo que sería mejor calcular las rutas para todo el mapa.De hecho, probablemente ni siquiera tenga que volver a calcular todo el mapa en cada cuadro. Si tiene cuidado al construir un algoritmo, debe poder determinar qué nodos se ven afectados por un cambio de usuario y volver a calcular solo 'ascendente' desde esos nodos. ¡Suena interesante! – Tim