Pathfinding problem solutions in cubic grids with 3D neighborhood expansion

Abstract

Pathfinding in three-dimensional environments is essential for solving various application problems. Pathfinding in 3D scenarios presents significantly greater complexity than in two-dimensional contexts, primarily due to the increase in potential paths an agent can traverse. This complexity is further amplified by three-dimensional obstacles, which add a layer of difficulty to pathfinding and demand solutions capable of efficiently navigating complex scenarios. Considering the third dimension, movement in multiple directions becomes relevant to identifying low-cost and smooth routes in 3D scenarios. To address these challenges, this work investigates an innovative technique called 3D Neighbor hood Expansion, which uniformly expands the neighborhood search in three-dimensional space. The proposed 3D neighborhood expansion is then integrated into relevant path smoothing algorithms. The primary goal is to analyze the impact of expanding the search neighborhood, controlled by the parameter k, on the performance of pathfinding algo rithms in 3D environments. Specifically, this work examines whether increasing k results in more direct and smoother paths. The technique is tested using voxel-based maps de rived from the online game Warframe, which offer realistic representations of 3D space. Based on a statistical analysis of various path search metrics, experiments conducted with the A∗, Theta∗, and JPS algorithms demonstrate that expanding the neighborhood signifi cantly improves the quality of the resulting paths as k increases. These findings are crucial for advancing practical applications in computer games, robotics, and simulation systems.

Abusca de caminhos em ambientes tridimensionais é essencial para resolver vários pro blemas de aplicação. A busca de caminhos em cenários 3D apresenta uma complexidade significativamente maior do que em contextos bidimensionais, principalmente devido ao aumento nos potenciais caminhos que um agente pode percorrer. Essa complexidade é ainda mais ampliada por obstáculos tridimensionais, que adicionam uma camada de di f iculdade à busca de caminhos e exigem soluções capazes de navegar eficientemente em cenários complexos. Ao considerar a terceira dimensão, o movimento em várias dire ções torna-se relevante para identificar rotas de baixo custo e suavidade em cenários 3D. Para lidar com esses desafios, este trabalho investiga uma técnica inovadora chamada Ex pansão da Vizinhança 3D, que expande uniformemente a busca de vizinhança no espaço tridimensional. A expansão da vizinhança 3D proposta é então integrada aos algoritmos relevantes de suavização de caminhos. O objetivo principal é analisar o impacto da expan são da vizinhança de busca, controlada pelo parâmetro k, no desempenho de algoritmos de busca de caminhos em ambientes 3D. Especificamente, este trabalho examina se o au mento de k resulta em caminhos mais diretos e suaves. A técnica é testada usando mapas baseados em voxel, derivados do jogo online Warframe, que oferecem representações re alistas do espaço 3D. Com base em uma análise estatística de várias métricas de busca de caminho, experimentos realizados com os algoritmos A∗, Theta∗ e JPS demonstram que a expansão da vizinhança melhora significativamente a qualidade dos caminhos resultan tes à medida que k aumenta. Essas descobertas são cruciais para o avanço de aplicações práticas em jogos de computador, robótica e sistemas de simulação.