| |
| Acadêmico(a): Jeanita Bassani da Silva |
| Título: Estudo Comparativo entre Algoritmo A* e Busca em Largura para Planejamento de Caminho de Personagens em Jogos do Tipo Pacman |
| |
| Conclusão: |
| Diante do objetivo deste trabalho, fazer um estudo comparativo entre os algoritmos de busca de caminhos, o busca em largura, o busca em profundidade e o algoritmo A*, entre os personagens do jogo PacMan, os objetivos foram alcançados e superados, pois além do estudo comparativo entre os algoritmos mencionados, foram implementados também os algoritmos de busca em profundidade adaptado e o A* adaptado, sendo que estes algoritmos são específicos para o problema proposto, o jogo PacMan. O algoritmo de busca em largura, em relação aos outros algoritmos implementados, encontra a solução do problema, porém testa uma grande quantidade de vértices, mesmo sabendo onde está o vértice que ele está procurando, mesmo assim ele é melhor que o busca em profundidade pois acha uma solução. O algoritmo busca em profundidade, conforme os testes realizados, não é eficiente para o problema proposto, pois o “fantasma” dificilmente chega até onde está o “come-come”. O algoritmo A* encontra sempre uma boa solução, ou seja, um caminho sem ter que testar uma grande quantidade de vértices, levando em consideração que é um algoritmo genérico, e que não foi criado para ser utilizado exclusivamente neste jogo. O algoritmo A* adaptado, é a implementação do algoritmo A* com número limitado de vértices que podem ser tirados da lista de abertos, o número escolhido foi 25 vértices, levando em consideração o tamanho do labirinto implementado. O A* adaptado, às vezes testa menos vértices que o A*, porém na maioria dos testes realizados ele deixa de testar um vértice importante para a solução do problema, acabando testando mais vértices que o A*. O algoritmo busca em profundidade adaptado mescla o algoritmo busca em profundidade com o algoritmo A*. Diante do problema proposto ele foi o algoritmo com o melhor desempenho, ou seja, a menor média de vértices testados. O busca em profundidade ordena os vértices adjacentes a serem testados por ordem de menor custo, colocando todos os adjacentes não testados em uma lista, calcula a distância, que é estimada conforme a fórmula do A* e adiciona um custo local. O custo local do vértice aumenta cada vez que um “fantasma” passa por ele, e é zerado quando o “come-come” passa pelo mesmo vértice, isso desestimula o “fantasma” a andar em círculos, (que é o problema do busca em profundidade implementado) e os estimula a seguir o “come-come”. Entretanto este é um algoritmo que foi implementado para o jogo PacMan e não pode ser usado para a solução de problemas genéricos de busca. O uso da linguagem de programação Object Pascal com ambiente Delphi para a realização deste estudo comparativo foi eficiente, pois ajudou a alcançar os objetivos propostos. Em relação a modelagem de objetos para implementação do protótipo, a separação entre classes de modelo e interface não foi proposta como requisito porque o principal objetivo da implementação era a criação de um protótipo de software com o qual se poderia comparar os diferentes algoritmos de busca em uma aplicação semelhante a um jogo, ao invés de implementar um jogo propriamente dito. Dentre as possibilidades de continuidade do trabalho realizado, poderia ser feita uma adaptação do algoritmo busca em largura com o algoritmo A*, transformar o cenário do jogo (o labirinto) em 3D e fazer um estudo de outros algoritmos para resolução de problemas de busca de caminho mínimo para aplicá-los no jogo implementado. |
| |
|
