qual é a solução padrão para encontrar caminhos em direção a um alvo em movimento?

Estou trabalhando em um RTS 2D como o jogo, A * básico funciona perfeitamente para mover uma unidade do ponto A para o ponto B.

Mas agora estou enfrentando o problema contínuo de localização de caminhos, como A, ataque um objeto em movimento B, chamo A * em cada quadro, uma vez que a posição do Objeto B mudou, parece ineficiente.

então, qual é o método padrão para esse problema?

Pelo que sei, você pode dar uma olhada no algoritmo D *, que significa "Dynamic A *". Este algoritmo é usado para calcular a busca de caminhos para um ambiente dinâmico, aqui com um alvo em movimento.

Aqui está um artigo usando D * para mover o caminho do alvo: Moving Target D * Lite

Uma opção é criar apenas um novo caminho uma vez a cada poucos quadros. Se você fez uma ou duas vezes por segundo, em vez de mais de 60 vezes por segundo, é improvável que o usuário note, a menos que sejam dois objetos em movimento muito rápido

Você pode usar a abordagem "curva de cão" que os cães aparentemente usam ao caçar alguém. Eles calculam onde o ponto de impacto estará "no futuro" e os conjuntos de diretos para essa posição.

Uma maneira simples e aproximada pode ser algo assim:

A = NPC

B = Alvo

T = tempo para chegar à posição B: s (B: s posição inicial)

Calcule onde B estará no tempo 'T' (se B continuar na mesma velocidade / ângulo) e vá para lá.

Essa não é a maneira perfeita, pois a distância muda, mas muito mais simples do que criar uma solução perfeita e muito melhor do que apenas tentar chegar ao 'B'.

Concordo com Kylotan que não existe um método padrão .

Um método que vi trabalhar foi assumir que o alvo continua se movendo na mesma direção e alterar a posição do objetivo enquanto você executa o algoritmo de localização de caminhos. Isso significa que você deve manter duas métricas nos nós A * (custo e tempo, em vez de apenas custo).

Fazer melhor do que isso é muito difícil. A menos que você realmente tenha conhecimento sobre o caminho inabalável do alvo, está indo para a terra da IA ​​bastante difícil, porque terá a segunda adivinhação ou simulação do comportamento do alvo para adivinhar onde eles estarão e o caminho para isso. Esse tipo de IA é um jogo AB em tempo real da teoria dos jogos, uma área que não é padrão em nenhum kit de ferramentas de IA para jogos em 3D.

Uma maneira de encontrar o caminho dinâmico é fazer com que a entidade preveja para onde o alvo está indo e vá para lá.

Uma maneira de fazer isso é usar uma série de Taylor.

Vou chamar o caminho do alvo ao longo do tempo como a função S (t) onde S é a posição et é a hora atual e a aproximação ao caminho é A (f) ef é a data no futuro que se aproxima. .

Então a aproximação mais simples e mais estúpida é A (f) = 0.

O próximo mais simples é A (f) = S (t) onde t é o tempo atual ef é o futuro. Isso está prevendo que o alvo simplesmente pára no lugar.

O terceiro mais simples é A (f) = S '(t) * f + S (t) onde S' é a derivada de S em relação ao tempo. Isso está prevendo que o alvo continua a uma velocidade constante, sem aceleração.

O quarto mais simples é A (f) = S '' (t) * f ^ 2/2 + S '(t) * f + S (t). Isso está prevendo que o alvo está acelerando a uma velocidade constante, como uma bola caindo.

Eu sei que isso pode ser reformulado em termos de mudança no tempo, o que provavelmente é mais conveniente para um jogo. Agora S pode ser qualquer coisa. Pode ser uma coordenada X, pode ser uma coordenada Y, pode ser a distância entre os objetos, pode ser um ângulo. Também existem prováveis ​​métodos melhores de prever o caminho futuro de um objeto, para que eu olhe um pouco.

Se o terreno estiver razoavelmente aberto e o alvo não estiver muito longe do perseguidor, você poderá usar o comportamento da direção de interceptação. Essencialmente, você toma a posição e a velocidade do alvo para calcular uma posição na frente do alvo que não está muito longe e nem muito perto, e você orienta o perseguidor em direção a esse ponto (calculado em intervalos regulares).