Vinokurova S.E. Modification of the method of navigation graph for path finding in 3D space // Software systems and computational methods. 2014. № 1. P. 109-124. URL: https://en.nbpublish.com/library_read_article.php?id=64048

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:

path finding, navigation graph, algorithm, optimization, advanced method, A* algorithm, navigation mesh, obstacles, dynamic objects, 3d space

This article can be downloaded freely in PDF format for reading. Download article

This article written in Russian. You can find original text of the article here .

References

1.	A.Yu. Smorkalov. Matematicheskaya i programmnaya modeli generatsii tekstur na graficheskikh potokovykh protsessorakh // Programmnye sistemy i vychislitel'nye metody. – 2013. – № 1. – S. 104-107. DOI: 10.7256/2305-6061.2013.01.10.
2.	Yap, P. Grid-Based Path-Finding / P.Yap // AI '02 Proceedings of the 15th Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence-2002. – 44-55 pp.
3.	Cui, X., Shi, H. A*-based Pathfinding in Modern Computer Games/ X. Cui, H. Shi // IJCSNS International Journal of Computer Science and Network Security-Vol.11 No.1, January 2011.
4.	Tozour, P. Fixing Pathfinding Once and For All [Electronic resource] / Game AI.-Electronic data.-Mode acess: http://www.ai-blog.net/archives/000152.html. free.
5.	Mika, M., Charla, C. Simple,Cheap Pathfinding / M. Mika, C. Charla // AI Game Programming Wisdom-2002.
6.	O'Neill, J. S. Efficient Navigation Mesh Implementation / J. C. O'Neill // Journal of Game Development-Vol. 1 No. 1, 2004.-71-90 pp.
7.	Akbar, A. Raycast Navigation Mesh Generation and Path Finding System [Electronic resource]-Electronic data.-Mode acess: http://syntheticarc.com/?q=node/6, free.
8.	Botea, A., Muller, M., Schaeffer, J. Near Optimal Hierarchical Path-finding / A. Botea, M. Muller, J. Schaeffer // Journal of Game Development-Vol. 1 Issue 1, 2004.
9.	I.A.Sadovin, A.Yu. Smorkalov. Sistema perenosa lektsiy v virtual'nyy mir vAcademia s ispol'zovaniem vozmozhnostey Microsoft Kinect i potokovykh protsessorov // Programmnye sistemy i vychislitel'nye metody. – 2013. – № 4. – S. 90-94. DOI: 10.7256/2305-6061.2013.04.10.