Se você é um desenvolvedor de jogos, você pode sempre ter querido implementar A* como um character (ou inimigo) pathfinding. Eu sei que há alguns anos atrás eu queria, mas com meu nível de programação na época eu tinha problemas com os artigos atuais lá fora. Eu queria escrever isso como uma introdução fácil com um exemplo claro de código fonte para A* pathfinding para que qualquer um possa facilmente pegá-lo e usá-lo em seu jogo.
Um aspecto importante de A* é f = g + h. As variáveis f, g e h estão em nossa classe Node e são calculadas toda vez que criamos um novo nó. Rapidamente vou rever o significado dessas variáveis.
- F é o custo total do nó.
- G é a distância entre o nó atual e o nó inicial.
- H é a distância heurística – distância estimada entre o nó atual e o nó final.
Vamos ver um gráfico rápido para ajudar a ilustrar isto.
Fantástico! Digamos que node(0) é a nossa posição inicial e node(19) é a nossa posição final. Digamos também que o nosso nó atual está no quadrado vermelho node(4).
G
G é a distância entre o nó atual e o nó inicial.
Se contarmos para trás podemos ver que node(4) está a 4 espaços do nosso nó inicial.
Também podemos dizer que G é 1 a mais do que o nosso nó pai (node(3)). Então neste caso para node(4), currentNode.g = 4.
H
H é a distância heurística – estimada do nó atual até o nó final.
Então vamos calcular a distância. Se dermos uma olhada veremos que se ultrapassarmos 7 espaços e subirmos 3 espaços, chegamos ao nosso nó final (node(19)).
Vamos aplicar o Teorema de Pitágoras! a² + b² = c². Depois de aplicarmos isto, vamos ver que currentNode.h = 7² + 3². Ou currentNode.h = 58.
Mas não temos de aplicar a raiz quadrada a 58? Não! Podemos saltar esse cálculo em cada nó e ainda assim obter a mesma saída. Esperto!
Com um heurístico, precisamos ter certeza de que podemos realmente calculá-lo. É também muito importante que a heurística seja sempre uma subestimação do caminho total, pois uma superestimação levará a A* procurar por nós que podem não ser os ‘melhores’ em termos de f valor.
F
F é o custo total do nó.
Então vamos somar h e g para obter o custo total do nosso nó. currentNode.f = currentNode.g + currentNode.h. Ou currentNode.f = 4+ 58. Ou currentNode.f = 62.
Tempo para usar f = g + h
Muito trabalho. Agora com todo esse trabalho, para que vou usar este f valor para?
Com este novo f valor, podemos olhar para todos os nossos nós e dizer: “Ei, este é o melhor nó que eu posso escolher para seguir em frente agora? Em vez de correr através de cada nó, podemos escolher os que têm mais chances de nos levar ao nosso objetivo.
Aqui está um gráfico para ilustrar. No topo, temos o Algoritmo de Dijkstra, que procura sem este f valor, e abaixo temos A* que usa este f valor.
Algoritmo de Dijkstra
Então dê uma olhada no algoritmo de Dijkstra, vemos que continua a procurar. Ele não tem idéia de qual nó é ‘melhor’, então ele calcula caminhos para todos eles.
A* Algoritmo
Com A*, vemos que uma vez que passamos o obstáculo, o algoritmo prioriza o nó com a menor f e a ‘melhor’ chance de chegar ao fim.