Efficient method for finding nearest neighbors in flocking behaviors using k-dimensional trees

Abstract

Flocking is a behavior where a group of objects travel, move or collaborate together. By learning more about flocking behavior, we might be able to apply this knowledge in different contexts such as computer graphics, games, and education. A key steppingstone for understanding flocking behavior is to be able to simulate it. However, simulating behaviors of large numbers of objects is highly compute-intensive task because of the n-squared complexity of nearest neighbor for separating n objects. The work in this paper presents an efficient nearest neighbor method based on the k-dimensional trees (KD trees). To evaluate the proposed approach, we apply it using Unity-3D game engine, together with other conventional nearest neighbor methods. The Unity-3D game simulation engine allows users to utilize interaction design tools for programming and animating flocking behaviors. Results showed that the proposed approach outperform other conventional nearest neighbor approaches. The proposed approach can be used to enhance digital games quality and simulations.