Algoritmo A* (A-estrela)

Algoritmo que busca o caminho com o menor custo entre dois pontos. É usado em jogos e aplicativos de navegação para calcular a menor distância possível.

Categoria de Programação

Postado em 09 março 2023

Atualizado em 09 março 2023

Palavras-chave: algoritmo,busca,linear,binario,binaria,estrela,asterisco,aplicativo,distancia,caminho,calculo

Visualizações: 3922



O contexto que um programa de computador roda, afeta diretamente o tipo de algoritmo que será implementado. Uma simples tarefa como a busca de algum elemento dentro de uma lista pode ser realizada usando métodos de busca linear. Porém, programas que necessitam de mais eficiência podem optar pela busca binária.

Conforme o contexto do programa muda, os algoritmos precisam ser adaptados. Em aplicativos de navegação ou em jogos, algoritmos de busca também são implementados para encontrar o caminho mais curto entre dois objetos, como a distância atual do usuário até um determinado objeto. Um algoritmo bastante eficiente para encontrar o menor caminho entre dois pontos é o algoritmo A*.

O que é o algoritmo A*?

O algoritmo A-estrela é um método que busca o caminho mais curto entre dois pontos. Esse método usa os valores de duas funções para estimar o melhor caminho em relação ao custo, cujos valores são o G e o H.

  • G: Valor do custo acumulado do caminho percorrido
  • H: Valor restante do custo necessário até o destino

A soma dos dois valores acima estimam o caminho mais eficiente de um ponto inicial até o ponto final. O resultado dos valores acima é representado com a letra F e quanto menor for esse valor, menos custoso será o trajeto calculado.

O algoritmo A* é considerado um algoritmo inteligente, uma vez que ele pode encontrar o seu destino automaticamente sem a intervenção humana. A eficiência desse algoritmo é bastante relativo, tendo o seu desempenho diretamente influenciado pelo contexto do programa, com fatores como a qualidade dos dados de entrada e os métodos heurísticos adotados. Alguns métodos heurísticos utilizados com frequência são a distância de Manhattan e a distância euclidiana. Geralmente, o método heurístico é usado para estimar o menor valor possível até o destino do objeto.

Onde o algoritmo A* pode ser usado com efetividade?

O algoritmo A* pode ser usado em exercícios de grafos ou mapas para calcular a menor distância entre dois pontos. Esse algoritmo pode ser usado em jogos, aplicativos de navegação e em robôs.

caminho entre dois pontos

No exemplo acima, seguindo a ordem das setas, teríamos 3 opções de caminhos até o ponto final (ponto vermelho). Sem nenhum cálculo é possível perceber que o caminho mais curto é o G, H, I. Porém, o método A* pode ser usado em problemas muito mais complexos, contendo muito mais valores complexos a serem considerados do que o exemplos acima.

Um labirinto 2D é um bom candidato para ter um algoritmo A* implementado. Um labirinto, geralmente possui diversos obstáculos e caminhos sem saída até chegar ao seu destino final.

exemplo de labirinto 2d usando o algoritmo a*

Na imagem acima, temos um labirinto 2D, onde cada cor tem uma representação:

  • Quadrados brancos: Paredes (Obstáculo)
  • Quadrados azuis: Quadrados calculados para estimar o menor caminho
  • Quadrados vermelhos: Menor caminho estimado até o destino
  • Quadrado verde: Início
  • Quadrado amarelo: Destino

É possível perceber que no exemplo acima, os valores na diagonal também são calculados. O labirinto acima possui ao todo 651 quadrados (31x21). O total de quadrados que tiveram que ser calculados até podermos estimar o menor caminho até o destino foi de 247 quadrados. Isso é apenas 37% do total de quadrados. Sendo que 44% (291 quadrados) do labirinto é composto de paredes e 56% (360 quadrados) do labirinto é composto por quadrados pretos (caminho com possibilidade de locomoção), podemos chegar a conclusão que apenas 68% dos quadrados pretos foram necessários para estimar o melhor caminho até o destino, o que é bastante eficiente para um labirinto com caminhos estreitos. Mas o que aconteceria se não tivéssemos paredes? Veja o resultado abaixo:

exemplo de algoritmo a* sem obstáculos

O exemplo acima possui um mapa de 651 quadrados (31x21) e não contém paredes. A quantidade total de quadrados que precisaram ser calculados para estimar o menor caminho foi 19 quadrados, ou seja, 2.9% de quadrados em relação ao mapa. Assim, podemos chegar a conclusão que o algoritmo A* é bastante eficiente. Porém, em mapas complexos contendo obstáculos, ele tem uma notação de O(n), onde o “n” é a quantidade de quadrados a serem calculados.

Como aplicar o algoritmo A*?

A aplicação do algoritmo A* pode variar dependendo do contexto do programa. Um dos métodos que mais podem variar é o método de heurística, usado para calcular a distância do ponto atual até o ponto final. A fórmula para calcular o melhor caminho do ponto atual até o destino é:

  • f(n) = g(n) + h(n)

