Vinokurova S.E. Modification of the method of navigation graph for path finding in 3D space

Abstract: Path finding is a task of defining the optimal rout between two points in a space. Use of path finding algorithms allows controlling the moving of a character in 3D space with obstacles being avoided automatically, giving user the opportunity to fully immerse in the simulated 3D reality since the solutions to the problems of avatar moves is provided by the software environment itself. The article presents a modification of the navigation graph method of path finding in 3D space by setting a separate navigation graph for each 3D object. In that case each navigation graph specifies the paths inside and around a complex 3D object or a path around a simple 3D object. The modified algorithm is of significantly less computational cost for setting navigation graph, provides a more natural path and allows finding a rout with bypassing of moving objects. The proposed method is suitable for real-time applications and specifically due to the optimizations suggested in this article.

Keywords: