Desbravando com eficiência muitos inimigos que se aglomeram em torno de obstáculos

Estou tentando melhorar o caminho para os inimigos do meu jogo. No momento, eles basicamente se movem constantemente em direção à posição exata do jogador, calculando o ângulo entre eles e os jogadores e se movendo nessa direção. Eu também tenho um algoritmo de agrupamento que evita que os inimigos se amontoem uns sobre os outros, para que eles se formem em grupos, em vez de se agruparem.

No entanto, agora que adicionei um mapa baseado em blocos, preciso que os inimigos também sejam capazes de percorrer obstáculos e paredes, por exemplo. Inicialmente, tentei adicionar um valor de separação a blocos "não passíveis de passagem", para que o algoritmo de agrupamento considerasse as paredes e os obstáculos como objetos para os quais se afastar. Eu ainda tenho que descobrir se isso é ou não viável, porque meu teste inicial mostrou os inimigos atingindo uma "parede" invisível onde não há azulejos que não podem ser percorridos, mas, por alguma razão, eles acertam e começam a disparar.

Fiquei me perguntando se poderia ser muito alto desempenho para calcular um caminho para o jogador usando A * e, em seguida, use o algoritmo flocking para evitar aglomeração. Originalmente, meu jogo seria um shooter baseado em ondas, mas decidi torná-lo baseado no nível na linha direta da Miami, por isso é provável que eu tenha menos inimigos, com a horda ocasional, e apenas faça eles mais fortes.

Esta é uma solução viável? Estou usando Java com o Slick2D como meu mecanismo de jogo. Ou existe uma solução / algoritmo melhor que lide com esses dois problemas?

Isso soa como um caso de uso para campos de fluxo.

Nesta técnica, você faz uma única consulta de busca de caminho a partir do (s) objeto (s) do jogador, marcando cada célula que encontra com a célula da qual chegou.

Se todos os seus ladrilhos / arestas tiverem um custo de passagem igual, você poderá usar uma pesquisa simples e abrangente. Caso contrário, o algoritmo de Dijkstra (como A * sem objetivo / heurística) funciona.

Isso cria um campo de fluxo: uma tabela de pesquisa que associa cada célula ao próximo passo em direção ao objeto player mais próximo dessa posição.

Agora, seus inimigos podem procurar sua posição atual no campo de fluxo para encontrar o próximo passo no caminho mais curto para evitar obstáculos até o objeto jogador mais próximo, sem que cada um faça sua própria consulta de busca de caminhos.

Isso aumenta cada vez melhor quanto mais inimigos você tiver no seu rebanho. Para um único inimigo, é mais caro que o A *, porque pesquisa no mapa inteiro (embora você possa sair mais cedo depois de atingir todos os agentes de busca de caminhos). Porém, à medida que você adiciona mais inimigos, eles compartilham cada vez mais o custo de encontrar caminhos, computando segmentos de caminho compartilhados uma vez, e não repetidamente. Você também ganha vantagem com o fato de que os BFS / Dijkdtra são mais simples que A * e geralmente mais baratos para avaliar por célula inspecionada.

Exatamente onde o ponto de equilíbrio atinge, de A * individual mais barato a A * com memorização sendo mais barata (onde você reutiliza alguns dos resultados de uma consulta de busca de caminho anterior para acelerar a próxima), para os campos de fluxo sendo mais barato, dependerá da sua implementação, do número de agentes e do tamanho do seu mapa. Mas se você planejar um grande número de inimigos se aproximando de várias direções em uma área confinada, um campo de fluxo quase certamente será mais barato que o A * iterado.

Como um exemplo extremo, você pode ver um vídeo aqui com 20.000 agentes, todos simultaneamente localizando em uma grade razoavelmente pequena .

A * não apresenta desempenho pesado. Eu abordaria essa situação variando os algoritmos. Faça A * de vez em quando e verifique se o próximo passo é livre para entrar ou se você precisa de evasão.

Por exemplo, rastreie a distância dos jogadores do local de destino A *, se estiver acima de um limite, recalcule um * e faça apenas movimentos de atualização. A maioria dos jogos usa uma combinação de waypoints, por exemplo, uma grade simplificada para encontrar caminhos e uma lógica que lida com o movimento entre os waypoints com algoritmos de evasão e direção usando raycasts. Os agentes tentam correr para um ponto de referência distante, manobrando obstáculos na proximidade deles, é a melhor abordagem na minha opinião.

É melhor trabalhar com máquinas de estado finito aqui e ler o livro "Programming Game AI By Example" de Mat Buckland. O livro oferece técnicas comprovadas para o seu problema e detalha a matemática necessária. O código-fonte do livro está disponível na web; o livro está em C ++, mas algumas traduções (incluindo Java) estão disponíveis.

Não só é viável, acredito que foi feito em um jogo comercial nos anos 90 - BattleZone (1998).

Esse jogo tinha unidades 3D com movimento livre não baseado em blocos e construção de base baseada em blocos.

É assim que parecia funcionar:

Primeiro, A * ou algo semelhante (provavelmente uma variação de A * com limites estritos de quanto tempo um caminho pode ser encontrado, portanto, nunca são necessários muitos recursos para executar, mas nem sempre encontra um caminho até o destino) seria usado para encontrar um caminho para um hovertank chegar ao seu destino sem ficar preso em obstáculos baseados em ladrilhos.

Em seguida, o tanque voava pelo espaço cultivado como se fosse atraído para o centro de um ladrilho próximo em seu caminho e repelido por obstáculos, outros tanques próximos etc.