Como o A * pathfinding funciona?

67

Eu gostaria de entender, em um nível fundamental, a maneira pela qual o A * pathfinding funciona. Qualquer implementação de código ou código psuedo, bem como visualizações, seria útil.

Daniel X Moore
fonte
Aqui está um pequeno artigo com um GIF animado que mostra o algoritmo de Dijkstra em movimento.
Ólafur Waage
As páginas A * de Amit foram uma boa introdução para mim. Você pode encontrar muitas visualizações boas pesquisando o algoritmo AStar no youtube.
jdeseno
Fiquei confuso com várias explicações sobre o A * antes de encontrar este ótimo tutorial: policyalmanac.org/games/aStarTutorial.htm Eu me referi principalmente a isso quando escrevi uma implementação do A * no ActionScript: newarteest.com/flash /astar.html
jhocking
4
-1 wikipedia tem artigo sobre A * com a explicação, o código fonte, visualização e ... . Algumas das respostas aqui têm links externos dessa página wiki.
user712092
4
Além disso, como esse é um assunto bastante complexo e de grande interesse para os desenvolvedores de jogos, acho que queremos as informações aqui. Lembro-me de Joel uma vez dizendo que ele quer que o StackOverflow seja o principal sucesso quando as pessoas pesquisam no Google sobre questões de programação.
22412 jhocking

Respostas:

63

aviso Legal

Existem vários exemplos de código e explicações sobre A * que podem ser encontrados online. Esta pergunta também recebeu muitas ótimas respostas com muitos links úteis. Na minha resposta, tentarei fornecer um exemplo ilustrado do algoritmo, que pode ser mais fácil de entender do que o código ou as descrições.


Algoritmo de Dijkstra

Para entender A *, sugiro que você dê uma olhada no algoritmo de Dijkstra . Deixe-me guiá-lo pelas etapas que o algoritmo de Dijkstra executará para uma pesquisa.

Nosso nó inicial é Ae queremos encontrar o caminho mais curto para F. Cada aresta do gráfico possui um custo de movimento associado (indicado como dígitos pretos ao lado das arestas). Nosso objetivo é avaliar o custo mínimo de viagem para cada vértice (ou nó) do gráfico até atingirmos o nó de meta.

Ilustrado de Dijkstra, parte 1

Este é o nosso ponto de partida. Temos uma lista de nós para examinar, atualmente essa lista é:

{ A(0) }

Atem um custo de 0, todos os outros nós são definidos como infinito (em uma implementação típica, isso seria algo parecido int.MAX_VALUEou semelhante).

Ilustrado de Dijkstra, parte 2

Pegamos o nó com o menor custo em nossa lista de nós (já que nossa lista contém apenas A, este é nosso candidato) e visitamos todos os seus vizinhos. Definimos o custo de cada vizinho para:

Cost_of_Edge + Cost_of_previous_Node

e acompanhe o nó anterior (mostrado como uma pequena letra rosa abaixo do nó). Apode ser marcado como resolvido (vermelho) agora, para que não o visitemos novamente. Nossa lista de candidatos agora é assim:

{ B(2), D(3), C(4) }

Ilustrado de Dijkstra, parte 3

Novamente, pegamos o nó com o menor custo da nossa lista ( B) e avaliamos seus vizinhos. O caminho para Dé mais caro que o custo atual de D, portanto, esse caminho pode ser descartado. Eserá adicionado à nossa lista de candidatos, que agora se parece com isso:

{ D(3), C(4), E(4) }

Ilustrado de Dijkstra, parte 4

O próximo nó a examinar é agora D. A conexão com Cpode ser descartada, pois o caminho não é mais curto que o custo existente. Encontramos um caminho mais curto para Eisso, portanto, o custo Ee o nó anterior serão atualizados. Nossa lista agora se parece com isso:

{ E(3), C(4) }

Ilustrado de Dijkstra, parte 5

Assim como fizemos antes, examinamos o nó com o menor custo da nossa lista, que é agora E. Epossui apenas um vizinho não resolvido, que também é o nó de destino. O custo para alcançar o nó de destino está definido como 10e seu nó anterior como E. Nossa lista de candidatos agora é assim:

