Que algoritmos de localização de caminhos existem? [fechadas]

Eu gostaria de ler sobre os algoritmos de localização de caminhos. Existe uma cartilha disponível ou algum material ou tutorial na Internet que seria um bom começo para mim?

Se você deseja pesquisar e aprender sobre a busca de caminhos em geral, eu definitivamente sugeriria aprender mais do que apenas um algoritmo. Você desejará entender os conceitos gerais, mas poderá aplicá-los ao que quer que esteja trabalhando. A maioria dos desenvolvedores de jogos que precisam realizar qualquer busca de caminhos séria acaba escrevendo seus próprios algoritmos personalizados, embora altamente baseados em soluções conhecidas, cada jogo seja diferente e terá requisitos diferentes.

Eu começaria lendo alguns dos métodos mais conhecidos, como o A *, o algoritmo de Dijkstra, a profundidade e a largura da primeira pesquisa. Há muitas informações boas na internet em cada uma delas. ( http://en.wikipedia.org/wiki/Pathfinding )

Ao lê-los, anote quais são as vantagens e desvantagens de cada abordagem, bem como o tipo de dados em que o algoritmo pode operar. Pode ser aplicado a caminhos tridimensionais? Ele pode ser modificado para dar conta de nossa IA humana que deseja evitar as minas terrestres no mapa?

Quando se trata de busca de caminhos, A * é praticamente o bilhete de ouro que todo mundo usa. Você definitivamente deve saber como isso funciona. ( http://en.wikipedia.org/wiki/A*_search_algorithm )

Aqui está um bom exemplo de A *, como se aplica a um jogo RTS, que precisa levar em consideração entidades de tamanhos diferentes: http://aigamedev.com/open/tutorials/clearance-based-pathfinding/

Boa sorte!

Os algoritmos de busca de caminhos são basicamente algoritmos de resolução de problemas de pesquisa de gráficos.

http://en.wikipedia.org/wiki/Pathfinding#Algorithms

O mais conhecido é o algoritmo de Djikstra: http://en.wikipedia.org/wiki/Dijkstra's_algorithm

e seu algoritmo de pesquisa variante A *: http://en.wikipedia.org/wiki/A*

Este é um excelente recurso inicial que analisa todos os aspectos da localização de caminhos em uma abordagem muito fácil de digerir.

Notas de Amit sobre localização de caminhos

... O Pathfinding aborda o problema de encontrar um bom caminho desde o ponto de partida até a meta - evitando obstáculos, evitando inimigos e minimizando custos (combustível, tempo, distância, equipamento, dinheiro, etc.). O movimento aborda o problema de seguir um caminho e segui-lo. É possível gastar seus esforços em apenas um deles. Em um extremo, um pathfinder sofisticado acoplado a um algoritmo de movimento trivial ...

A busca de caminhos é um problema bastante resolvido ... como mencionado em quase todas as respostas aqui, algumas variações do A * serão o que você usar.

O maior desafio para mim é como você deseja representar seu caminho . Usando uma grade, códigos de caminho, navmeshes, grades hierárquicas ou outras estruturas complexas, etc.

Não tenho nenhuma referência específica em mente, mas explorar o AIGameDev fornecerá todo tipo de idéias sobre o que há por aí.

Lembre-se de que cada representação tem seus prós e contras; não se trata de encontrar o 'melhor', é de encontrar o que melhor se adequa à sua jogabilidade .

Há uma boa lista na Wikipedia: Pathfinding

Tanto quanto eu sei, A * e D * são ambos bastante populares.

Existem vários algoritmos de localização de caminhos por aí.

Um dos mais populares é provavelmente o A * ( A-Star ). É um algoritmo muito útil se você tiver uma função heurística que possa fornecer custos estimados para atingir uma meta (por exemplo, a distância da linha de visão até o destino). A * é muito útil para encontrar o caminho mais curto do início ao fim.

Fora isso, também há o algoritmo de Dijkstra, que é muito útil para encontrar o item mais próximo dentre vários itens. Por exemplo. se você quiser descobrir qual power-up (ou similar) é o mais próximo ao seu personagem de jogo.

Existem vários outros algoritmos por aí, mas acho que A * é de longe o mais popular. Mat Buckland tem um excelente capítulo sobre Localização de caminhos em seu Game Programming Game AI by Example . Convido você a obter uma cópia. Caso contrário, você encontrará muitas informações on-line pesquisando "Uma pesquisa por estrelas".

Aqui está um tutorial sobre como usar o algoritmo de Dijkstra para encontrar caminhos.

Aqui está um bom exemplo de A * sendo usado em um jogo com algum código psuedo: http://www.anotherearlymorning.com/2009/02/pathfinding-with-a-star/

Isso não é muito primer, mas discutimos extensivamente os algoritmos de gráficos em nossa classe de algoritmos no outono passado de 2009. Usamos este livro,

Introdução aos algoritmos, terceira edição de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein

http://mitpress.mit.edu/algorithms/

e também acompanha palestras do YouTube de uma aula do MIT.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/

Os capítulos 17, 18 e 19 tratam dos caminhos mais curtos.

Consulte [Algoritmos de pesquisa de gráfico e árvore] na Wikipedia 1 . Eles são basicamente apenas uma variação da Pesquisa no Espaço de Estado. Você apenas precisa examinar todas elas e descobrir onde elas diferem.

Há também Difusão Colaborativa , que é um dos algoritmos mencionados anteriormente, de maneira interessante.

Este parece interessante:

http://www.codeproject.com/Articles/455 Gostaria de saber se é melhor que A *?