Use este identificador para citar ou linkar para este item: https://repository.ufrpe.br/handle/123456789/2136
Título: Um Algoritmo Para Geração de Navigation Meshes em Mapas Bidimensionais Homogêneos: uma aplicação no jogo Dragon Age: Origins
Autor: Costa, Ingrid Danielle Vilela
Endereco Lattes do autor: http://lattes.cnpq.br/6113606913639280
Orientador: Bocanegra, Silvana
Endereco Lattes do orientador : http://lattes.cnpq.br/4596111202208863
Palavras-chave: Algorítmos computacionais;Robótica;Jogos eletrônicos
Data do documento: 2019
Citação: COSTA, Ingrid Danielle Vilela. Um Algoritmo Para Geração de Navigation Meshes em Mapas Bidimensionais Homogêneos: uma aplicação no jogo Dragon Age: Origins. 2019. 55 f.Trabalho de Conclusão de Curso (Bacharelado em Sistemas de Informação)- Departamento de Estatística e Informática, Universidade Federal Rural de Pernambuco, Recife, 2019.
Abstract: In the field of electronic gaming and more recently in robotics, autonomous agent soften need to repeatedly solve the problem of searching for the smallest path. This need can eventually consume a lot of resources and demands optimizations to make these searches more efficient. Such optimizations may include improvements in search algorithms, map representation, data structures used. This work presents an optimization for search algorithms based on the reduction of the search space by means of an automatic Navigation Meshes generation algorithm which are networks of walka blemap areas implying in a reduction of the search space and consequently improving the search processing time. The generation of Navigation Meshes is a problem with no consolidated solution. To prove the heuristic, path finding problems were solved on 156 benchmark maps. The path findings were performmed by the A* algorithm and the solutions were compared between the original maps and the optimized ones. An average search space reduction of 97.42% was achieved, with a standard deviation of 0.026and the search had an average marginal reduction in execution time of 46.76%.
Resumo: Nos cenário dos jogos eletrônicos e, mais recentemente, na robótica, agentes autônomos comumente necessitam resolver repetidamente o problema de busca de menor caminho. Esta necessidade eventualmente pode consumir muitos recursos e demandaotimizações para que estas buscas sejam mais eficientes. Tais otimizações podem in-cluir melhorias nos algoritmos de busca, na representação dos mapas, nas estruturasde dados utilizadas, entre outras. O presente trabalho apresenta uma otimização para algoritmos de busca baseada na redução do tamanho do espaço de busca, através deum algoritmo de geração automática de Navigation Meshes, que são redes de áreas caminháveis de mapas, implicando em redução do espaço de busca e consequen-temente melhoria de tempo de processamento. A geração de Navigation Meshes é um problema ainda sem solução estabelecida. Para avaliar a heurística foram solucionados problemas de caminho mínimo em 156 mapas obtidos de um benchmark. Os caminhos foram determinados pelo algoritmo A* e foram comparadas as soluções no mapa original e no mapa otimizado pela heurística. Foi alcançada uma redução de espaço de busca média de 97,42%, com desvio padrão de 0,026 e a busca teve uma redução marginal média no tempo de execução de 46,76%.
URI: https://repository.ufrpe.br/handle/123456789/2136
Aparece nas coleções:TCC - Bacharelado em Sistemas da Informação (Sede)

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
tcc_ingriddaniellevilelacosta.pdf1,55 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.