International Journal of Scientific & Technology Research

IJSTR@Facebook IJSTR@Twitter IJSTR@Linkedin
Home About Us Scope Editorial Board Blog/Latest News Contact Us

IJSTR >> Volume 9 - Issue 1, January 2020 Edition

International Journal of Scientific & Technology Research  
International Journal of Scientific & Technology Research

Website: http://www.ijstr.org

ISSN 2277-8616

Comparative Analysis Of Path-Finding Algorithm On Unrestricted Virtual Object Movable For Augmented Reality

[Full Text]



Aninditya Anggari Nuryono, Alfian Ma’arif, Iswanto



A*, Unity 3D, Intel RealSense, Pathfinding, NavMesh, Augmented Reality, Intel RealSense



Pathfinding is a necessary method in gaming, especially in 3D games. Path-finding is used by an object to find paths from one place to another based on the state of the map and other objects. Path-finding requires algorithms that can process quickly and produce the shortest path to reach a destination location. In this paper, path-finding is applied in Augmented Reality. The Intel RealSense camera is used to reconstruct the real environment and display virtual objects. The path-finding algorithm is reviewed that the A*, A* smooth, and Navigation Mesh algorithms. Each of these algorithms is implemented into the Unity 3D object game. Each object game will move simultaneously to the destination point with different starting positions and goals by avoiding many obstacles. It is obtained in the 3D simulation that the A* smooth algorithm is superior to the A* algorithm and NavMesh. The travel time required a game object with A* smooth algorithm is 1.54 seconds faster, and 1.4 seconds compared to A* and NavMesh. Virtual objects can use pathfinding algorithms as a navigation path in the real world. The navigation path is located in the grid area that generated by Intel RealSense cameras.



[1] R. Azuma, Y. Baillot, R. Behringer, S. Feiner, S. Julier, and B. MacIntyre, “Recent advances in augmented reality,” IEEE Comput. Graph. Appl., vol. 21, no. 6, pp. 34–47, 2001.
[2] S. Siltanen, “Theory and applications of marker-based augmented reality,” in Espoo 2012. VTT Science Series 3, VTT, 2012, p. 198 p. + app. 43 p.
[3] M. Billinghurst, A. Clark, and G. Lee, “A Survey of Augmented Reality,” Found. Trends® Human–Computer Interact., vol. 8, no. 2–3, pp. 73–272, Aug. 2015.
[4] P. Zanuttigh, G. Marin, C. Dal Mutto, F. Dominio, L. Minto, and G. M. Cortelazzo, Time-of-Flight and Structured Light Depth Cameras. Springer International Publishing, 2016.
[5] P. Norvig and S. J. Russell, Artificial Intelligence: A Modern Approach. Upper Saddle River, NJ: Prentice Hall, 2010.
[6] J. R. Puigvert, T. Krempel, and A. Fuhrmann, “Localization Service Using Sparse Visual Information Based on Recent Augmented Reality Platforms,” in 2018 IEEE International Symposium on Mixed and Augmented Reality Adjunct (ISMAR-Adjunct), 2018, pp. 415–416.
[7] I. Iswanto, A. Ma’arif, O. Wahyunggoro, and A. Imam, “Artificial Potential Field Algorithm Implementation for Quadrotor Path Planning,” Int. J. Adv. Comput. Sci. Appl., vol. 10, no. 8, pp. 575–585, 2019.
[8] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Third Edition, 3rd ed. The MIT Press, 2009.
[9] P. de Byl, Holistic Game Development with Unity. 2017.
[10] S. L. Kim, H. J. Suk, J. H. Kang, J. M. Jung, T. H. Laine, and J. Westlin, “Using Unity 3D to facilitate mobile augmented reality game development,” in 2014 IEEE World Forum on Internet of Things (WF-IoT), 2014, pp. 21–26.
[11] A. Akaydın and U. Güdükbay, “Adaptive grids: an image-based approach to generate navigation meshes,” Opt. Eng., vol. 52, no. 2, p. 027002, 2013.
[12] J. Stamford, A. S. Khuman, J. Carter, and S. Ahmadi, “Pathfinding in partially explored games environments: The application of the A* Algorithm with occupancy grids in Unity3D,” in 2014 14th UK Workshop on Computational Intelligence (UKCI), 2014, pp. 1–6.
[13] M. Kallmann and M. Kapadia, “Navigation Meshes and Real-time Dynamic Planning for Virtual Worlds,” in ACM SIGGRAPH 2014 Courses, 2014, pp. 3:1--3:81.
[14] Z. Abd Algfoor, M. S. Sunar, and H. Kolivand, “A comprehensive study on pathfinding techniques for robotics and video games,” Int. J. Comput. Games Technol., vol. 2015, 2015.
[15] M. Ramirez, E. Ramos, O. Cruz, J. Hernandez, E. Perez-Cordoba, and M. Garcia, “Design of interactive museographic exhibits using Augmented reality,” in 23rd International Conference on Electronics, Communications and Computing, CONIELECOMP 2013, 2013, pp. 1–6.
[16] J. Wang et al., “Augmented Reality Navigation With Automatic Marker-Free Image Registration Using 3-D Image Overlay for Dental Surgery,” IEEE Trans. Biomed. Eng., vol. 61, no. 4, pp. 1295–1304, 2014.
[17] S. Bedoya-Rodriguez, C. Gomez-Urbano, A. Uribe-Quevedoy, and C. Quintero, “Augmented reality RPG card-based game,” in 2014 IEEE Games Media Entertainment, 2014, pp. 1–4.
[18] R. Furlan, “The future of augmented reality: Hololens - Microsoft’s AR headset shines despite rough edges [Resources_Tools and Toys],” IEEE Spectr., vol. 53, no. 6, p. 21, 2016.
[19] T. Araújo et al., “Life Cycle of a SLAM System: Implementation, Evaluation and Port to the Project Tango Device,” in 2016 XVIII Symposium on Virtual and Augmented Reality (SVR), 2016, pp. 10–19.
[20] Intel, “RealSense,” 2015. [Online]. Available: https://www.intel.com/content/www/us/en/architecture-and-technology/realsense-overview.html. [Accessed: 01-Jan-2015].
[21] M. Kallmann and M. Kapadia, “Geometric and discrete path planning for interactive virtual worlds,” ACM SIGGRAPH 2016 Courses - SIGGRAPH ’16, pp. 1–29, 2016.