Comparação dos algoritmos de busca de caminho, A* e Dijkstra, aplicado em cenários de jogos

Abstract

O mercado de Jogos Digitais cresce de forma constante e acelerada. A indústria de jogos lança todo ano diversos títulos que contam com, cada vez mais, recursos gráficos de alto poder tecnológico. O uso destes recursos depende muitas vezes do hardware de processamento gráfico, mas também está diretamente ligado à forma como um jogo digital é idealizado e implementado. Acompanhando o crescimento dos jogos digitais, surgem também as engines, termo utilizado para definir os motores de jogos, muitos disponibilizados gratuitamente e responsáveis por facilitar o desenvolvimento de jogos. Por meio do uso de um motor de jogo, é possível gerar cenários tridimensionais e implementar vários outros recursos presentes em jogos digitais de forma mais rápida. Em diversos gêneros de jogos, o comportamento dos personagens e de outras entidades relacionadas ao jogo também impactam na performance do mesmo, e consequentemente, na experiência do jogador. Uma das técnicas responsáveis por prover inteligência à uma entidade de um jogo é conhecida como busca de caminho, esta técnica consiste na determinação e projeção de uma rota para que um objeto do jogo possa navegar entre dois ou mais pontos do cenário, conhecendo o ambiente a qual está percorrendo e, consequentemente, demonstrando mais inteligência e fluidez na navegação. Para o uso do recurso de busca de caminho, se faz necessário a implementação de um algoritmo que será responsável por interpretar os pontos navegáveis do cenário a qual está inserido e então, gerar uma rota entre estes pontos. Existem vários tipos de algoritmos que realizam esta tarefa, dentre eles estão os algoritmos de Dijkstra e A*. Nesta pesquisa, utilizando-se do motor de jogo Unity3D para a modelagem de cenários tridimensionais, foram implementados os algoritmos de busca de caminho Dijkstra e A* que foram utilizados para a geração de caminhos dentro dos cenários modelados, viabilizando uma comparação entre ambos. Dentre os cenários testados, os resultados obtidos demonstraram que, conforme a complexidade dos cenários aumenta, os algoritmos tendem a impactar de forma crescente o fluxo do jogo.