Como o pathfinding nos jogos RTS funciona?

42

[crossposted from stackoverflow]

Em um jogo como Warcraft 3 ou Age of Empires, as maneiras pelas quais um oponente de IA pode se mover pelo mapa parecem quase ilimitadas. Os mapas são enormes e a posição de outros jogadores muda constantemente.

Como a descoberta de caminhos da IA ​​em jogos como esses funciona? Os métodos padrão de pesquisa de gráficos (como DFS, BFS ou A *) parecem impossíveis nessa configuração.

cobertores
fonte
2
Por que A * não funcionaria neste gráfico?
user712092
Blog relacionado: ai-blog.net/archives/000152.html
tenfour
1
@ tenfour, o link está quebrado agora.
Montreal

Respostas:

29

Na maioria dos casos, o uso de A * em uma malha de navegação (geralmente chamada de "navmesh") é a solução de RTSs comerciais de busca de caminhos que eles usam. Há uma explicação detalhada de como os navmeshes funcionam, por que eles são uma solução melhor que os sistemas de waypoint e links para recursos de implementação, aqui .

Se você planeja desenvolver modos especiais de jogo (captura de ponto / nó) ou unidades que patrulham, protegem-se, etc., você provavelmente desejará implementar uma camada de waypoint no topo da sua navmesh, para controlar o comportamento da IA ​​( não o caminho ).

Ari Patrick
fonte
17

Confira o algoritmo Flowfield usado no Supreme Commander 2. Ele faz um trabalho muito melhor do que a maioria dos sistemas de busca de caminhos RTS (vá para 0:50 para alguns exemplos).

