TCC - Bacharelado em Sistemas da Informação (Sede)
URI permanente para esta coleçãohttps://arandu.ufrpe.br/handle/123456789/427
Navegar
1 resultados
Resultados da Pesquisa
Item Um algoritmo para geração de Navigation Meshes em mapas bidimensionais homogêneos: uma aplicação no jogo Dragon Age: Origins(2019) Costa, Ingrid Danielle Vilela; Bocanegra, Silvana; http://lattes.cnpq.br/4596111202208863; http://lattes.cnpq.br/6113606913639280Nos 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%.