Os materiais didáticos aqui disponibilizados estão licenciados através de Creative Commons Atribuição-SemDerivações-SemDerivados CC BY-NC-ND. Você possui a permissão para visualizar e compartilhar, desde que atribua os créditos do autor. Não poderá alterá-los e nem utilizá-los para fins comerciais.
Atribuição-SemDerivações-SemDerivados
CC BY-NC-ND
Cursos / Jogos Digitais / Inteligência Artificial para Jogos / Aula
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:
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.
Busca_A*(Grafo g, Vértice inicio, Vértice fim){ Visitados = {} //Nenhum vértice foi visitado ainda Abertos ={inicio} //Vértices na fila para exploração custo[] // Vetor que representa os custos dos caminhos para cada //vértice anterior[] // Vetor que representa o vértice anterior no caminho futuro[] //Vetor que representa o custo futuro do caminho Enquanto Abertos não for vazio{ atual = vértice de Abertos que possui menor valor de caminho futuro Se atual == fim Retorne o caminho Remove atual de Abertos Insere atual em Visitados Para cada vizinho de atual{ Se o vizinho não foi visitado{ Se ele não estiver em Abertos Insere vizinho em Abertos custo_vizinho = custo[atual] + g[atual, vizinho] Se custo_vizinho < custo[vizinho]{ anterior[vizinho] = atual custo[vizinho] = custo_vizinho futuro[vizinho] = custo[vizinho]+ HEURÍSTICA } } } } Retorna ERRO }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? )
Versão 5.3 - Todos os Direitos reservados