Journal of Electrical Engineering and Technology

The Korean Institute of Electrical Engineers (대한전기학회)
권호 표지
DOI QR코드

DOI QR Code

Reducing the Search Space for Pathfinding in Navigation Meshes by Using Visibility Tests

  • Kim, Hyun-Gil (Department of Multimedia, Korea Nazarene University) ;
  • Yu, Kyeon-Ah (Department of Computer, Duksung Women's University) ;
  • Kim, Jun-Tae (Department of Computer Engineering, Dongguk University)
  • Received : 2010.11.21
  • Accepted : 2011.09.01
  • Published : 2011.11.01
Download PDF
⟨ Previous Next ⟩

Abstract

A navigation mesh (NavMesh) is a suitable tool for the representation of a three-dimensional game world. A NavMesh consists of convex polygons covering free space, so the path can be found reliably without detecting collision with obstacles. The main disadvantage of a NavMesh is the huge state space. When the $A^*$ algorithm is applied to polygonal meshes for detailed terrain representation, the pathfinding can be inefficient due to the many states to be searched. In this paper, we propose a method to reduce the number of states searched by using visibility tests to achieve fast searching even on a detailed terrain with a large number of polygons. Our algorithm finds the visible vertices of the obstacles from the critical states and uses the heuristic function of $A^*$, defined as the distance to the goal through such visible vertices. The results show that the number of searched states can be substantially reduced compared to the $A^*$ search with a straight-line distance heuristic.

Keywords

References

  1. H. Alt, M. Godau and S. Whitesides, "Universal 3-dimensional visibility representations for graphs," Computational Geometry: Theory and Applications (9), 1998.
  2. M. de Berg, M. van Kreveld, M. Overmas, and O. Schwarzkorf, Computational Geometry-Algorithms and Applications, Springer-Verlag, New York, 2000.
  3. G. Dehghani and H. Morady, "An Algorithm for Visibility Graph Recognition on Planar Graphs," Proceedings of the ICFCC2009, 2009.
  4. F. Farnstorm, "Improving on Near-Optimality: More Techniques for Building Navigation Meshes," In: Rabin, S. (eds.): AI Game Programming Wisdom 3, Charles Rive Media, 2006.
  5. B. Gao, D. Xu, F. Zhang, and Y. Yao, "Constructing Visibility Graph and Planning Optimal Path for Inspection of 2D Workspace," Proceedings of the ICIS2009, 2009.
  6. D. H. Hale, G. M. Youngblood, and P. N. Dixit, "Automatically-generated convex region decomposition for real-time spatial agent navigation in virtual worlds," Proceedings of the fourth Conference on Artificial Intelligence and Interactive Digital Entertainment, 2008.
  7. D. Higgins, "Generic $A^{\ast}$ Pathfinding," AI Game Programming Wisdom, Charles River Media, 2002.
  8. G. Johnson, "Smoothing a Navigation Mesh path," In: Rabin, S. (eds.): AI Game Programming Wisdom 3, Charles Rive Media, 2006.
  9. J.C. Latombe, Robot Motion Planning, Kluwer Academic Publishers, 1991.
  10. C. McAnlis and J. Stewart, "Intrinsic Detail in Navigation Mesh Generation," In: Rabin, S. (eds.): AI Game Programming Wisdom 4, Charles Rive Media, 2008.
  11. M. NouriBygi and M. Ghodsi, "3D Visibility and Partial Visibility Complex," Proceedings of the ICCCSA2007, 2007.
  12. M. Pinter, "Towards more realistic pathfinding," Game Developer Magazine, April, 2001.
  13. S. Rabin, "$A^{\ast}$ speed optimizations and A* Aesthetic Optimizations," In: Deloura, M. (eds.): Game Programming Gems, Charles Rive Media, 2000.
  14. N. Sariff and N. Buniyamin, "An Overview of Autonomous Robot Path Planning Algorithms," Proceedings of the 4th Student Conference on Research and Development, 2006.
  15. G. Snook, "Simplified 3D Movement and Pathfinding Using Navigation Meshes," In: Deloura, M. (eds.): Game Programming Gems, Charles Rive Media, 2000.
  16. W. Sterren, "Terrain reasoning for 3D action games," Proceedings of the CGF-AI Conference, 2001.
  17. B. Stout, "The Basics of $A^{\ast}$ for Path Planning," In: Deloura, M. (eds.): Game Programming Gems, Charles River Media, 2002.
  18. P. Tozour, "Search Space Representations," In: Rabin, S. (eds.): AI Game Programming Wisdom 2, Charles Rive Media, 2004.
  19. P. Yap, "Grid-based Path-finding," Lecture notes in Artificial Intelligence, Vol. 2338, 2002.
  20. T. Young, "Expanded Geometry for Points-of-Visibility Pathfinding," In: Deloura, M. (eds.): Game Programming Gems 2, Charles Rive Media, 2001.

Cited by

  1. Design of Heuristics Using Vertex Information in a Grid-based Map vol.20, pp.1, 2015, https://doi.org/10.9708/jksci.2015.20.1.085
  2. Path-Planning for Group Movement in Dynamic Environments vol.18, pp.2, 2013, https://doi.org/10.9708/jksci.2013.18.2.117
  3. Efficient planning of NPC cluster movement in computer game environment vol.18, pp.1, 2015, https://doi.org/10.1007/s10586-014-0399-3