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.

O algoritmo A
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
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 |
Pesquisa em Largura#
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:
- Escolher e remover um local da fronteira (frontier). →
- 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 Areached
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.
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:
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:
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:
Uau!! Surpreendente, não? Mas o que acontece com um mapa mais complicado?
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
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
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
O Algoritmo A
E … é tudo! Este é o Algoritmo A