Algoritmo dinámico de ruta para el juego de defensa de torres

Estoy haciendo un Tower Defense y necesito un buen algoritmo de ruta para ello.

He pensado en Dijkstra pero necesito uno que pueda ser dinámico; debe poder actualizarse cuando se elimina o agrega un borde sin un recálculo completo.

Estoy codificando en C # si ayuda.

En general, querrá usar A *, a menos que esté buscando algo muy diferente.

Necesitaba resolver un problema similar: encontrar caminos en una gran cuadrícula tipo laberinto con "costos" y barreras en constante cambio.

La cuestión es que, en el juego de defensa de la torre, el número de entidades que necesitan que se les resuelva el camino suele ser mucho mayor que el número de nodos en el gráfico. A * no es el algoritmo más apropiado para manejar esto, porque necesitará resolverlo nuevamente cada vez que se cambie algo. Bueno, es apropiado si necesita encontrar solo una ruta, pero en mi caso necesitaba poder manejar entidades que pueden aparecer en diferentes ubicaciones y cada una tiene su propia ruta.

El algoritmo de Floyd-Warshall es mucho más apropiado, aunque para mi caso escribí un algoritmo personalizado que cada vez que cambia un nodo, vuelve a calcular el costo para ese nodo de todos sus vecinos, y luego, si los vecinos han cambiado, se invoca recursivamente sobre ellos.

Entonces, al comienzo del juego, simplemente enciendo este algoritmo en todos mis nodos de "objetivo". Luego, cada vez que cambia un solo nodo (por ejemplo, no se puede pasar), simplemente lo enciendo en ese nodo y el cambio se propaga a todos los nodos que se verán afectados, y luego se detiene. Por lo tanto, no es necesario un recálculo global, y el algoritmo es completamente independiente del número de entidades que requerirán la búsqueda de rutas.

Mi algoritmo era básicamente algo como (pseudocódigo):

update_node method in Node class:
    $old <- $my_score
    find $neighbor node among all neighbors such that
        $neighbor.score + distance_to($neighbor) is minimal
    $my_score <- $neighbor.score + distance_to($neighbor)
    $next_node <- $neighbor
    if ($my_score != $old)
        for each $neighbor
            $neighbor.update_node()

Con el puntaje inicial dependiendo de si el nodo es un objetivo o algún tipo de barrera.

El algoritmo de ruta que utilicé en mi TD era anterior a la ruta A * normal debido a la cantidad de entidades que tenía en el juego. En lugar de enrutar desde la portería a los malos, me dirigí desde la portería a cada cuadro vacío en el tablero.

Esto no toma mucho tiempo, solo sigue iterando el tablero hasta que haya encontrado sus "costos", y proporciona una buena respuesta para las rutas bloqueadas (si las está haciendo). El uso del algoritmo de Floyd es rápido y amigable con la memoria caché en comparación con A *, ya que no está haciendo búsquedas dependientes de datos, solo está cargando y operando datos en flujos.

Comience con su tablero configurado en costo infinito, luego establezca el cuadrado del objetivo en costo cero, luego repita el control del tablero para ver si una celda vecina cuesta menos que el costo actual más el costo de viaje. El costo de viaje es donde pones tu heurística (en mi caso, el costo de viajar en diagonal era infinito, pero el costo de viajar a través de una torre era alto, por lo que se les permitió comer a través de torres, pero no a menos que no tuvieran elección)

Una vez que tenga su grilla de costos, puede construir rápidamente una grilla de "flujo" a partir de eso probando el gradiente de costo más pronunciado en las celdas. Esto funciona muy bien para grandes cantidades de tipos malos porque ninguno de ellos tiene que encontrar el camino, solo siguen las señales virtuales.

Otro beneficio es que de esta manera solo tienes que ejecutar esta tarea cada vez que ajustas las obstrucciones (o en mi juego, cuando un arrastramiento se come a través de una de tus torres). No cada vez que un creep / mob ingresa al campo (lo que con miles de mobs y decenas por segundo habría sido un gran dolor de cabeza).

Pathfinding es rápido, y en algo del tamaño de un juego de defensa de torre normal, no tendrás problemas para ejecutar un pase A * o Dijkstra completo cada vez que algo cambie. Estamos hablando mucho menos de un milisegundo para una actualización completa. Cualquier tipo de camino adaptativo termina horriblemente complicado. Simplemente hazlo de manera simple, a menos que estés haciendo la cuadrícula de defensa de torre más grande del mundo.

¿Cómo funciona A * pathfinding? podría ser un buen lugar para comenzar :-)

Esto puede ser excesivo para su solución, pero piense en enrutar hacia atrás en lugar de hacia adelante.

En un juego de TD, los enemigos generalmente intentan llegar a un objetivo específico. Dirígete hacia atrás desde ese objetivo hasta el primer enemigo, luego almacena en caché ese camino. En la generación de rutas para enemigos posteriores, usa la primera ruta como punto de partida, y así sucesivamente. Si tiene múltiples puntos de entrada de enemigos o múltiples objetivos, tenga un rango de caminos pre-almacenados en caché para comenzar.

La búsqueda de ruta en el punto de referencia probablemente sería la mejor para un juego de td, porque generalmente, en función del nivel, el ai sigue una ruta directa. Básicamente, establece sus nodos o puntos de referencia, luego tiene el punto "ai" hacia el waypoiny y camina hacia él, una vez que se acerca lo suficiente para que vaya al siguiente punto de referencia, enfréntelo y muévase hacia él.

Como alguien le preguntó, usted se dirige a entornos que cambian dinámicamente al volver a calcular la ruta cada vez que el jugador coloca o elimina una torre, y mientras tanto, simplemente almacena esa ruta en la memoria. El entorno no cambia en cada cuadro.

Tenga en cuenta que algunos juegos de TD tienen una ruta establecida y no le permiten colocar torres en ella, por lo que resuelven la búsqueda de ruta de la manera fácil: codificando una ruta y no permitiéndole bloquearla :)

Una solución simple es hacer trampa.

Diseñe el mapa de antemano para asegurarse de que no haya callejones sin salida. Luego, en cada intersección, agregue un disparador que haga que el personaje elija una ruta (ejemplo: siempre gire a la izquierda, siempre gire a la derecha o al azar).