Abstract
Pathfinding plays a vital role in video games, whether in terms of gameplay mechanics or player immersion. Commonly used methods only allow the simplest types of movements like walking and running. Although seldom, other types of movement like swimming and flying are also considered. Even rarer are mechanisms that natively contemplate jumps, without the need of extra intervention of game developers. Most games overlook these movements on Non Player Characters, affecting player experience. This article discusses the limitations of Navigation Meshes when it comes to take jumps into consideration and proposes a new solution using grid-based any-angle pathfinding. Each cell of this navigation grid constitutes a voxel that delimits a small 3D space and is expressed in a shape of a cube. Voxels discretize the game world and are explored by a search algorithm to achieve pathfinding with jumps. Performance is critical and found paths should be optimal and efficient. Results show that the proposed solution can be successfully applied in game development.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Sturtevant, Nathan R.: Moving path planning forward. In: Kallmann, M., Bekris, K. (eds.) MIG 2012. LNCS, vol. 7660, pp. 1–6. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34710-8_1
Mononen, M.: Recast Navigation (2009). https://github.com/recastnavigation/recastnavigation. Accessed 16 July 2018
Madhav, S.: Game programming algorithms and techniques: a platform-agnostic approach. In: Pearson Education, pp. 180–192 (2014)
Daniel, K., Nash, A., Koenig, S., Felner, A.: Theta*: any-angle path planning on grids. J. Artif. Intell. Res. 39, 533–579 (2010)
Yap, P., Burch, N., Holte, R.C., Schaeffer, J.: Any-angle path planning for computer games. In: Proceedings of the Seventh AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE-11), pp. 201–207 (2011)
Abd Algfoor, Z., Sunar, M.S., Kolivand, H.: A comprehensive study on pathfinding techniques for robotics and video games. Int. J. Comput. Games Technol. 2015, 11 (2015)
Nash, A., Koenig, S.: Any-angle path planning. AI Mag. 34(4), 85–107 (2013)
Sreedharan, V.: DoN AI Navigation–A free plugin for Unreal Engine 4, Drunk On Nectar - The Nature Simulator (2017). http://www.drunkonnectar.com/3d-pathfinding-ue4/. Accessed 16 Apr 2019
Andrade, E., Coelho, B., Reis, G., Grilo, C.: JumpingAI–autonomous jumping for unreal engine 4. In: Conference of Sciences and Arts of Video Games (Videogames 2017) (2017)
Rama, AI Navigation in C ++, Customize Path Following Every Tick. https://wiki.unrealengine.com/AI_Navigation_in_C%2B%2B,_Customize_Path_Following_Every_Tick. Accessed 16 July 2018
Unity|Documentation : Building Off-Mesh Links Automatically. https://docs.unity3d.com/Manual/nav-BuildingOffMeshLinksAutomatically.html. Accessed 16 July 2019
Yao, J., Lin, C., Xie, X., Wang, A.J., Hung, C.-C.: Path planning for virtual human motion using improved A* star algorithm. In: 2010 Seventh International Conference on Information Technology: New Generations, pp. 1154–1158 (2010)
Hart, P.E., Nilsson, N.J., Raphael, B.: Formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Silva, G., Reis, G., Grilo, C. (2019). Voxel Based Pathfinding with Jumping for Games. In: Moura Oliveira, P., Novais, P., Reis, L. (eds) Progress in Artificial Intelligence. EPIA 2019. Lecture Notes in Computer Science(), vol 11804. Springer, Cham. https://doi.org/10.1007/978-3-030-30241-2_6
Download citation
DOI: https://doi.org/10.1007/978-3-030-30241-2_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-30240-5
Online ISBN: 978-3-030-30241-2
eBook Packages: Computer ScienceComputer Science (R0)