¿Utilizando A * y aún evitando colisiones?

Question

Estoy diseñando un juego de defensa de la torre, y para eso estoy usando el algoritmo de determinación de ruta A * para llegar a mi destino desde mis áreas de spawn.

El problema aquí es que todas las unidades se acumulan, lo que no se ve visualmente bien. ¿Existe alguna forma de que pueda hacer que se agrupen de alguna manera, y se extiendan más si no hay suficiente espacio?

El algoritmo funciona para que todas las unidades muevan una sola ficha a la vez.

Answer 1

Puede usar el comportamiento de bandadas para que sigan la misma ruta general pero no se unan entre sí. Hay un ejemplo de XNA proporcionado por MS aquí: http://xbox.create.msdn.com/en-US/education/catalog/sample/flocking

Answer 2

Si agrega una penalización para las losetas ocupadas por muchas enredaderas, probablemente las espaciará mientras haya espacio para que se muevan.

Sin embargo, no sería necesario ser el camino más rápido. También podría hacerlos más impredecibles, lo que dependiendo de la dificultad del objetivo podría ser bueno o malo :)

Answer 3

¿Está volviendo a calcular el camino más corto en cada paso del tiempo?

En caso afirmativo: simplemente, otorgue a un mosaico la cantidad máxima de unidades que puedan soportarlo. Si está lleno, no más unidades pueden ocupar este mosaico.

En caso negativo, calcule la ruta de cada unidad una después de la otra. Dale a cada ficha un vector que diga a las otras unidades (que vendrán después) cuando esta casilla esté ocupada. Pon esta información en tu algoritmo A * Nota: su algoritmo será mucho más lento de esta manera.

Sugiero volver a calcular la ruta más corta en cada paso.

EDIT 1 En realidad, la complejidad del algoritmo es en ambos casos el mismo, sin embargo, me parece que el caso 1 es mucho más fácil de implementar.

Answer 4

Un amigo mío que solía hacer diseño de AI para un famoso juego de disparos en primera persona del que probablemente haya escuchado cuenta una historia sobre cómo su algoritmo de búsqueda de caminos produjo un comportamiento de apariencia falsa. Lanzabas una granada a un grupo de enemigos en un espacio restringido, y todos chocaban entre sí tratando de que todos se pusieran en el camino eficiente hacia la única salida. Parecía tonto y rompió la ilusión.

En lugar de quemar ciclos de procesador valiosos en una mejor ruta, agregaron una heurística tal que si un grupo de enemigos huye y un enemigo choca con otro enemigo dos veces en una sucesión corta, el enemigo deja de intentar huir y en su lugar pato-y-cubre, y luego generalmente es asesinado por la granada como resultado. Es muy satisfactorio para el jugador y se ve mucho más realista.

Quizás haya algo similar que pueda hacer aquí. Si demasiadas unidades terminan dirigiéndose hacia el mismo camino y chocan entre sí, y parece poco realista, ¿hay alguna cosa barata y fácil que pueda hacer para detectar la situación y cambiar la animación?

Answer 5

¿Qué hay de pathfinding iterativo?

1. Ejecute un algoritmo de búsqueda de ruta, ignorando los problemas con la superposición. Esto encontrará el camino más corto.
2. Simula el movimiento de fluencia. Esta simulación debería ejecutarse con movimientos basados ​​en mosaicos para que sea rápida.
3. Seleccione la mitad (violín con esto) de los creeps que están esperando en una línea y por lo tanto no se mueven. Vuelva a ejecutar el algoritmo para esos creeps, pero agregue una penalización de peso adicional en esta posición que estaban esperando.Este peso SÓLO se aplicará a los creeps que tenían el peso extra.
4. Repita los pasos 2-3 hasta que se cumpla alguna condición, prestando atención (jugando con esto) a los pesos adicionales anteriores.

Este algoritmo requerirá el toqueteo para fusionarse completamente en algo útil. Sin embargo, tiene la ventaja de utilizar rutas previamente planificadas, por lo que no tendrá ningún bucle o creeps moviéndose hacia atrás. También le permite ignorar cosas como el tiempo, por lo que es conceptualmente más simple. Pero también probablemente menos eficiente.