Resumo

Nessa derradeira e última aula sobre descoberta de caminhos, você aprendeu um pouco sobre dois algoritmos amplamente utilizados na Ciência da Computação e na área de jogos: algoritmo de Dijkstra e A*.

Inicialmente foi apresentado o conceito de heurística e exemplificadas três formas distintas de como o processo de decisão de escolha de caminho pode ser realizado. Um dos exemplos foi utilizado junto com uma busca em profundidade para ilustrar como seria a execução de um algoritmo que possui um processo decisório simples no percurso de um caminho em um grafo.

Em seguida, foi apresentado o algoritmo de Dijkstra, que permite o cálculo do menor caminho entre um vértice e todos os outros vértices do grafo, podendo ser adaptado para procurar o menor caminho entre dois pontos do grafo. Também foi observado que, apesar de garantir o menor caminho, esse algoritmo necessita explorar muitos vértices para gerar o resultado, o que limita o seu uso em cenários onde o mapa possui tamanho exagerado.

Uma otimização em cima desse algoritmo é a busca A*, em que se une o algoritmo de Dijkstra com um passo de decisão heurístico para otimizar o processo de descoberta de caminhos. Com esse algoritmo, é possível traçar o melhor caminho entre dois pontos de um mapa com uma boa performance de execução, o que torna essa técnica uma das principais da indústria de jogos.