Redes neurais e algoritmos hierárquicos de pathfinding para computação de elevação e inclinação na busca de caminhos em terrenos virtuais

Abstract

In computer games and virtual simulators, the fun, difficulty and variability of entertainment and/or training challenges are directly related to the behavior of characters inserted in the built virtual environments. In terms of behavior, one of the main characteristics of these characters is the ability to move along paths that are automatically computed. For this, pathfinding algorithms have gained greater importance in the field of Artificial Intelligence (AI) especially when considered together with deep neural networks (DNN). However, the integration of these AI research areas still does not present clearly established patterns, especially when we consider that relief information of the land used must be used in computing the cost of the investigated paths. The objective of this TCC, therefore, is to research, develop and test hierarchical pathfinding algorithms that consider terrain relief irregularities, and explore DNN to optimize the search for such paths in large terrains that contain this topographical information. With this, this work presents experiments with traditional heuristics and DNN computed heuristics trained in the execution of the pathfinding algorithms A∗ and HPA*, presenting a way to consider the terrain relief in the determination of paths. From the statistical analysis of the experimental results obtained in the TCC, it is possible to state that the use of DNN can reduce the computational cost of both A* and HPA* considering the terrain relief.