Como devo replanejar A *?

10

Eu tenho um inimigo chefe que procura o jogador usando o algoritmo A *. É um ambiente bastante complexo, e estou fazendo isso no Flash, para que a pesquisa possa ficar um pouco lenta ao pesquisar por longas distâncias. Se o player estivesse parado, eu poderia procurar apenas uma vez, mas no momento estou pesquisando todos os quadros. Isso leva tempo suficiente para que minha taxa de quadros esteja sofrendo.

Qual é a solução usual para isso? Existe uma maneira de "replanejar" A * sem refazer toda a pesquisa? Devo procurar um pouco menos frequentemente (a cada meio segundo ou segundo) e aceitar que haverá um pouco de imprecisão no caminho?

Gregory Avery-Weir
fonte

Respostas:

13

Você não precisa pesquisar o caminho inteiro em um quadro; eu fiz isso fornecendo um limite no loop de pesquisa; a IA começará a seguir as poucas informações que ele possui; no próximo quadro, pesquisarei um pouco mais. , pode levar três quadros até que o caminho seja encontrado. Pode parecer bastante convincente, pois parece que a IA está realmente pesquisando.

PhilCK
fonte
+1. Isso também é o que Mat Buckland descreve em seu livro de IA. Ele chama isso de "Planejamento de caminho em fatias de tempo" ( books.google.ch/… ). Coisa boa.
21811 bummzack
8

Você pode usar a detecção de proximidade para executar o algoritmo a cada poucos quadros, se a distância for muito grande (porque na maioria dos casos, se a distância for grande, o caminho de destino não mudará drasticamente de quadro para quadro). Por exemplo:

      Distance > 100, run A* every 2 seconds
100 > Distance >  50, run A* every 1 second
50  > Distance >  25, run A* every 10 frames
25  > Distance <  25, run A* every frame

Isso pressupõe que exista uma distância em que a execução de A * em cada quadro tenha desempenho ainda aceitável. Em suma, eu iria para a sua segunda opção. Especialmente se o que você tem está funcionando, eu evitaria reimplementar outra coisa se eu pudesse reduzir o que está funcionando bem. A linha inferior é que você terá que experimentar para ver se funciona para o seu jogo.

Nate
fonte
8

Não estou realmente respondendo sua pergunta exata, mas ... se você estiver disposto a "trapacear", você pode fazer o jogador deixar "migalhas de pão" e fazer com que o chefe as siga. Se o caminho da trilha de trilha se cruzar, siga o mais recente (isso faz com que o chefe evite loops e outros caminhos que podem ser muito longos, para não mencionar não seguir o caminho exato do jogador)

Isso funcionaria bem se o chefe fosse algum tipo de animal com um bom senso de olfato. Isso funcionaria muito como seguir o cheiro do jogador :)

ggambett
fonte
5

Seu caso é basicamente o que o HPA * foi inventado para resolver. Se parecer um exagero, no entanto, eu tenderia a pensar que a busca de caminhos a cada meio segundo deveria funcionar muito bem.

caos
fonte
4

Se for um ambiente estático, você poderá pré-calcular o caminho mais curto de todos os pares.

Peter Taylor
fonte
2
Se é um pequeno ambiente estático.
Depende da plataforma e da memória disponível.
Nate
@ Joe, @ Nate, é verdade.
Peter Taylor
2

Eu criei um jogo para uma competição de 48 jogos em que um personagem A * segue o jogador em um nível. Como minha implementação A * era lenta (não era possível executar todos os quadros), coloquei o intervalo em um atraso de três segundos. Isso teve o resultado não intencional de permitir ao jogador "enganar" a IA por alguns instantes. Na verdade, tornou o jogo mais divertido.

Posteriormente, aprimorei o desempenho da implementação A * e tentei executá-la em todos os quadros. O jogo deixou de ser divertido porque o inimigo sempre buscava perfeitamente o jogador.

Isso foi inesperado e uma boa experiência de aprendizado.

GloryFish
fonte
1
Este é um bom ponto. Lembro-me de ler sobre encontrar caminhos no pac-man, onde eles deliberadamente usaram um algoritmo imperfeito, permitindo ao jogador ser mais esperto que os fantasmas. Cada fantasma tinha uma imperfeição ligeiramente diferente, dando-lhes mais caráter. A diferença aqui é que, nos jogos, diversão> tudo mais.
precisa
0

A menos que você queira (ou precise) usar A *, você também pode dar uma olhada nos comportamentos de direção . Como não há planejamento de caminho completo por quadro envolvido, deve ser muito mais leve no processamento.


fonte
Uso comportamentos de direção (especificamente a busca) nos casos em que não há obstáculos entre o agente e seu alvo. Infelizmente, meu ambiente contém coisas como corredores giratórios, onde é necessária uma solução mais inteligente.
Gregory Avery-Weir