| |
| 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 |
| |
| Introdução: |
| Nos últimos anos, cada vez mais os jogos por computador vêm implementando algum grau de inteligência em seus personagens. Um exemplo disto é a implementação de métodos de planejamento de caminho. Este trabalho visa comparar técnicas utilizadas normalmente para planejamento de caminho de personagens de jogos de labirinto 2D, do tipo PacMan (o jogo pode ser encontrado em Postma (2000)). Estas técnicas são os algoritmos de busca heurística A*, a busca em largura e a busca em profundidade em grafos. O jogo PacMan possui dois personagens, o “come-come” e os “fantasmas”. O jogador controla o personagem “come-come”, que tem o objetivo de comer todas as bolinhas do cenário do jogo. A fig. 1 a) mostra como é o desenho do personagem “come-come”. Os personagens “fantasmas” têm o objetivo de impedir a atividade do personagem “come-come” tentando encurralá-lo. A morte deste acontece quando algum “fantasma” consegue encostar-se a ele, impedindo que o jogador vença o jogo. A fig. 1 b) mostra como é o desenho do personagem “fantasma”. Uma ilustração de um cenário para o jogo pode ser visto na fig. 2. Em cada estado do jogo, o objetivo de cada “fantasma” é dirigir-se para o local onde está o “come-come”. Para isso, cada “fantasma” precisa calcular o caminho mais curto de sua posição até a posição do “come-come”.A área onde se encontra o cenário do jogo pode ser modelada como um grafo, sendo que o cenário do jogo será uma adaptação do tradicional jogo PacMan, e o planejamento do caminho de cada “fantasma” resume-se a um problema de busca por caminho mínimo no grafo. Neste contexto, o caminho mínimo entre um par de vértices u e v em um grafo é definido como sendo o caminho com menor quantidade de arestas, dentre todos os caminhos possíveis entre esses dois vértices. Devido à característica dinâmica dos jogos do tipo PacMan, acredita-se que os métodos tradicionais de busca possuem um desempenho muito lento, pois durante o processo de busca, eles visitam uma grande quantidade de vértices desnecessariamente. Uma das técnicas que pode melhorar o desempenho dos personagens “fantasmas” em concluir o seu objetivo é o uso de um algoritmo de busca heurística. A heurística é uma técnica que melhora a eficiência de um processo de busca. No problema proposto, é necessária uma heurística que se aproxime bastante do caminho mínimo, mas que explore uma pequena quantidade de vértices para chegar à solução. O algoritmo de busca heurística A* (RABUSKE, 1995, p. 41), a busca em largura (CORMEN et al., 2002, p. 422), e a busca em profundidade (CORMEN et al., 2002, p. 429) encontram o menor caminho entre dois vértices em um grafo, podendo ser utilizados para planejamento do menor caminho entre o personagem “fantasma” e o personagem “come-come”. |
| |
|