{ C(4), F(10) }

Ilustrado de Dijkstra, parte 6

A seguir, examinamos C. Podemos atualizar o custo e o nó anterior para F. Como nossa lista agora tem Fcomo nó com o menor custo, estamos prontos. Nosso caminho pode ser construído retornando os nós mais curtos anteriores.


Algoritmo A *

Então você pode se perguntar por que expliquei o Dijkstra para você, em vez do algoritmo A * ? Bem, a única diferença está em como você avalia (ou classifica) seus candidatos. Com Dijkstra é:

Cost_of_Edge + Cost_of_previous_Node

Com A * é:

Cost_of_Edge + Cost_of_previous_Node + Estimated_Cost_to_reach_Target_from(Node)

Onde Estimated_Cost_to_reach_Target_fromé comumente chamada de função heurística . Essa é uma função que tentará estimar o custo para alcançar o nó de destino. Uma boa função heurística conseguirá que menos nós sejam visitados para encontrar o alvo. Embora o algoritmo de Dijkstra se expanda para todos os lados, A * procurará (graças à heurística) na direção do alvo.

A página de Amit sobre heurísticas tem uma boa visão geral sobre heurísticas comuns.

bummzack
fonte
2
Vale ressaltar que a heurística nem sempre pressiona a pesquisa para encontrar o melhor caminho. Por exemplo, se sua heurística estiver à distância do alvo, mas a rota viável estiver ao redor da borda do mapa - a pesquisa nesse caso pesquisará todo o mapa antes de seguir a rota correta. Certamente então, você deve estar pensando, há algo que eu não entendo? Isso não funciona! - o que é preciso entender é que o objetivo de uma heurística é reduzir a pesquisa na maioria dos casos, e seu trabalho é encontrar uma que seja a 'melhor' de todas as soluções disponíveis para suas necessidades específicas.
22812 SirYakalot
2
@AsherEinhorn Ainda será melhor (ou, no pior dos casos, igual) do que uma pesquisa desinformada como a de Djikstra.
bummzack
sim sim, você está absolutamente certo. Talvez eu não tenha ficado claro, o exemplo de que falei no comentário acima é um senário teórico de 'pior caso' para A * com essa heurística, MAS é o que Dijkstra faria TODA vez. Na maioria das vezes, o A * será melhor, mesmo com uma heurística muito simples. Meu argumento foi que a heurística pode ser confusa no início, porque 'distância ao alvo' nem sempre faz sentido para todos os cenários - o ponto é que sim para a maioria.
13269 SirYakalot
Além disso, veja o seguinte: qiao.github.io/PathFinding.js/visual
David Chouinard
Essa resposta poderia mencionar o que torna uma heurística admissível, no sentido de garantir que A * encontre o caminho mais curto. (Resumidamente: para ser admissível, a heurística nunca deve superestimar a distância real do alvo. Às vezes, heurísticas não admissíveis podem ser úteis, mas podem fazer com que A * retorne caminhos
abaixo do
26

Uma descoberta de caminho * é a melhor pesquisa de tipo que usa uma heurística adicional.

A primeira coisa que você precisa fazer é dividir sua área de pesquisa. Para esta explicação, o mapa é uma grade quadrada de peças, porque a maioria dos jogos 2D usa uma grade de peças e porque é simples de visualizar. Observe, no entanto, que a área de pesquisa pode ser dividida da maneira que você desejar: uma grade hexagonal, talvez, ou mesmo formas arbitrárias como Risco. As várias posições do mapa são chamadas de "nós" e esse algoritmo funcionará sempre que você tiver vários nós para atravessar e tiver conexões definidas entre os nós.

De qualquer forma, começando em um determinado bloco inicial:

  • As 8 peças ao redor da peça inicial são "pontuadas" com base em a) o custo da mudança da peça atual para a peça seguinte (geralmente 1 para movimentos horizontais ou verticais, sqrt (2) para movimento diagonal).

  • Cada bloco recebe uma pontuação "heurística" adicional - uma aproximação do valor relativo de se mover para cada bloco. Diferentes heurísticas são usadas, sendo a mais simples a distância em linha reta entre os centros do ladrilho fornecido e do ladrilho final.

  • O bloco atual é então "fechado" e o agente se move para o bloco vizinho aberto, possui a menor pontuação de movimento e a menor pontuação heurística.

  • Esse processo é repetido até que o nó de objetivo seja atingido ou que não haja mais nós abertos (o que significa que o agente está bloqueado).

