Uma Introdução ao Algoritmo A*

António Ferreira Pereira, Novembro de 2020
traduzido e adaptado de Red Blob Games
com o gentil consentimento de Amit Patel.

Em muitos jogos é frequente andarmos à procura de caminhos de um local para outro. Não estamos apenas interessados na distância percorrida mas também no tempo de viagem!

Ao alteramos o ponto de partida (origem) e/ou o ponto de chegada (destino) o caminho "mais curto" altera-se também.

Para encontrar este "caminho mais curto" usamos um algoritmo de pesquisa em grafos. Para isso é preciso que o mapa esteja representado por um grafo. Um dos algoritmos mais simples é a Pesquisa em Largura (Breadth First Search), pelo qual começamos e a partir do qual derivamos o Algoritmo A*.

Representação dos mapas#

A primeira coisa a fazer quando se estuda um algoritmo é perceber as estruras dos dados subjacentes. Quais são os dados de entrada (input)? Quais são os dados de saída (output)?

Input: Um grafo: um conjunto de locais ("nós", "vértices") e um conjunto de ligações ("arestas", "arcos") entre os locais.

Different map with the same pathfinding graph
Sprites by StarRaven - see footer for link

O algoritmo A* não vê mais nada para além do grafo. Não sabe se um local é interior ou exterior, se é uma sala ou uma passagem, nem se tem uma área grande ou pequena. O algoritmo não vê a diferença entre o mapa indicado e .

Output: O caminho encontrado pelo algoritmo é uma sequência As arestas, sendo um conceito matemático abstrato, indicam a deslocação de um local para outro mas não indicam como: se o caminho é em linha recta ou corresponde a abrir uma porta, ou a nadar entre duas margens de um rio sinuoso!

Custos/Benefícios: Existem muitas formas de definir grafos correspondentes a um dado mapa, adequados aos algoritmos de pesquisa.

No mapa seguinte são atribuídos vértices às passagens nas portas. Se atribuirmos obtemos um grafo diferente. Mas podemos também usar obtendo um grafo com um número elevado de vértices (e arestas)!

Note-se que o grafo de pesquisa não tem de ser o mesmo que o mapa do jogo! O algoritmo A*, como a maioria dos algoritmos de pesquisa, é mais rápido em grafos com poucos vértices. Por uma questão de clareza e simplicidade, no que se segue, vamos usar grelhas para ilustrar os diversos conceitos presentes nos algoritmos.

Algoritmos#

Existe muitos algoritmos para pesquisar e determinar caminhos em grafos. Vamos considerar apenas os seguintes:

A Pesquisa em Largura (Breadth First Search) explora sucessivamente todos os vizinhos de um vértice em todas as direções. É um algoritmo genérico, bastante útil em diversas áreas e para a resolução de vários problemas, como a análise e a geração de mapas ou a determinação de caminhos em grafos.
O Algoritmo de Dijkstra (também conhecido por Pesquisa de Custo Uniforme) permite atribuir preferências aos caminhos que vão ser explorados. Em vez de explorar todos os caminhos possíveis, dá prioridade aos caminhos com menor custo. Nos mapas de jogos, podemos atribuir custos mais reduzidos a certas arestas para encorajar a deslocação por estradas ou atribuir custos mais elevados para evitar florestas ou a aproximação de inimigos. Quando os custos dos movimentos são variáveis, este algoritmo é mais eficiente do que a Pesquisa em Largura.
O Algoritmo A* é uma modificação do algoritmo de Dijkstra que otimiza a pesquisa para um único destino. Enquanto o algoritmo de Dijkstra permite encontrar caminhos para todos os destinos, o algoritmo A* permite apenas encontrar um caminho para um único destino ou para uma vizinhança de vários locais de destino.

A ideia principal destes 3 algoritmos que vamos analisar é a de manter um registo de um conjunto de vértices que serão analisados e expandidos chamado a fronteira. Nos problemas com grafos de grelha o processo de construção da fronteira é conhecido por inundação (“flood fill”). Inicie a animação para ver como a fronteira se expande    


Qual é o algoritmo? Basta repetir os seguintes passos até que a fronteira fique vazia:

  1. Escolher e remover um local da fronteira (frontier).    
  2. Expandir a fronteira por análise dos vizinhos           do local actual. Ignorar as paredes ou obstáculos. Todos os vizinhos que ainda não tenham sido alcançados são adicionados à fronteira (frontier) bem como ao conjunto dos vértices alcançados (reached)    

Vejamos este processo com mais detalhe, numerando as quadrículas da grelha pela ordem em que são vizitadas. Avançe passo a passo para ver a expansão da fronteira:


A implementação deste processo consiste em apenas 10 linhas de código (Python):

frontier = Queue()
        frontier.put(start )
        reached = set()
        reached.add(start)
        while not frontier.empty():
            current = frontier.get()
            for next in graph.neighbors(current):
            if next not in reached:
                frontier.put(next)
                reached.add(next)

O ciclo while no código anterior é a essência dos algoritmos de pesquisa em grafos que vamos analisar, incluindo o algoritmo A*. O problema agora é: como encontrar o caminho mais curto? O ciclo não constrói os caminhos, apenas nos permite visitar todo o mapa. Vamos então modificar o ciclo de modo a registar o antecessor de cada local alcançado. Vamos substituir o conjuntoreached por uma tabela came_from na qual as chaves (ou índices) formam o conjunto dos locais alcançados:

frontier = Queue()
frontier.put(start )
came_from = dict()
came_from[start] = None
while not frontier.empty():
    current = frontier.get()
    for next in graph.neighbors(current):
        if next not in came_from:
            frontier.put(next)
            came_from[next] = current

Agora, para cada local loc, came_from[loc] aponta para o local que o antecede. São como migalhas largadas num caminho e que nos possibilitam voltar ao local de partida.

Aponte para um qualquer lugar no mapa e observe que seguindo as setas obtemos o caminho reverso do percorrido pelo algoritmo, de volta à posição original.

O código para reconstruir os caminhos é simples: seguir as setas desde o destino para oinício. Um caminho é uma sequência de vértices e arestas mas, frequentemente, é suficiente guardar os vértices:

current = goal 
path = []
while current != start: 
    path.append(current)
    current = came_from[current]
path.append(start) # optional
path.reverse() # optional

Este é um dos mais simples algoritmos para determinar caminhos em grafos. Para além das grelhas, funciona também para todos os tipos de problemas que tenham uma estrutura de grafo.

Saída antecipada#

O algoritmo anterior permite encontrar caminhos de um determinado local para todos os outros locais. É frequente não estarmos interessados em todos os caminhos, precisando apenas de um caminho de um local para outro local. Podemos pois parar de expandir a fronteira assim que atingimos o local de destino.

Arraste o e observe como a fronteira pára de se expandir assim que atinge o local de destino.

Sem saída antecipada
Com saída antecipada

O código necessário para implementar esta alteração é trivial:

frontier = Queue()
frontier.put(start )
came_from = dict()
came_from[start] = None
while not frontier.empty():
    current = frontier.get()
    if current == goal: 
        break
    for next in graph.neighbors(current):
        if next not in came_from:
            frontier.put(next)
            came_from[next] = current

Há algumas coisas bem interessantes que se podem alcançar com a utilização de condições de saída apropriadas...

Custos dos movimentos#

Até agora considerámos que todos os passos têm o mesmo "custo". Em muitas situações há custos diferentes para diferentes tipos de movimentos. Por exemplo no mapa apresentado inicialmente podemos considerar que "caminhar" na água tem um custo 10 vezes superior a caminhar na relva. Um outro exemplo é o do movimento diagonal numa grelha que tem um custo superior ao dos movimentos ao longo dos eixos. Queremos que o algoritmo de pesquisa de um caminho tenha em conta estes custos.

Vamos comparar o número de passos dados para chegar até um local com a distância a que este se encontra do início:

Número de passos
Distância

Para resolver este problema precisamos do Algoritmo de Dijkstra (ou Pesquisa de Custo Uniforme). Quais as diferenças para a Pesquisa em Largura? Precisamos acompanhar os custos dos movimentos, por isso adicionamos uma nova variável cost_so_far responsável por registar o custo total da deslocação até cada local, partindo do local inicial. Queremos também utilizar os custos dos movimentos para decidir quais os locais a explorar. Assim, vamos substituir a simples fila de espera usada acima por uma fila prioritária. Um outro aspecto menos óbvio é que podemos visitar um mesmo local, em várias etapas, com custos diferentes. Por isso é necessário modificar ligeiramente a lógica do algoritmo anterior: em vez de sempre juntar à fronteira qualquer local que não tenha sido anteriormente alcançado, vamos adicioná-lo apenas quando o novo caminho para esse local é melhor do que os caminhos anteriormente explorados.

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
cost_so_far = dict()
came_from[start] = None
cost_so_far[start] = 0
while not frontier.empty():
    current = frontier.get()
    if current == goal:
        break
    for next in graph.neighbors(current):
        new_cost = cost_so_far[current] + graph.cost(current, next)
        if next not in cost_so_far or new_cost < cost_so_far[next]:
            cost_so_far[next] = new_cost
            priority = new_cost
            frontier.put(next, priority)
            came_from[next] = current

