Algoritmos de localização de caminhos?

24

Eu postei essa pergunta no estouro de pilha primeiro, mas acho que ninguém está muito interessado em videogames por lá ...

Quais são alguns algoritmos de localização de caminhos usados ​​em jogos de todos os tipos? (De todos os tipos em que os personagens se movem, de qualquer maneira) O Dijkstra's é usado muito? Eu acho que não, pois na verdade não segue as etapas a serem tomadas para chegar a algum lugar, certo? Se estou entendendo direito, ele determina apenas qual objeto é o mais próximo. Não estou realmente procurando codificar nada; apenas fazendo alguma pesquisa, embora se você colar pseudocódigo ou algo assim, tudo bem (eu posso entender Java e C ++). Basicamente, estou procurando uma visão geral rápida da localização de caminhos em geral.

Eu sei que A * é como o algoritmo a ser usado em jogos 2D. Isso é ótimo e tudo, mas e os jogos 2D que não são baseados em grade? Coisas como Age of Empires ou Link's Awakening. Não há espaços quadrados distintos para navegar, então o que eles fazem?

O que os jogos em 3D fazem? Eu li este http://www.ai-blog.net/archives/000152.html , que eu ouvi dizer que é uma grande autoridade sobre o assunto, mas na verdade não explica COMO, depois que as malhas são definidas, a localização do caminho está concluída. Se A * é o que eles usam, então como é feito algo assim em um ambiente 3D? E como exatamente as splines funcionam nos cantos arredondados?

Pojo
fonte
2
Eu acho que essa pergunta é muito aberta para o formato de perguntas e respostas da SE. Perguntas frequentes
John McDonald
11
Os jogos que você mencionou devem dividir o mapa em nós para A * de uma maneira ou de outra. Que quebram processo não tem que envolver quadrados grades e há muitas maneiras de fazer it.Check este vid youtube.com/watch?v=nGC_kBCoHYc , um bom jogo faz com que os jogadores não podem dizer o que eles estão realmente fazendo nos bastidores.
XiaoChuan Yu
11
Há muitas perguntas aqui, então não posso realmente escrever uma resposta, mas observarei que o Dijkstra retorna um caminho, e a maioria dos algoritmos de busca de caminhos é multiuso. Você converte seu mundo, 2D ou 3D, em um gráfico conectado e executa um algoritmo de busca de caminhos nele.
Gregory Avery-Weir
Apenas para referência: respondi à pergunta no Stack Overflow .
Julian
11
Permita-me reclamar. Esta questão tem 4 upvotes no SO, em comparação com 4 perto de votos aqui na GDSE. Não posso deixar de sentir que os moderadores deste site estão sendo excessivamente agressivos. Claro, posso ver como a pergunta vai contra as diretrizes especificadas no FAQ, mas, citando, essas diretrizes estão em vigor para impedir diminishing the usefulness of our site. Essa pergunta já foi escolhida 3 vezes, o que é uma prova de que ela foi útil para alguns usuários. Portanto, não posso deixar de sentir que votar para fechá-lo e arriscar uma eventual remoção é muito mais contraproducente.
David Gouveia

Respostas:

62

Muitas perguntas ao mesmo tempo, por isso é difícil dar uma resposta concreta, mas discutir alguns desses tópicos. Dividirei a resposta em duas e tentarei resolvê-la da melhor maneira possível. Não afirmo que nenhuma dessas listas esteja completa , mas são alguns dos métodos diferentes que me lembro.


Parte 1 - Algoritmos de localização de caminhos