Para diagramas que ilustram essas etapas, consulte este tutorial para iniciantes .

Existem algumas melhorias que podem ser feitas, principalmente na melhoria da heurística:

  • Levando em consideração as diferenças de terreno, aspereza, inclinação, etc.

  • Às vezes, também é útil fazer uma "varredura" pela grade para bloquear áreas do mapa que não são caminhos eficientes: uma forma de U voltada para o agente, por exemplo. Sem um teste de varredura, o agente entra primeiro no U, vira-se, depois sai e contorna a borda do U. Um agente inteligente "real" anotaria a armadilha em forma de U e simplesmente a evitaria. A varredura pode ajudar a simular isso.

Sean James
fonte
11
Uma explicação com gráfico, nós, arestas seria mais clara do que apenas sobre blocos. Não ajuda a entender que, independentemente da estrutura de espaço do seu jogo, você pode aplicar o mesmo algoritmo, desde que tenha informações de posições interligadas neste espaço.
Klaim
Eu argumentaria que seria menos claro, na verdade, porque é mais difícil de visualizar. Mas sim, essa explicação deve mencionar que não é necessária uma grade de blocos; na verdade, eu vou editar esse ponto.
jhocking
14

Está longe de ser o melhor, mas essa é uma implementação que eu fiz do A * em C ++ há alguns anos atrás.

Provavelmente é melhor que eu aponte para você recursos do que tentar explicar todo o algoritmo. Além disso, ao ler o artigo da wiki, brinque com a demonstração e veja se consegue visualizar como ela está funcionando. Deixe um comentário se você tiver uma pergunta específica.

  1. A * na Wikipedia
  2. Uma demonstração Java *
David McGraw
fonte
4
Seu exemplo de Python está em C ++.
Buns of Aluminum
@finish - É bom ver alguém pegar isso! Atualmente, as atividades diárias giram em torno do Python. Obrigado!
David McGraw
3
Seu C ++ exemplo poderia muito bem ser C.
deceleratedcaviar
4
O exemplo também pode estar no assembler para toda a estrutura que possui. Não é nem A *, como essa é a resposta aceita?
4
Desculpe, não cabe a todos, foi uma das minhas primeiras tentativas de codificação quando comecei. Sinta-se à vontade para contribuir com algo para os comentários / editar a postagem para compartilhar sua própria solução.
David McGraw
6

Você pode achar útil o artigo do ActiveTut sobre Localização de caminho . Ele aborda o algoritmo de A * e de Dijkstra e as diferenças entre eles. É voltado para desenvolvedores de Flash, mas deve fornecer algumas boas informações sobre a teoria, mesmo se você não usar o Flash.

VirtuosiMedia
fonte
4

Uma coisa que é importante visualizar ao lidar com o A * e o algoritmo de Dijkstra é que o A * é direcionado; ele tenta encontrar o caminho mais curto para um ponto específico "adivinhando" em qual direção procurar. O algoritmo de Dijkstra encontra o caminho mais curto para / every / point.