A utilização de uma fila prioritária em vez de uma fila normal altera a forma como a fronteira se expande. As linhas de contorno são uma forma de visualizar essa diferença. Inicie a animação e observe como a fronteira se expande mais lentamente nas florestas, encontando o caminho de custo mínimo à volta da floresta em vez de a atravessar:

Pesquisa em Largura
Algoritmo de Dijkstra

A utilização de custos diferentes permite explorar diversas situações interessantes, nomeadamente grafos que não são grelhas: No mapa apresentado no início os custos eram baseados na distância de local para local mas podem ser melhorados de modo a evitar zonas próximas de inimigos ou a preferir zonas próximas de aliados.

Pesquisa por Heurísticas#

Tanto na Pesquisa em Largura como no Algoritmo de Dijkstra, a fronteira expande-se em todas as direções. Esta pode ser uma propriedade favorável quando procuramos caminhos para muitos (ou todos os) locais. No entanto, em muitas situações o objetivo é encontrar um caminho para um único local. Assim, será desejável que a fronteira se expanda mais na direção do local de destino do que nas outras direções. Começamos por definir uma função heurística que indica o quão próximo um dado local está do local de destino:

def heuristic(a, b):
    # Distância de Manhattan numa grelha quadrada
    return abs(a.x - b.x) + abs(a.y - b.y)

No Algoritmo de Dijkstra usámos a distância da origem a um local para estabelecer a ordem na fila prioritária. Aqui, na chamada Pesquisa Gulosa o Melhor em Primeiro (Greedy Best First Search), usaremos a distância estimada de um local ao destino. O local mais perto do destino é aquele que é explorado em primeiro lugar. O código usa a fila prioritária do Algoritmo de Dijkstra sem o cost_so_far:

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
came_from[start] = None
while not frontier.empty():
    current = frontier.get()
    if current == goal:
        break
    for next in graph.neighbors(current):
        if next not in came_from:
            priority = heuristic(goal, next)
            frontier.put(next, priority)
            came_from[next] = current

Vejamos o comportamento:

Algoritmo de Dijkstra
Pesquisa Gulosa o Melhor Primeiro

Uau!! Surpreendente, não? Mas o que acontece com um mapa mais complicado?

Dijkstra’s Algorithm
Pesquisa Gulosa o Melhor Primeiro

Os caminhos obtidos não são os de custo mínimo! Assim, este algoritmo é muito eficiente quando os obstáculos são poucos, mas os caminhos obtidos podem não ser bons. Podemos corrigir este problema? Sim!

O Algoritmo A*#

O Algoritmo de Dijkstra funciona bem para encontrar o caminho de custo mínimo, mas gasta tempo a explorar direções não promissoras. O Algoritmo de Pesquisa Gulosa o Melhor Primeiro explora apenas nas direções promissoras mas pode não encontrar o caminho de custo mínimo. O Algoritmo A* usa em simultãneo a distância desde a origem a um local e a distância estimada de um local ao destino.

O código é semelhante ao Algoritmo de Dijkstra:

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
cost_so_far = dict()
came_from[start] = None
cost_so_far[start] = 0
while not frontier.empty():
    current = frontier.get()
    if current == goal:
        break
    for next in graph.neighbors(current):
        new_cost = cost_so_far[current] + graph.cost(current, next)
        if next not in cost_so_far or new_cost < cost_so_far[next]:
            cost_so_far[next] = new_cost
            priority = new_cost + heuristic(goal, next)
            frontier.put(next, priority)
            came_from[next] = current

Comparação dos algoritmos: O Algoritmo de Dijkstra calcula a distância desde a origem. O Algoritmo Guloso o Melhor Primeiro estima a distância ao destino. O Algoritmo A* usa a soma das duas distâncias.

Algoritmo de Dijkstra
Algoritmo Guloso o Melhor Primeiro
Algoritmo A*

Tente abrir buracos na parede em vários locais. Podemos verificar que quando o Greedy Best-First Search encontra a solução ótima também o Algoritmo A* a encontra, ambos explorando a mesma área. Quando o Greedy Best-First Search falha a solução ótima (um caminho de custo mais elevado), o algoritmo A* encontra o caminho ótimo, assim como o Algoritmo de Dijkstra, mas explora menos área que o Algoritmo de Dijkstra.

O Algoritmo A* é o melhor de dois mundos. Desde que a função heurítica seja admissível, isto é, que não sobrestime as distâncias (custos) , o Algoritmo A* encontrará o caminho ótimo. O algoritmo A* usa a heurística para reordenar os nós do grafo de modo que seja mais provável encontrar o nó destino mais cedo.

E … é tudo! Este é o Algoritmo A*.