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?

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.

  

• 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 .

  

• 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 .

  

• 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 .