ZorbaTHut
fonte
4
que é uma demonstração muito legal, mas não me diz nada sobre a própria implementação
MetaGuru
4
Eles mencionaram em uma frase - é baseada na pesquisa de fluxo de multidões da UW, que você pode encontrar em grail.cs.washington.edu/projects/crowd-flows .
O algoritmo do campo de fluxo parece bastante interessante e definitivamente parece fazer um trabalho muito melhor de correção do que a maioria dos algoritmos, mas eu gostaria que houvesse documentação pública sobre como o próprio sistema funcionava, não apenas como o sistema em que ele funciona funciona. Naturalmente, existem muitas perguntas que os desenvolvedores devem fazer antes de implementar um sistema principal como esse, mas, neste caso, parece que a única maneira de responder a essas perguntas é implementando o sistema primeiro. :(
Ari Patrick
2
@ Kragen: Você realmente só precisa de duas unidades antes que o simples A * (especialmente o waypoint) faça com que elas colidam uma com a outra sem parar, e você precisa de algum tipo de sistema para contornar a situação.
5
Com base no vídeo, a busca de caminhos do Starcraft 2 se parece com isso. O SC2 usa campo de fluxo?
precisa
7

Muitos jogos mais antigos usam A *. O Starcraft original usava A *; o que levou a alguns problemas ao lidar com colisões. O Starcraft 2 lida muito bem com a colisão, usando um comportamento de flaming / flocking para manter o controle fluido de grandes grupos. Este artigo sobre gamedev discute como isso pode estar sendo alcançado.

phillipwei
fonte
2

Eu já concordo com as outras respostas, mas também tente pensar no WoW / Warcraft3 como mundos 2D reais. Eles não são tão diferentes de base, são apenas os azulejos.

Você também pode pensar em como um GPS encontra o melhor caminho? Existe uma grande quantidade de algoritmos para encontrar caminhos através de mapas vinculados.

Eu acho que alguns dos primeiros scripts do "Quake bots" também podem ajudá-lo, pois foram desenvolvidos para trabalhar em "áreas desconhecidas" porque poderíamos projetar nossos próprios níveis do zero.

Em suma, minha maneira pessoal de lidar com esse mapa seria pensar nele como o descobridor A *. Mas primeiro eu pré-calculava todos os "pontos do bloco" e indexava todos esses com "vizinho mais próximo" etc. Depois, quando um objeto precisava passar de A para B, basta procurar em B, ver o que está conectado e continuar repetindo até você atingir a meta.

Dependendo do tipo de jogo e cenário / cenário, diferentes táticas de pré-varredura também podem ser úteis. Alguns jogos têm muito pouco obstáculo e podem ser movimentos em "linhas retas" + alguns "como posso me locomover" para objetos.

Espero que isso faça um pouco de sentido e talvez tenha lhe dado alguns pensamentos para trabalhar.

BerggreenDK
fonte
1

A maioria dos jogos usa algum tipo de algoritmo de busca ou A * para encontrar caminhos em um mapa. A IA é aprimorada em alguns aspectos, obviamente por razões de desempenho.

Você notará isso no Starcraft 2, onde os Zerglings obviamente não se saem bem, seria um pesadelo de CPU fazer isso nos Zerglings. Eles apenas fazem o melhor para ir de A a B e nem tentam encontrar o melhor caminho. Eles chegarão o mais próximo possível do gargalo ou das rampas.

Bryan Harrington
fonte
1

Mapa é uma grade. Grade é um gráfico. A * funciona em gráfico, é um algoritmo de busca de gráficos. A * deve procurar alguns nós do gráfico.

Como foi mencionado, eles podem usar a malha de navegação. Mas o A * (ou algo semelhante) estará no topo dessa malha de qualquer maneira, porque os polígonos dessa malha são apenas nós de um gráfico; A * procurará então o caminho de um polígono para outro polígono.

Não tenho certeza sobre Warcraft ou jogos comerciais, mas também existe uma técnica chamada Difusão Colaborativa e é muito simples; geralmente é feito na grade. Também existe uma técnica chamada Campos Potenciais , que é muito semelhante à anterior, se não a mesma.

Você também pode tentar:

  • se alguns desses jogos têm código fonte disponível
  • se alguns dos clones desses jogos têm fonte disponível
  • se SDK ou editores não sugerem algo
  • Pergunte aos empregadores de empresas que fazem esses jogos, alguns deles podem estar dispostos a compartilhar
user712092
fonte
0

Não tenho muita experiência, mas acho que uma boa solução é baseada em heurísticas, não em uma verificação completa do mapa conhecido. As heurísticas em que posso pensar são baseadas localmente e baseadas na experiência. Os controles locais podem basear-se na verificação do terreno e nos obstáculos locais, mantendo o movimento na direção necessária. Eu acho que a maioria dos mapas não requer movimentos complexos de labirinto, mas são bem conectados. Outra heurística é usar caminhos conhecidos anteriores (explorados por outras unidades ou explicitamente pelo usuário) para mover as unidades para posições conhecidas ou quase conhecidas. Mas eu estou falando sobre mover em grandes mapas, não em espaços fechados, como disse o ZorbaTHut. Em casos aglomerados, o algoritmo pode ser mais complexo, exigindo tipos de "previsão", coordenação entre unidades da mesma equipe ou apenas estratégias de espera semelhantes a semáforos. Além disso,

Eu acho que os algoritmos heurísticos são bons porque geralmente fornecem uma boa solução em grandes espaços com um tempo de computação razoável (o que importa quando você está movendo muitas unidades).

Desculpe se esta é uma resposta genérica: trabalhei com multidões, mas o espaço era bastante peculiar e não consigo explicar exatamente como o algoritmo funcionava (era baseado em agente, de qualquer maneira, não definido globalmente). Espero que você possa obter algumas idéias úteis da minha resposta.

AkiRoss
fonte
Mmmh eu me pergunto o que havia de errado no que eu disse ... Foi muito difícil colocar um comentário?
AkiRoss
BTW, eu gostaria de destacar que A * usa abordagem heurística. Obrigado pelo -2.
AkiRoss
Sua resposta equivale a "Vala A * e seu estilo e faça você mesmo". Isso pode ser o começo de uma resposta razoável, mas você fornece muito pouca informação além da sugestão. Ele acha que o motivo da baixa votação é que você não deixa claro o quão difícil sua solução seria implementar. Não duvido que um super gênio, com tempo ilimitado, possa codificar / ajustar um algoritmo de correção para um determinado RTS que seria superior a A * em uma malha de navegação. Mas "gênio" e "ilimitado" são muito difíceis de encontrar.
Deft_code 24/11/2010
Oh, certo. Eu pensei que o cara queria uma resposta genérica, já que ele não perguntou como fazer uma, mas como eles funcionam em geral. De qualquer forma, não sou especialista como disse: estava apenas fornecendo algumas informações sobre as soluções que conhecia sobre a exploração de grandes espaços em um aplicativo geral de IA. Obrigado por seu comentário.
AkiRoss