AI orientada para a ação: algoritmo de evasão leva muito tempo

Evasão, o processo de fuga, é o oposto de perseguir. Em vez de tentar diminuir a distância do alvo, tentamos maximizá-lo.

Leva muito tempo enquanto evadimos vários objetos simultaneamente. Eu uso o BFS aqui. Para tornar mais rápido quais algoritmos devo usar?

Eu sugiro que você use comportamentos de direção para simular esses tipos de comportamento. Veja esta página para um exemplo de comportamento evasivo implementado dessa maneira.

A idéia básica é que você considere apenas propriedades simples, como os vetores de posição e velocidade de suas presas e predadores, para calcular a alteração desejada nessas propriedades em tempo linear. Isso resulta em um comportamento responsivo, mas realista.

No entanto, isso tem o custo de não levar em consideração outros fatores, como objetivos de mais alto nível (a posição de power-ups, por exemplo) ou a posição de obstáculos estáticos, como você faria na busca de caminhos. Isso pode ser levado em consideração combinando a abordagem Comportamentos de direção com, por exemplo, campos em potencial (consulte Usando campos potenciais em um cenário de jogo de estratégia em tempo real (Tutorial) ) ou busca de caminhos (por exemplo , método de mapa de corredor ). No caso deste último, você deseja diminuir a frequência de atualização (e confiar nos Comportamentos de Direção para compensar quaisquer erros que possam ocorrer por causa disso) ou fazer replanejamento parcial, possivelmente combinado com uma abordagem mais hierárquica (por exemplo, Localização de caminho hierárquico quase ideal) (HPA *) .

Se você deseja uma resposta mais específica, melhore sua pergunta com mais detalhes sobre o seu problema. Por exemplo, considere descrever o que é o seu jogo e o número de NPCs sobre os quais estamos falando.