Mass astar pathfinding

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

Fuente

2012-04-12 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

Uso Anti-objetos, esta es la única manera de conseguir la búsqueda de caminos barato, que yo sepa: http://www.cs.colorado.edu/~ralex/papers/PDF/OOPSLA06antiobjects.pdf

Anti-objeto, básicamente, significa que en lugar de los robots que tienen ai individual, tendrás un "swarm ai", que está vinculado a tu mapa del juego.

p.s .: Aquí hay otro enlace sobre la búsqueda de caminos en general (posiblemente la mejor referencia en línea disponible): http://theory.stanford.edu/~amitp/GameProgramming/index.html

Fuente

2012-04-12 10:01:55 c69

gracias por el recurso lo echaré un vistazo un poco más tarde. Aunque solo por lo que has dicho, parece que tiene más sentido buscar el mapa completo y quizás establecer una dirección en cada "bloque" que siguen los bots. Hmmm – james

Sólo almacenar en caché el resultado.

Almacene la ruta como el valor en una tabla hash (objeto), otorgue a cada nodo un UUID, concatene los UUID para formar una clave única de la tabla hash e inserte la ruta en ella.

Al recuperar el camino de vuelta de la tabla hash, recorrer el camino, y ver si todavía es válida, si no, volver a calcular e insertar uno nuevo de nuevo.

Hay muchos optimización que pueda hacer :)

como c69 dijo enjambre AI o de la mente colmena vienen a la mente: P

Fuente

2013-10-28 03:54:31 Metalstorm

Respuesta

Cuestiones relacionadas