Entendendo de vez o PathFinding A*

Estudar e tentar entender algoritmos de programação é sempre um desafio e tanto. Nos últimos dias resolvi desenvolver um jogo em HTML 5 e typescript. Mas aí você deve estar se perguntando: "Por que raios alguém teria motivação de escrever um jogo do zero?"

A resposta é simples: adquirir conhecimento e resolver desafios.

Sim! O processo de criação de um jogo envolve vários desafios e problemas, que precisam ser resolvidos usando lógica de programação e organização.

Como servidor estou usando o NodeJS e MySQL de banco de dados. A conexão entre cliente e servidor é feita através do Websocket nativo do Javascript e vem funcionando muito bem para fins didáticos.

Enquanto escrevia este jogo, me deparei com o seguinte problema: imagine que você precisa calcular o menor caminho do ponto A para o ponto B, desviando de colisões e objetos no mapa… Ficou difícil de imaginar? Tudo bem.. Desenhar é sempre mais fácil.

Considere o seguinte mapa abaixo.

Mapa

Agora imagine que queremos chegar do quadrado verde até o quadrado azul, pulando de nó em nó (é assim que vamos chamar cada 'célula’ do mapa). Imagine também que os nós na cor cinza são obstáculos, a qual devemos evitar, ou seja, só podemos andar em quadrados da cor branca.

Uma das formas de calcular esse caminho é usando um algoritmo chamado A* (ou A Estrela, no bom e velho pt-BR).

Para entender como esse algoritmo funciona, vamos simplificar nosso mapa, usando como exemplo o mapa abaixo.

Tomando por base as coordenadas X, indo de 0 à 8 e Y de 0 à 6, podemos afirmar que o nó verde (ponto de partida) está na posição x = 1 e y = 1, e que o nó azul (destino) está na posição x = 6 e y = 1.

Com essas informações, já podemos começar a entender como o algoritmo funciona, então vamos nessa…

Entendendo o algoritmo

A melhor forma de entender o algoritmo é separa-lo por partes.

Imagine que você está no nó de partida (1,1) e você quer ir para o nó de destino (6,1).

O primeiro passo é considerar o nó de partida (1,1) como nó atual.

Tendo esse nó como base, devemos então pegar todas as opções de nós que você pode ir, a partir dali. Para facilitar, vamos ignorar caminhos diagonais. Sendo assim, temos como possibilidades o nó de cima (1,0), o nó da direita (2,1), o nó debaixo (1,2) e o nó da esquerda (0,1) conforme vemos na cor verde clara na imagem abaixo.

Mapa com os nós mais próximos do nó de início destacados em verde claro.

Agora, como saber para qual nó devemos ir, vamos entender alguns conceitos desse algoritmo.

Cada nó carrega consigo algumas informações. São elas:

  • Custo
  • G
  • H
  • F
  • Parent
  • Posição

Vamos um por um…

Custo: o custo é o preço a ser pago para que a gente possa ir de um nó para outro. Por exemplo, imagine que estamos na cidade A, e num fim de semana queremos visitar uma outra cidade, para conhecer… ao olhar o mapa eu vejo que todas as cidades que estão na direção ortogonal (em cima, na direita, embaixo ou na esquerda) da minha cidade estão a 10 km de distância. Ou seja, o custo para ir para alguma cidade na ortogonal é de 10 km. De forma semelhante, imagine também que, para ir para uma cidade que fica na posição diagonal, com relação a nossa cidade A, a distância seja de 14 km. Então o custo para estas cidades na diagonal seria de 14 km.

G: O g é a somatória de todos os custos até o momento. Para entender melhor, vamos supor que decidimos ir para a cidade de cima, que tem custo igual a 10. Então o G do nó de cima do nosso, cidade a qual estamos indo, será 0 (custo do nó atual) + 10 (custo do nó destino). G = 10.

H: É a estimativa do quanto ainda falta para chegar, a partir da cidade vizinha, até a cidade destino (que no nosso caso é o nó azul). Novamente vamos usar a cidade de cima como referência. A cidade de cima da nossa está na coordenada 1,0 (em x,y). Para chegar na cidade azul, temos que andar até 6,1. Então se subtrair 6 (x da cidade destino) de 1 (x da cidade do norte), e somar com 1 (y da cidade destino)- 0 (y da cidade destino) temos que H será igual a 6. Veja na formula abaixo para ficar mais fácil:

H = Math.abs(destino.x-norte.x) + Math.abs(destino.y-norte.y);
H = Math.abs(6–1) + Math.abs(1–0)
H = 6

F: aqui apenas somamos o G + H, ou seja, o custo agregado que é o quanto já andamos + a estimativa do quanto ainda falta andar. No caso do nó de cima temos:

F = G + H
F = 10 + 6
F = 16

Posição: Aqui apenas armazenamos a posição do nó. No caso do nó de cima é x = 1, y = 0;

Parent: Por fim, no parent armazenamos o nó que foi a origem para o nó em questão. Então, se a gente for da nossa cidade para a cidade de cima, temos como parent da cidade de cima a nossa cidade. Melhor dizendo, se estamos indo de A para B, então A é parent de B. Se for de B para C, então o parent de C é B, que por sua vez tem A como parent, ficando A -> B -> C.

Tendo essas informações em mãos, devemos então adicionar esses nós (as cidades a qual podemos ir) em uma lista, que chamamos de lista aberta.

Essa lista contém os nós que podemos ir a partir do nó atual.

Em seguida ordenamos a lista de acordo com o F de cada nó, assim o nó que tem o menor F ficará na posição 0 da lista, e o nó com o maior F ficará em último na lista.

Com a lista ordenada em mãos, agora sim podemos saber qual o nó que custa menos para podermos ir. Este será o nó na posição zero.

Retiramos esse nó da lista aberta a adicionamos em uma outra lista chamada lista fechada. Esta lista conterá todos os nós que já passamos. Essa lista serve para saber quais nós já passamos. Ou seja, se estamos no nó inicial (1,1) então esse nó está na lista fechada. Se a gente passar do nó inicial (1,1) para o nó de cima (1,0) então o nó inicial (1,1) e o nó de cima (1,0) estarão na lista de nós fechados. Assim sabemos que não podemos mais ir do nó de cima (1,0) de volta para o nó inicial (1,1).

Esse processo se repete até que o nó atual seja igual ao nó destino, e então sabemos o caminho até o destino.

Implementando o código

Vamos implementar o código, parte por parte, conforme dito anteriormente.

A implementação exibida acima está hospedada no JSFiddle e lá fica mais fácil de ver ela funcionando.

LEMBRE-SE: Leia os comentários do código, pois o código está todo comentado, detalhadamente. Isso irá clarear sua interpretação. ;)


Enfim… Espero que eu tenha conseguido passar para o leitor, de forma clara e simples, como funciona esse algoritmo de suma importância e que pode ser aplicado em várias situações cotidianas.

Caso você tenha alguma dúvida, comente no texto e tentarei responder da melhor forma possível.

Até a próxima!