Karantza
fonte
11
Esta não é realmente uma descrição precisa da diferença entre A * e Dijkstra. É verdade que o Dijkstra resolve a fonte única para todos os pontos, mas quando usado em jogos, geralmente é cortado assim que você encontra o caminho para o gol. A diferença real entre os dois é que A * é informado pela heurística e pode encontrar esse objetivo com menos ramificações.
Para acrescentar à explicação de Joe: A * também encontrará o caminho para todos os pontos, se você permitir, mas em jogos geralmente queremos parar mais cedo. A * funciona como o algoritmo de Dijsktra, exceto que a heurística ajuda a reordenar os nós para explorar os caminhos mais promissores primeiro. Dessa forma, você geralmente pode parar ainda mais cedo do que com o algoritmo de Dijkstra. Por exemplo, se você deseja encontrar um caminho do centro do mapa para o lado leste, o algoritmo de Dijkstra explorará igualmente em todas as direções e parará quando encontrar o lado leste. A * passará mais tempo indo para o leste do que para o oeste e chegando mais cedo.
Amitp
3

Assim, apenas como uma primeira afirmação, A * está no coração de um algoritmo de exploração de gráficos. Geralmente, nos jogos, usamos peças ou outra geometria do mundo como gráfico, mas você pode usar A * para outras coisas. Os dois algoritmos ur para a travessia de gráfico são a pesquisa de profundidade primeiro e a pesquisa de largura primeiro. No DFS, você sempre explora completamente sua ramificação atual antes de olhar para os irmãos do nó atual e, no BFS, sempre olha para os irmãos primeiro e depois para os filhos. A * tenta encontrar um meio termo entre eles, onde você explora um ramo (mais parecido com o DFS) quando está mais perto do objetivo desejado, mas às vezes para e tenta um irmão se ele tiver melhores resultados em seu ramo. A matemática real é que você mantenha uma lista de possíveis nós para explorar a seguir, onde cada um tem uma "bondade" pontuação indicando quão próximo (em algum sentido abstrato) está do objetivo, pontuações mais baixas sendo melhores (0 significaria que você encontrou o objetivo). Você seleciona qual usar a seguir, localizando o mínimo da pontuação mais o número de nós distantes da raiz (que geralmente é a configuração atual ou a posição atual na busca de caminhos). Cada vez que você explora um nó, adiciona todos os seus filhos a esta lista e escolhe o novo melhor.

coderanger
fonte
3

Em um nível abstrato, A * funciona assim:

  • Você trata o mundo como um número discreto de nós conectados, por exemplo. uma grade ou um gráfico.
  • Para encontrar um caminho através desse mundo, você precisa encontrar uma lista de 'nós' adjacentes nesse espaço, levando desde o início até a meta.
  • A abordagem ingênua seria a seguinte: calcule todas as permutações possíveis de nós que começam com o nó inicial e terminam no nó final e escolha o mais barato. Obviamente, isso levaria uma eternidade em todos os espaços, exceto nos menores.
  • Portanto, abordagens alternativas tentam usar algum conhecimento sobre o mundo para adivinhar quais permutações valem a pena considerar primeiro e para saber se uma determinada solução pode ser vencida. Essa estimativa é chamada de heurística.
  • A * requer uma heurística admissível . Isso significa que nunca superestima.
    • Uma boa heurística para os problemas de localização de caminhos é a distância euclidiana, porque sabemos que o caminho mais curto entre 2 pontos é uma linha reta. Isso nunca superestima a distância em simulações do mundo real.
  • A * começa com o nó inicial e tenta permutações sucessivas desse nó mais cada vizinho e vizinhos do vizinho etc., usando a heurística para decidir qual permutação tentar a seguir.
  • A cada etapa, A * examina o caminho mais promissor até agora e escolhe o próximo nó vizinho que parece ser o "melhor", com base na distância percorrida até o momento e a estimativa da heurística de quão longe ainda resta desse percurso nó.
  • Como a heurística nunca superestima e a distância percorrida até agora é conhecida por ser precisa, ela sempre escolherá o próximo passo mais otimista.
    • Se o próximo passo atingir a meta, você sabe que encontrou a rota mais curta desde a última posição, porque esse foi o palpite mais otimista dos válidos restantes.
    • Se não alcançou a meta, é deixado como um ponto possível para explorar mais tarde. O algoritmo agora escolhe a próxima possibilidade mais promissora, portanto a lógica acima ainda se aplica.
Kylotan
fonte