Encuentra eficientemente a muchos enemigos en bandada alrededor de obstáculos

Estoy trabajando para tratar de mejorar la búsqueda de caminos para los enemigos de mi juego. En este momento, básicamente se mueven constantemente hacia la posición exacta del jugador calculando el ángulo entre ellos y los jugadores y moviéndose en esa dirección. También tengo un algoritmo de congregación que evita que los enemigos se apilen uno encima del otro, por lo que se formarán en grupos en lugar de cortarse entre sí.

Sin embargo, ahora que he agregado un mapa basado en mosaicos, necesito que los enemigos también puedan sortear obstáculos y muros, por ejemplo. Inicialmente intenté agregar un valor de separación a las baldosas "no transitables" para que el algoritmo de flocado considerara las paredes y los obstáculos como objetos para alejarse. Todavía tengo que determinar si esto es factible o no porque mi prueba inicial mostró que los enemigos golpean un "muro" invisible donde no hay baldosas no transitables, pero por alguna razón, lo golpean y comienzan a salir.

Me preguntaba si sería demasiado pesado el rendimiento para calcular una ruta al jugador usando A * y luego usar el algoritmo de flocado para evitar la aglomeración. Originalmente, mi juego iba a ser un juego de disparos basado en olas, pero en su lugar decidí hacerlo a nivel de la línea de Hotline Miami, por lo que es probable que tenga menos enemigos, con la horda ocasional, y solo haga ellos más fuertes

¿Es esta una solución viable? Estoy usando Java con Slick2D como mi motor de juego. ¿O hay una mejor solución / algoritmo que aborde estos dos problemas?

Esto suena como un caso de uso para los campos de flujo.

En esta técnica, realiza una única consulta de búsqueda de ruta hacia afuera desde su (s) objeto (s) de jugador, marcando cada celda que encuentra con la celda desde la que llegó.

Si todas sus fichas / bordes tienen el mismo costo transversal, entonces puede usar una búsqueda simple de amplitud para esto. De lo contrario, el algoritmo de Dijkstra (como A * sin objetivo / heurístico) funciona.

Esto crea un campo de flujo: una tabla de búsqueda que asocia cada celda con el siguiente paso hacia el objeto jugador más cercano desde esa posición.

Ahora tus enemigos pueden buscar su posición actual en el campo de flujo para encontrar el siguiente paso en su camino más corto para evitar obstáculos al objeto jugador más cercano, sin que cada uno haga su propia consulta de búsqueda de camino.

Esto escala mejor y mejor cuantos más enemigos tengas en tu rebaño. Para un solo enemigo, es más costoso que A * porque busca en todo el mapa (aunque puede salir temprano una vez que haya alcanzado a todos los agentes de búsqueda de caminos). Pero a medida que agrega más enemigos, pueden compartir cada vez más el costo de encontrar rutas al calcular segmentos de ruta compartidos una vez en lugar de una y otra vez. También obtiene una ventaja del hecho de que los BFS / Dijkdtra son más simples que A *, y generalmente son más baratos de evaluar por celda inspeccionada.

Exactamente dónde llega el punto de equilibrio, desde A * individual que es más barato, hasta A * con la memorización más barata (donde reutiliza algunos de los resultados para una consulta de búsqueda de ruta anterior para acelerar el siguiente), para que los campos fluyan más barato, dependerá de su implementación, la cantidad de agentes y el tamaño de su mapa. Pero si alguna vez planea un gran enjambre de enemigos que se acercan desde múltiples direcciones en un área confinada, un campo de flujo seguramente será más barato que A * iterado.

Como un ejemplo extremo, puede ver un video aquí con 20 000 agentes, todos simultáneamente buscando rutas en una cuadrícula razonablemente pequeña .

A * no es pesado rendimiento. Me acercaría a esta situación variando los algoritmos. Haga A * de vez en cuando y, en el medio, verifique si el siguiente paso es libre o si necesita evasión.

Por ejemplo, rastrea la distancia de los jugadores desde la ubicación del objetivo A *, si está por encima de un umbral, recalcula a * y luego simplemente actualiza los movimientos. La mayoría de los juegos usan una combinación de puntos intermedios, por ejemplo, una cuadrícula simplificada para encontrar el camino y una lógica que maneja el movimiento entre puntos intermedios con algoritmos de dirección de evasión que usan rayos. Los agentes intentan correr a un punto de referencia distante maniobrando alrededor de obstáculos en su proximidad, es el mejor enfoque en mi opinión.

Aquí es mejor trabajar con máquinas de estados finitos y leer el libro "Programando la IA del juego por ejemplo" de Mat Buckland. El libro ofrece técnicas comprobadas para su problema y detalla las matemáticas requeridas. El código fuente del libro está disponible en la web; el libro está en C ++ pero algunas traducciones (incluida Java) están disponibles.

No solo es factible, creo que se hizo en un juego comercial en los años 90: BattleZone (1998).

Ese juego tenía unidades 3D con movimiento libre no basado en fichas y construcción de base basada en fichas.

Así es como parecía funcionar:

Primero, A * o algo similar (probablemente una variación de A * con límites estrictos sobre cuánto tiempo puede encontrar una ruta, por lo que nunca se necesitan demasiados recursos para ejecutarse, pero no siempre encuentra una ruta hasta el destino) se usaría para encontrar un camino para que un hovertank llegue a su destino sin atascarse en obstáculos basados ​​en fichas.

Luego, el tanque volaría alrededor del espacio sin mosaico como si fuera atraído hacia el centro de una baldosa cercana en su camino, y rechazado por obstáculos, otros tanques cercanos, etc.