Pathfinding in hierarchical representation of large realistic virtual terrains

• Ano de defesa: 2018
• Autor(a) principal: Brondani, Juliana Rubenich
• Orientador(a): Freitas, Edison Pignaton de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Palavras-chave em Português: Simulação computacional
• Palavras-chave em Inglês: Hierarchical terrain; Simulation systems; Hierarchical pathfinding; Large virtual terrain; Navigation map representation
• Link de acesso: http://hdl.handle.net/10183/185250

Pathfinding is critical to virtual simulation applications. One of the most prominent pathfinding challenges is the fast computation of path plans in large and realistic virtual terrain environments. To tackle this problem, this work proposes the exploration of a quadtree structure in the navigation map representation of large real-world virtual terrains. Exploring a hierarchical approach for virtual terrain representation, we detail how a global hierarchical pathfinding algorithm searches for a path in a coarse initial navigation map representation. Then, during execution time, the pathfinding algorithm refines regions of interest in this terrain representation in order to compute paths with a higher quality in areas where a large amount of navigation obstacles is found. The computational time of such hierarchical pathfinding algorithm is systematically measured in different hierarchical and non-hierarchical terrain representation structures that are instantiated in the modeling of a small real-world terrain scenario. Then, similar experiments are developed in a large real-world virtual terrain that is inserted in a real-life simulation system for the development of military tactical training exercises. The results show that the computational time required to generate pathfinding answers can be optimized when the proposed hierarchical pathfinding algorithm along with the easy and reliable implementation of the quadtree-based navigation map representation of the large virtual terrain are explored in the development of simulation systems.