Onde o “g” é o caminho total percorrido até o ponto atual e o “h” é a heurística do ponto atual até o destino. O “f” é o custo total estimado do ponto atual até o destino.

Geralmente, o algoritmo A* usa duas variáveis para gerenciar o programa:

  • Lista aberta
  • Lista fechada

Lista aberta

A lista aberta contém pontos (coordenadas) que ainda não tiveram o seu melhor custo calculado. Dependendo do caminho do início até o ponto atual, ainda podem haver rotas com menores custos até o destino final. Pontos que ainda precisam ser calculados, estarão situados dentro da lista aberta.

Os pontos dentro da lista aberta terão o seu custo calculado através dos seus pontos vizinhos. O algoritmo testa todas as direções possíveis a partir do ponto atual, se locomovendo um intervalo a frente (x + 1 ou y + 1 em espaços 2D) e calculando a heurística para chegar ao ponto final. A direção que apresenta menor heurística será escolhida e adicionada à lista aberta com o ponto atual como parente.

exemplo de lista aberta no algoritmo a*

Lista fechada

A lista fechada contém objetos que já tiveram todos os seus vizinhos calculados. Os objetos inseridos na lista fechada são interpretados como concluídos ou custosos e ineficientes. Uma vez que a coordenada é inserida na lista fechada, ela passa a ser ignorada, fazendo com que a lista aberta continue avançando até chegar ao destino final.

Como funciona o algoritmo A*?

O algoritmo A* pode variar dependendo do contexto e das técnicas adotadas. Um dos diversos exemplos de algoritmo A* que existem é o abaixo:

algoritmo a* em gráfico

As etapas do algoritmo acima em detalhes são:

  1. Início
  2. Adiciona o ponto inicial na lista aberta para que o algoritmo comece a operar
  3. Ordena a lista aberta pelos itens que apresentaram menos custos até o destino
  4. Pega o primeiro item da lista aberta
  5. Examina todas as direções vizinhas do ponto atual e calcula o caminho mais curto
  6. Checa se o ponto atual chegou ao destino. Se sim, finaliza o programa. Se não, continua.
  7. Coloca o ponto atual na lista fechada com antecedência
  8. Cria uma repetição (loop) para examinar cada direção (vizinho) disponível do ponto atual
  9. Vizinho atual (ponto) já está adicionado na lista aberta? Se sim, continua. Se não, inseri o vizinho na lista com o ponto atual como parente.
  10. Vizinho atual já está adicionado a lista, mas apresenta um menor custo até o destino? Se sim, substitui o item existente da lista com o vizinho atual.
  11. Volta para a etapa 3 após finalizar a repetição.

Conclusão

O algoritmo A* é uma técnica de busca do menor caminho possível entre o ponto inicial e o destino. Esse método pode ser implementado tanto em simples problemas até em problemas complexos. Esse algoritmo é considerado como parte do campo de inteligência artificial de sistemas de busca inteligente.

Projetos práticos

Criando um jogo de pacman usando javascript e pixi.js (parte 1)

Desenvolvimento dos conceitos mais básicos do clássico pacman, como: mapa, animação, deslocamento e detector de colisões.

Implementando um algoritmo de pathfinding

Implementando um programa que encontra a menor distância entre dois pontos dentro de um labirinto usando o algoritmo A* (a-estrela).

Tutorial de programação do jogo da serpente em javascript

Programando o clássico jogo da serpente usando o framework p5.js. Tutorial indicado para iniciantes da programação que querem aprender os conceitos básico da área criando jogos.

Criando o esqueleto de um jogo de tiro 2D visto de cima usando P5.js

Usando lógicas matemáticas como trigonometria para criar e calcular o esqueleto de um jogo de tiro 2D em javascript

Desenvolvendo um jogo de quebra blocos em javascript

Programando um jogo clássico de arcade usando javascript e p5.js. O usuário deve quebrar os blocos utilizando uma bola ao mesmo tempo que evita que a bola saia pela parte inferior da tela

Veja também

Qual é o papel das grandes empresas além de fornecer seu serviços?

Poluição do ar, solo e água ainda é um grande problema para ser resolvido ainda em vários países. Há estudos que comprovam que os países mais poluentes podem causar câncer...

A comunicação entre dispositivos existe graças aos protocolos

Alguns desses protocolos é o HTTP que usamos em nossos navegadores. Sem esses protocolos teríamos alguns problemas na comunicação de dispositivos através da internet.

Seguir caminho (path following)

Um dos comportamentos de navegação (steering behaviors). Faz com que um agente siga um caminho pré-determinado pelo desenvolvedor.

RAT Remote Access Trojan

O RAT é um malware que tipicamente infecta o computador da vítima por um cavalo de tróia. Uma vez detectado, não é muito difícil sua remoção.

Linguagem de programação

A linguagem de programação é um conjunto de instruções que possuem um padrão de escritas, sendo um intermediário entre o programador humano e a máquina.

Variáveis na programação

As variáveis são elementos responsáveis por armazenar informações temporariamente ou perpetuamente durante a execução de um programa ou algoritmo.