Para iniciantes, existem muitas maneiras de implementar a busca de caminhos, mas nem todas elas retornam o caminho mais curto ou são eficientes ou mesmo confiáveis. Por exemplo:

  • Métodos primitivos que não "olham para o futuro" e dão um passo de cada vez:

    • Backstepping aleatório - Dê um passo de cada vez na direção da meta. Se um obstáculo for encontrado, tente contorná-lo, seguindo um pouco em uma direção aleatória e depois tente novamente. Não é confiável e ficará preso em várias situações.

    • Rastreamento de obstáculos - Outra abordagem, semelhante ao passo aleatório, mas em vez de voltar aleatoriamente, comece a rastrear o objeto quando uma colisão for encontrada, como se você tivesse a mão direita presa na parede e tivesse que se mexer para tocá-la. Quando não houver colisão, continue se movendo na direção da meta. Mais uma vez pode ficar preso em muitas situações.

  • Métodos que esperam encontrar o caminho inteiro de uma só vez:

    • Primeira Pesquisa de Largura - Percurso simples de gráfico, visitando cada camada de crianças de cada vez, pare quando o caminho for encontrado. Se o gráfico não for ponderado (ou seja, a distância entre cada nó adjacente é sempre a mesma), ele encontra o caminho mais curto, embora não com muita eficiência. Para gráficos ponderados, pode não retornar o caminho mais curto, mas sempre encontrará um, se existir.

    • Pesquisa em profundidade primeiro - Outra maneira de percorrer um gráfico, mas, em vez de tomá-lo camada por camada, o algoritmo tenta pesquisar profundamente no gráfico primeiro. Esse método pode ter problemas se a profundidade da pesquisa não for limitada, especialmente ao usar uma implementação recursiva, o que pode levar a um estouro de pilha; portanto, é mais seguro implementá-lo iterativamente usando uma pilha.

    • Melhor Primeira Pesquisa - Similar à Pesquisa de Largura Primeira, mas usa uma heurística que escolhe primeiro o vizinho mais promissor. O caminho retornado pode não ser o menor, mas é mais rápido do que executar a primeira pesquisa. A * é um tipo de melhor primeira pesquisa.

    • Método de Dijkstra - Controla o custo total desde o início até cada nó visitado e o utiliza para determinar a melhor ordem para percorrer o gráfico. Funciona com gráficos ponderados e retorna o caminho mais curto, mas pode envolver muita pesquisa.

    • A * - Semelhante ao Dijkstra, mas também usa uma heurística para estimar a probabilidade de cada nó estar próximo da meta, a fim de tomar a melhor decisão. Devido a essa heurística, A * encontra o caminho mais curto em um gráfico ponderado de maneira muito mais oportuna.

  • Depois, há variações de A * (ou otimizações de busca de caminho em geral) que o tornam mais rápido ou mais adaptado a determinadas circunstâncias, como (consulte a resposta relacionada e uma lista abrangente em cstheory.SE ):

    • LPA * - semelhante a A *, mas pode recalcular mais rapidamente o melhor caminho quando é feita uma pequena alteração no gráfico
    • D * Lite - Com base no LPA *, ele faz a mesma coisa, mas assume que o "ponto inicial" é uma unidade que se move em direção ao acabamento enquanto as alterações nos gráficos estão sendo feitas
    • HPA * (hierárquico) - usa várias camadas em diferentes níveis de abstração para acelerar a pesquisa. Por exemplo, uma camada de nível superior pode simplesmente conectar salas, enquanto uma camada de nível inferior cuida de evitar obstáculos.
    • IDA * (Aprofundamento Iterativo) - Reduz o uso de memória em comparação com o A * comum, usando o aprofundamento iterativo.
    • SMA * (Limite da memória simplificado) - Utiliza apenas a memória disponível para realizar a pesquisa.
    • Jump Point Search - Créditos ao Eric nos comentários por mencioná-lo! Acelera a busca de caminhos em mapas de grade de custo uniforme ( link ).

Parte 2 - Representação do espaço de pesquisa

E, finalmente, para resolver esta questão:

Eu sei que A * é como o algoritmo a ser usado em jogos 2D. Isso é ótimo e tudo, mas e os jogos 2D que não são baseados em grade?

Dois grandes equívocos aqui! De fato:

  1. A * não se importa se o jogo é 2D ou 3D e é igualmente apropriado para os dois casos.
  2. A * funciona sob qualquer representação gráfica, portanto, não importa se o mundo é uma grade ou não.

Então, se o mundo não precisa ser uma grade, de que outras maneiras você pode representá-lo? Aqui está uma breve visão geral de maneiras de particionar o espaço mundial para busca de caminhos, e a maioria delas funciona tanto em 2D quanto em 3D:

  • Grade retangular - Divida o mundo em uma grade regular de quadrados, com cada célula na grade sendo um nó no gráfico, e a conexão entre dois nós desobstruídos é uma aresta.

    insira a descrição da imagem aqui

  • Quadtree - Outra maneira de particionar o espaço, mas em vez de particionar em uma grade de células de tamanho regular, particione em quatro e divida recursivamente cada uma delas em quatro novamente. Adicionar uma terceira dimensão torna uma octree .

    insira a descrição da imagem aqui

  • Polígonos convexos - Particionando a área passável em uma malha de polígonos convexos interconectados. Cada polígono se torna um nó e as arestas compartilhadas são as arestas do gráfico. Podem ser triângulos, por exemplo, e às vezes até ser uma malha criada por um artista ao criar os ativos de nível. Geralmente chamado de malha de navegação . Veja este link . Aqui está um conjunto de ferramentas de construção de malha de navegação muito popular: Reformulação .

    insira a descrição da imagem aqui

  • Pontos de visibilidade - A maneira mais comum é colocar um nó do lado de fora de cada um dos vértices convexos do obstáculo e conectar cada par de nós que possam se ver . Verifique este link . Os nós não precisam ser os vértices e podem ser colocados manualmente pelo designer no mapa. Nesse caso, o sistema é frequentemente referido como um gráfico de waypoint .

    insira a descrição da imagem aqui

David Gouveia
fonte
11
Dois links: 1) Mikko Mononen fez o trabalho de busca de caminhos Killzone 3 , e ele tem um blog muito bom, onde documenta o processo de desenvolvimento de Recast (gerador de navmesh) e Detour (kit de ferramentas de busca de caminhos), ambos sob licença MIT e usados ​​por exemplo em Reinos de Amalur: Reckoning . 2) A pesquisa de pontos de salto é, eu acho, um dos maiores desenvolvimentos recentes na busca de caminhos baseados em grade.
31412 Eric