V11 N2 Paper 2
Annals of the MS in Computer Science and Information Systems at UNC Wilmington
Fall 2017

Optimization of Spatial Partitioning for 3D-Pathfinding Specified for Sparsely Populated, Simulated Environments  

Brian Abdo

Committee

Brittany Morago (chair)
Tom Janicki
Hyunbym Kim

Abstract

Pathfinding in 3D-Space is one of the more novel and complex use cases in a world where the advent of new technology is abundant. Drones, Robotics, Simulations, and Game Development have dealt with the stated use case for some time. Depending on the specific requirements, a solution is presented that almost always differentiates vastly from its brethren. More often than not, it’s the pathfinding methodology that is optimized over the spatial partitioning structure itself if a partitioning structure is used at all. This paper analyzed and optimized an Octree data structure for 3D pathfinding by using and integrating current methodology in conjunction with A* pathfinding. The A* pathfinding methodology was a standard version with the stated goal of testing the usefulness of the implemented methodology for optimization in a variety of 3D-pathfinding scenarios. Many portions of this paper are exploratory as the subject of spatial partitioning in 3D has been developed for many fields other than strictly computer science. Modeling is the primary implementer of the structure style required and much of this paper has referenced the historical and theoretical work of that field.

download (pdf)

Recommended Citation: Abdo, B., Morago, B, Janicki, T., Kim, H. (2017) Optimization of Spatial Partitioning for 3D-Pathfinding Specified for Sparsely Populated, Simulated Environments. Annals of the Master of Science in Computer Science and Information Systems at UNC Wilmington, 11(2) paper 2. http://csbapp.uncw.edu/data/mscsis/full.aspx.

V11 N2 Paper 2
Annals of the MS in Computer Science and Information Systems at UNC Wilmington
Fall 2017