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

Marwan Al-Tawil, Moh’d Belal Al-Zoubi, Omar Y. Adwan, Ammar Al-Huneiti, Reem Q. Al Fayez


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.


Algorithms; Flocking behavior; K-dimensional trees; Nearest neighbor; Simulation

Full Text:


DOI: http://doi.org/10.11591/ijai.v12.i4.pp1628-1635


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

IAES International Journal of Artificial Intelligence (IJ-AI)
ISSN/e-ISSN 2089-4872/2252-8938 
This journal is published by the Institute of Advanced Engineering and Science (IAES) in collaboration with Intelektual Pustaka Media Utama (IPMU).

View IJAI Stats