Um algoritmo para geração de Navigation Meshes em mapas bidimensionais homogêneos: uma aplicação no jogo Dragon Age: Origins

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%.