A * é eficiente mesmo quando os obstáculos estão se movendo?

Estou apenas começando a aprender sobre a localização de caminhos e tenho estudado o algoritmo A * e minha principal preocupação é que todos os exemplos que eu vi mostrem obstáculos estáticos que ele calcula.

Se eu tiver obstáculos em movimento, digamos outros personagens, por exemplo, movendo-se também para que o personagem encontre o caminho, suponho que precisarei executar o algoritmo a cada quadro, mas estou preocupado que isso se torne bastante caro para o hardware processar cada quadro para cada ator em movimento.

Então, o A * ainda é eficiente o suficiente para ser usado sempre que os obstáculos estão se movendo, ou existe outro método de encontrar caminhos que lida com obstáculos mais eloquentes?

Existem vários algoritmos que são muito mais rápidos que A * quando você precisa recalcular um caminho com obstáculos em movimento. Veja aqui em "Recálculos simples".

No entanto, é provável que você não encontre uma solução pronta para uso em nenhum deles, portanto, em 99% dos casos, eles são um exagero para um jogo. Seu tempo seria mais bem gasto usando uma solução A * totalmente otimizada e usando os truques existentes para acelerar a busca de caminhos nos jogos:

• Recalculando apenas o melhor caminho em intervalos pouco frequentes
• Compartilhando os melhores caminhos entre várias unidades ( exemplo )
• Criando um gráfico hierárquico para que você só precise recalcular parte do caminho

etc. Você pode encontrar mais informações sobre esses truques e mais em todo o site, ou nas páginas A * de Amit

Sim. A * ainda é o caminho a percorrer em quase todos os casos. É o seu cálculo de custo do nó que se torna dinâmico e, portanto, mais complexo para calcular e rastrear.

Se você já sabe onde os obstáculos em movimento estarão no futuro, seu A * pode levar em consideração a temporalidade dos obstáculos na função de custo.

Por exemplo: este nó será alcançado em 4 ticks, ocupado desde o tick 3 até o tick 6, portanto, o custo da viagem nesse nó é de 6 a 4 = +2 ticks. Esse ainda pode ser o melhor caminho.

A direção de deslocamento do obstáculo também deve ser levada em consideração.

Se você não souber com antecedência, não poderá assumir obstáculos e recalcular o caminho quando os obstáculos forem alcançados, mas precisará fazer algo sobre impasses e bloqueios. (O mesmo se aplica se você puder prever onde estarão os obstáculos, mas isso por si só é um tipo de prevenção de impasse / livelock e pode ser bom o suficiente para o seu objetivo.)

Um impasse é quando ambos esperam o outro se mover e nenhum se move.

Um livelock é quando ambos ( ou mais <- é importante considerar) se movem para evitar o outro na mesma direção e acabam indo e voltando sem progresso.

A resolução de livelocks pode se tornar muito complexa e isso depende inteiramente das regras e da mecânica de colisão do seu jogo (por exemplo: eles devem lutar e destruir o obstáculo?).

Costuma voltar a ter seus objetos em movimento agendando reservas de nó / caminho (não se esqueça de cancelamentos quando eles mudam de caminho ou morrem) para que outros objetos em movimento possam planejar com antecedência.

Depois de obter essas informações, você também pode planejar interceptações.