3 - Caminho eficaz: Algoritmo A*

Ehr... sem pressão.

O algoritmo A* é um dos mais utilizados em situações de pathfinding, ou busca de caminhos. Ele otimiza o algoritmo de Dijkstra em dois aspectos para tornar o seu funcionamento mais eficiente:

• Ele utiliza uma estrutura de dados chamada Fila de prioridade para organizar os vértices que serão explorados;
• Além de salvar os caminhos já calculados (como Dijkstra faz), ele também utiliza heurísticas para estimar em cada ponto quanto ainda falta para o final, buscando direcionar a escolha do próximo vértice.

A ideia do algoritmo é tentar acertar o menor caminho o mais rápido possível! Por isso ele olha tanto para o passado (o quanto ele já percorreu) como para o futuro (o quanto ainda falta) na hora de estimar se um caminho é bom ou não. Calma, não estou dizendo que ele acerta de primeira, mas ele converge para o menor caminho muito mais rápida e precisamente do que Dijkstra ou as buscas por DFS e BFS conseguem fazer. De certa forma, esse algoritmo é uma combinação das duas abordagens que foram apresentadas nas seções anteriores dessa aula, utilizando o que há de melhor em cada um dos métodos.

Por convergir mais rápido, o algoritmo A* acaba explorando menos vértices para achar a solução, e consequentemente possui uma performance melhor (por isso o povo de jogos usa bastante ele!). Se você não usar nenhuma heurística para mensurar o caminho para a frente do vértice atual, estará olhando apenas o caminho já percorrido, e o algoritmo se iguala ao de Dijkstra.

Você deve estar se perguntando: o que é uma Fila de prioridade? É a mesma estrutura que eu já estudei?

Não! Essa seria uma estrutura de dados nova. Nessa estrutura, foi definido um critério de prioridade, e os elementos que mais atendem esse critério são os primeiros a serem acessados em uma consulta à estrutura. Por exemplo, se for definida uma Fila de prioridade para valores inteiros, e que o critério é o menor valor, então o menor valor existente entre os elementos da Fila será o primeiro a ser acessado em uma consulta. Independentemente da sequência em que você realiza a inserção dos valores, o menor valor sempre será o primeiro a sair da Fila. Ou seja, o menor critério sempre fura para o começo da fila, porque tem a prioridade, captaram?

A implementação desse tipo de estrutura exigiria que você tivesse estudado outras estruturas, como a heap… então essa parte eu vou abstrair. Tudo o que você precisa saber é que, numa Fila de prioridade eu sempre consigo pegar o menor elemento de acordo com o meu critério de forma imediata, ok?

Com esses elementos em mente, o pseudocódigo do A* pode ser descrito como no código abaixo.

Perceba que o código fica um pouco mais complexo na medida em que você adiciona as otimizações. Que tal uma simulação com o exemplo dos casos anteriores, para você poder visualizar melhor o funcionamento do algoritmo?

O bom e velho mapa!

O primeiro passo é processar o vértice inicial e calcular os primeiros valores. Como heurística, resolvi fazer esse com a distância Euclidiana, que é uma heurística bastante utilizada em diversas aplicações da computação. A conta fica um pouquinho maior, mas como quem vai fazer é o computador, então tá tudo tranquilo.

Lembrando: a posição do destino é (4,8) e a de partida do jogador é (4,1). Todas as contas de coordenadas são feitas da posição do vértice com a posição do destino, ok?

Aqui serão dois conjuntos de valores calculados para cada um dos vértices: Denomine de C o valor do caminho percorrido até o vértice, e F o valor estimado do restante do caminho a partir do vértice. O custo de movimentação C é unitário, então você precisa fazer a conta do valor da heurística para somar com esses custos:

F(4,1) = RAIZ_QUADRADA(0 + 49) + C(4,1) = 7 + 0 = 7
F(3,1) = RAIZ_QUADRADA(1 + 49) + C(3,1) = 7.07 + 1 = 8.07
F(3,2) = RAIZ_QUADRADA(1 + 36) + C(3,2) = 6.08 + 1 = 7.08
F(4,2) = RAIZ_QUADRADA(0 + 36) + C(4,2) = 6 + 1 = 7
F(5,1) = RAIZ_QUADRADA(1 + 49) + C(5,1) = 7.07 + 1 = 8.07
F(5,2) = RAIZ_QUADRADA(1 + 36) + C(5,2) = 6.08 + 1 = 7.08

Entendeu a ideia? Cada vértice vai ter duas informações: C e F.

A partir desse ponto, escolhe-se sempre o vértice que tiver o menor F como o próximo a ser explorado. Em caso de empate, vai ser o primeiro que foi adicionado na fila.

Valide as contas do valor de F, para ver se você está seguro:

F(3,3) = RAIZ_QUADRADA(1 + 25) + C(3,3) = 5.09 + 2 = 7.09
F(4,3) = RAIZ_QUADRADA(0 + 25) + C(4,3) = 5 + 2 = 7
F(5,3) = RAIZ_QUADRADA(1 + 25) + C(5,3) = 5.09 + 2 = 7.09

A partir daqui vou colocar as contas dos passos diretamente, mas você pode fazer a conta para validar, certo?

Esse vértice não tem vizinhos para atualizar: ou o caminho a partir dele fica pior, ou o vizinho já foi visitado. Você irá só processá-lo e seguir para o próximo menor F!

Quase lá! Substitui a figura da nave pelos valores que são calculados para o vértice destino, para mostrar que ele seria a escolha certa ao final do algoritmo.

Chegou!Ufa, 20 passos para convergir para o menor caminho.

Eu não adicionei a informação do mapa anterior nessa imagem, mas o caminho traçado como menor foi o seguinte:

Não deixe a quantidade de imagens lhe enganar: o algoritmo A* convergiu para o menor caminho após explorar 20 vértices. Eu não coloquei todos do Dijkstra, mas contei aqui: foi necessário explorar 35, quase o dobro para achar o caminho! Isso é uma pequena mostra de como esse algoritmo consegue aumentar a performance de execução mantendo a corretude do caminho encontrado. Mas é claro, tanto o meu nome como o dele começam com a mesma letra.

E é com esse assunto que encerro o estudo do conteúdo de IA para jogos.

É, eu também fico sentimental nessas horas…

Eu sei que alguns assuntos podem parecer muito complexos à primeira vista, mas lembre-se: para alguns dos tópicos da disciplina já existem ferramentas prontas, e você entender como elas funcionam, para quais situações são adequadas e a forma de utilizar já é metade do caminho andado!

E quem sabe alguns dos assuntos da disciplina tenham despertado seu interesse para outras áreas também. Que o conhecimento aqui sirva de plataforma para você progredir ainda mais como programador.

Até uma próxima aula! (Essa não é a última? )