Mapa de jogo parcialmente observável - A * é apropriado?

16

Sei muito pouco sobre desenvolvimento de jogos e estou tentando entender os algoritmos de busca de caminhos.

Considere esta configuração: um agente está em um mapa 2D e deve encontrar o caminho mais curto para um objeto conhecido globalmente, mas possui apenas informações sobre obstáculos em seu escopo de visão local (ou seja, apenas obstáculos imediatos são conhecidos, o layout geral do mapa é desconhecido). )

Além disso, cada movimento para um quadrado adjacente é caro e o algoritmo de busca de caminhos deve minimizar o número de movimentos.

A eficiência computacional também é de extrema importância e mais importante que a precisão.

A * é apropriado para este caso de uso?

algorithm path-finding maps David Chouinard
fonte

Respostas:

19

Você deve usar o algoritmo D * , projetado para esse cenário exato. Especificamente, a implementação do D * Lite é a variante mais eficiente e simples.

jmegaffin
fonte
2
Altamente relevante . Compreender o D * -lite é simples quando você entende o LPA * (o algoritmo D * -lite é baseado) , mas o próprio LPA * é bastante complexo. Então, se você está pensando em realmente implementar D * -Lite, o papel na LPA * seria o lugar para começar (supondo que você já entendeu A *, que é)
BlueRaja - Danny Pflughoeft
3

Muitas implementações de IA de jogo nessa situação escolherão trapacear e darão a si mesmas o conhecimento completo do mapa, onde seu oponente humano não o possui. Você pode simplesmente aplicar A * ao mapa completo.

O quão sensato isso parece para as unidades controladas por computador dependerá de coisas como o labirinto como os mapas e se o jogador provavelmente aprenderá os layouts do mapa ao longo do tempo.

Se for para unidades controladas por jogadores, você também pode impedir que o jogador selecione um destino que ainda não explorou, para forçá-los a explorar manualmente.

Adão
fonte
2
Boas sugestões, não apropriadas para o meu caso de uso, mas podem ser úteis para outras pessoas. (Estou desenvolvendo um AI para competir em um jogo de simulação)
David Chouinard
também existem jogos que usam a implementação de localização de caminhos, assumindo que áreas inexploradas são passíveis de travessia, enquanto as áreas visitadas anteriormente não tiveram nenhuma alteração na capacidade de travessia desde a última visita (ou seja, não saberia que um muro pode ter sido destruído ou construído até que visite a área novamente).
Lie Ryan