JPS Algorithm Adaptation and Optimization to Three-dimensional Space

Abstract

The aim of this thesis is to research the principles of the Jump Point Search (JPS) pathfinding algorithm and study the possibilities of adapting JPS to three-dimensional environment. JPS is partly based on A* algorithm but its performance is significantly better than the original A* algorithm. At the moment, there is no known 3D pathfinding algorithm published which uses the same principles as JPS. The motivation of this work is to find out what changes will be needed on the algorithm so that it will work in 3D and improve performance of the 3D version. Special target is performance comparison to the original A* algorithm and 3D JPS algorithm on inside a layered 3D space (building). Pathfinding inside building is common pathfinding problem in a video games as well it has importance also in real life. The algorithms were implemented by using Unity 3D game engine with C# language. For the purpose of research, A* and JPS algorithms were tested in the same 3D test environment. This arrangement made it possible to run the algorithms with the same test data to get a meaningful performance comparison between the algorithms. As a result, this gives also the exact principles how to adapt JPS Algorithm on a 3D environment. Moreover, it provides a novel idea and practical implementation on how to optimize the JPS 3D algorithm to get an improved performance. The presented results also include performance measurements for comparing JPS 3D method and its optimized variant in different environments.