Fazendo a IA seguir caminhos diferentes entre si

16

Eu tenho um jogo 2D de cima para baixo, onde a IA aparece nas bordas do mapa e corre em direção ao centro.

Estou usando A * e uma malha de nó para fazer o pathfinding.

No momento, a IA aparece em um ponto na borda do mapa e todos seguem o mesmo caminho, que é o caminho mais curto para o centro.

Agora, quero que sejam mais surpreendentes e interessantes e tomem caminhos diferentes entre si.

Posso pensar imediatamente em duas idéias para fazer isso, mas queria saber se existem outras maneiras ou melhores que as pessoas costumam usar?

  1. Quando um inimigo aparecer e gerar um caminho para o centro, aumente temporariamente o custo de todos os nós nesse caminho e depois diminua-os lentamente ao longo do tempo. Então a IA inimiga que aparecer mais tarde será forçada a seguir um caminho mais amplo.

  2. A abordagem acima levará a IA a seguir um caminho cada vez mais amplo e ainda assim ser muito previsível. Por isso, pensei em introduzir também vários nós de objetivos intermediários no mapa. Quando a IA aparece, eles escolhem aleatoriamente um dos objetivos intermediários e dirigem-se para lá primeiro antes de irem para o centro do mapa. Combinar isso com a abordagem acima de aumentar os custos pode parecer muito bom?

Quais abordagens as pessoas acharam que funcionam melhor para fazer com que a IA varie os caminhos que elas seguem, parecem convincentes e surpreendentes?

TerryB
fonte

Respostas:

7

Sua segunda opção sugere uma abordagem mais fundamental: garantir que os inimigos se aproximem do jogador de diferentes direções. A questão é: até onde eles precisam viajar para "contornar" o seu jogador? O ideal para isso seria uma mistura de

  • gerar pontos dinamicamente que cercam (ou seja, seguem) a posição do jogador;
  • o que Nevermind sugeriu em termos de caminhos aleatórios para esses pontos circundantes, em maior ou menor grau.

Dessa forma, você pode garantir que as IAs não façam desvios desnecessariamente longos apenas para obter uma variação realista do caminho ao convergir no player.

A difusão colaborativa faz o que você quer implicitamente como parte do algoritmo. Mas não é trivial de implementar.

Engenheiro
fonte
A difusão colaborativa é apenas um preenchimento de inundação com alguma ponderação. É trivial de implementar, talvez mais fácil que o A *. Requer apenas uma visão diferente do seu mundo - uma mudança conceitual não trivial, talvez, mas sem problemas de implementação.
É ainda não trivial de implementar como resultado de ser um ponto de vista não-padrão em termos de gestão entidades AI :)
Engenheiro
Obrigado Nick. Acho que configurar alguns waypoints que cercam o jogador no centro do mapa será o principal caminho a percorrer. Não tenho certeza, nesta fase, se eles serão gerados dinamicamente ou se haverá algum trabalho manual envolvido em cada nível para a minha situação em particular. Obrigado novamente!
TerryB
12

Como primeira idéia, tente adicionar um pequeno valor aleatório ao peso de cada nó ao encontrar o caminho. Dessa forma, todo agente procurará um caminho em um ambiente ligeiramente diferente. Não tenho certeza se isso funcionará no seu caso, mas deve ser muito fácil tentar.

deixa pra lá
fonte
Os inimigos acabarão correndo como galinhas e, em um ambiente refinado, os caminhos não serão tão diferentes assim. É um bom complemento para outras soluções, mas não é uma solução em si
Coyote
@ Coiote Isso depende muito da estrutura da malha de navegação e das relações entre pesos dos nós, velocidades e componentes aleatórios. Por isso, enquadrei a resposta como uma sugestão para tentar, não como uma resposta definitiva.
Nevermind
De fato :) Normalmente sou fã de entropia. Mas o resultado final raramente é ótimo.
Coyote
Na verdade, acredito que a resposta de Nick Wiggill é muito melhor que a minha. Mas, de alguma forma, não está recebendo os votos positivos que merece.
Nevermind
É ... Mas o seu é o primeiro e mais simples ... poderíamos tentar votá-lo: P
Coyote
3

Eu gosto da resposta de Nevermind , no entanto, dada a limitação descrita nos comentários, é isso que eu tentaria:

  1. O algoritmo de uma única unidade para o centro registra a distância total percorrida.
  2. Para cada unidade subseqüente, aloque uma distância aleatória e pequena, maior que essa.
  3. Ao fazer o A * para cada unidade, adicione um peso extra com base na sua proximidade e na distância que você deseja "viajar". Provavelmente seria algo assim (distanceToGoal) + Max(0, desiredDistance - distanceTravelled)).

