A* PathFinding

 O A* PathFinding é um algoritmo de Busca de caminho, é usado em jogos, esse algoritmo é considerado o melhor algoritmo de PathFinding existente atualmente.

Vamos ver como ele funciona, temos esse Zumbi que precisa chegar até o cérebro.

O que o Algoritmo em questão vai fazer é encontrar o menor caminho possível.

Ele usa essa formula abaixo

F = G + H

Esse algoritmo possui 2 Listas: Aberta e Fechada, Tais listas representam respectivamente os pontos da grid que ainda não foram analisados e os que ainda serão analisados.

No inicio o nó inicial (posição do zumbi é adicionado a lista Aberta).

Nesse Algoritmo tem um loop, e a cada iteração desse loop, o nó com menor F, será removido da lista Aberta e adicionado na lista Fechada. (esse nó que será adicionado na lista Fechada, chamamos de nó atual)

INICIO DA ITERAÇÃO

(então na primeira iteração o nó inicial é adicionado na lista fechada e vira o nó atual)

Em seguida é feito o Calculo dos F, G e H de todos os nós vizinhos do nó atual

Propriedade G

O G representa o Custo de movimento do nó atual até o nó a ser calculado, nesse contexto da imagem representa a distancia (ali a distancia foi multiplicada por 10 e arredondada para usar menos processamento), mas também poderia representar o tempo que leva para se mover, ou o consumo de combustível por exemplo.

OBS: caso o nó tenha um nó pai o G será a soma do G do nó + o G do nó pai.

Propriedade H

O H representa a distancia estimada do nó até o destino. nesse exemplo ele usou o método manhattan que não considera as diagonais, ele calculou a distancia no eixo X e Y separadamente e depois as somou (ele multiplicou por 10, já que ele também fez isso com o G).

(usando o método manhattan nem sempre o algoritmo vai encontrar o caminho mais curto)

OBS: na hora de calcular a distancia no manhattan funciona da seguinte forma abs(x - xFinal) + abs(y - yFinal), o abs é obrigatório para tratar os números negativos, sem abs tende a formar escadinhas.

OBS²: você pode pegar o H e multiplicar por uma variável "peso", isso vai aumentar a influencia do H na variável F

Propriedade F

Depois é só calcular o F, de acordo com a formula do inicio.

Também deve ser armazenado qual é o nó pai de cada nó analisado.

E o nó com menor F se torna o nó atual, e o loop chama a próxima iteração

FIM DA ITERAÇÃO

O loop só termina em 2 cenários:

• Quando o Destino é colocado na lista Fechada
• Quando a Lista Aberta fica vazia. (não há caminho possível)

 OBS: nós com obstáculos são ignorados.

Depois que se chega ao destino, basta ir seguindo a trilha de nós pai, e você vai ter o caminho a ser seguido para chegar ao objetivo.

PathFinding DEMO