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.
algorithm
path-finding
Daniel X Moore
fonte
fonte
Respostas:
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 é
A
e queremos encontrar o caminho mais curto paraF
. 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.Este é o nosso ponto de partida. Temos uma lista de nós para examinar, atualmente essa lista é:
A
tem um custo de0
, todos os outros nós são definidos como infinito (em uma implementação típica, isso seria algo parecidoint.MAX_VALUE
ou semelhante).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:e acompanhe o nó anterior (mostrado como uma pequena letra rosa abaixo do nó).
A
pode ser marcado como resolvido (vermelho) agora, para que não o visitemos novamente. Nossa lista de candidatos agora é assim:Novamente, pegamos o nó com o menor custo da nossa lista (
B
) e avaliamos seus vizinhos. O caminho paraD
é mais caro que o custo atual deD
, portanto, esse caminho pode ser descartado.E
será adicionado à nossa lista de candidatos, que agora se parece com isso:O próximo nó a examinar é agora
D
. A conexão comC
pode ser descartada, pois o caminho não é mais curto que o custo existente. Encontramos um caminho mais curto paraE
isso, portanto, o custoE
e o nó anterior serão atualizados. Nossa lista agora se parece com isso:Assim como fizemos antes, examinamos o nó com o menor custo da nossa lista, que é agora
E
.E
possui apenas um vizinho não resolvido, que também é o nó de destino. O custo para alcançar o nó de destino está definido como10
e seu nó anterior comoE
. Nossa lista de candidatos agora é assim:A seguir, examinamos
C
. Podemos atualizar o custo e o nó anterior paraF
. Como nossa lista agora temF
como 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 é:
Com A * é:
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.
fonte
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.
fonte
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.
fonte
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.
fonte
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.
fonte
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.
fonte
Em um nível abstrato, A * funciona assim:
fonte