Isso faria com que as unidades tentassem ir além, o que provavelmente é um caminho diferente, o que resultaria em possíveis caminhos diferentes.

Você também pode adicioná-lo ao seu huerestic inicial para cada unidade, mas o intervalo aleatório provavelmente teria que ser um pouco maior.

Jonathan Dickinson
fonte
2

Como apontado por Nick Wiggill, a abordagem mais simples seria fazer um círculo em torno do objetivo.

  • atribua aleatoriamente um ponto próximo a este círculo como um waypoint.
  • elimine todos os caminhos do círculo do caminho inicial (ou aumente drasticamente o valor desses pontos)
  • então, a partir desse ponto de referência, obtenha o caminho para o objetivo.

A parte importante é eliminar todos os caminhos do círculo para o waypoint original, pois você provavelmente terminaria com inimigos cruzando o círculo para chegar ao waypoint inicial.

Com isso, você pode obter qualquer variante jogando com vários valores, adicionando waypoints secundários no círculo próximo ao inicial etc.

Coiote
fonte
se o seu mapa o suportar, encontre locais 'interessantes' ao redor deste círculo (portas, coberturas, árvores, pedras, edifícios; qualquer nó com alguma vantagem tática) e faça com que seus inimigos sigam primeiro por esses locais, se estiverem disponíveis e só aparecerem aberto se for necessário. Isso parecerá muito mais inteligente do que apenas atingir um ponto aleatório na borda do círculo.
DampeS8N
Obrigado Coiote, sim, provavelmente vou usar a solução Nicks e, como sugerido pelo DampeS8N, alguns locais importantes de interesse como pontos de referência. Para evitar o problema da AI "cruzando o círculo" Eu estou indo só para aumentar significativamente o custo dos nós no círculo para A * deve ser encaminhado em torno dele espero :)
TerryB
2

Seu problema aqui é essencialmente que A * é um algoritmo para encontrar a rota mais rápida para um destino. Se esse é seu critério principal para um caminho "bom", não surpreende que todos os seus atores tomem as mesmas decisões.

O que você precisa fazer é modificar seus critérios de qualidade para o caminho, para que 'o menor seja o melhor' não seja o único fator. O elemento aleatoriedade é fundamental nisso, mas não tanto que diminua a inteligência de encontrar caminhos (ou seja, os atores tomam caminhos estupidamente redondos para o alvo).

A busca de caminhos é ingênua por natureza, pois geralmente supõe que o ator tenha conhecimento perfeito de toda a rota antes de começar. Isso sempre vai parecer irreal. A solução sugeriu que objetivos intermediários escolhidos estão a um passo disso - a IA está tentando se aproximar do alvo, mas apenas tenta navegar em pequenas seções por vez (isso é análogo à vida real, onde você só pode navegar até o ponto mais distante). como você pode ver e ao percorrer mais o caminho, pode ver mais adiante).

Eu talvez recomendo uma maneira mais simples de ver isso. Quando estiver procurando o caminho, não basta manter um único melhor caminho que encontrei até agora. Em vez disso, colete um conjunto dos melhores 5 ou 10 caminhos. Use um limite para descartar valores discrepantes óbvios. Por exemplo, se o melhor caminho percorre 20u para chegar ao alvo, o próximo melhor percorre 21u, e o próximo depois percorre 50u. Defina um limite 20% maior que o melhor caminho e descarte o caminho de 50u porque é estupidamente mais longo. Agora você tem vários caminhos para escolher e, ao selecionar aleatoriamente esse conjunto de caminhos, seus atores tomarão decisões diferentes.

No entanto, você não obterá esse tipo de informação com a pesquisa padrão A *, então acho que você precisaria modificar o algoritmo ou usar outra coisa para reunir o conjunto de caminhos possíveis.

MrCranky
fonte
1

Se você tiver um pequeno conjunto de inimigos recorrentes (ou tipos de inimigos), tente dar a eles personalidades que afetam seus movimentos. Eles não precisam ser grandes, apenas coisas que surgem de vez em quando. Um bom exemplo disso são os fantasmas do Pac-Man. Divida seu A * em vários objetivos intermediários. Talvez um inimigo seja realmente estúpido e se perca facilmente, indo em uma direção aleatória a cada terceiro nó (que não seja diretamente para trás). Seja criativo.

SomeGuy
fonte