13. Performance Analysis for Partitioning Size in Flocking Behavior Algorithm Based on Spatial Partitioning Method

Title(KR)

• 공간분할에 기초한 무리 짓기 알고리즘에서 분할 크기에 따른 성능 분석

Title(ENG)

• Performance Analysis for Partitioning Size in Flocking Behavior Algorithm Based on Spatial Partitioning Method

Keywords(KR)

• 무리 짓기, 에이전트, k-개의 가장 가까운 이웃, 공간분할, 시간 복잡도

Keywords(ENG)

• Flocking behavior, Agent, k-nearest neighbor, Spatial partitioning, Time complexity

Author

• Jae Moon Lee, Sung Dong Kim

Abstract(KR)

본 논문은 공간분할에 기초한 무리 짓기 알고리즘에서 적절한 분할의 크기를 제시한다. 이것은 공간분할에 기초한 무리 짓기의 알고리즘의 성능이 에이전트의 수, 이웃 에이전트들의 수뿐만 아니라 분할의 크기에도 의존하기 때문이 다. 에이전트 수 및 이웃 에이전트들의 수는 게임 환경에 의하여 고정되는 반면, 분할의 크기는 게임 환경에 관계없이 선택될 수 있기 때문에 최적화가 가능하다. 이를 위하여, 공간분할에 기초한 무리 짓기 알고리즘의 성능은 시간 복잡 도 및 실험적 방법을 통하여 다양한 분할의 크기에 따라 분석되었다. 분석 결과는 대부분의 3D 환경에서 분할의 크기 가  에이전트의수 일 때 좋은 성능을 얻을 수 있음을 보였다.

Abstract(ENG)

This paper proposed the proper partitioning size of the flocking behavior algorithm based on the spatial partitioning method. It is because the performance of the flocking behavior algorithm based on the spatial partitioning method is dependent on not only the number of agents and the number of the neighborhood, but also the partitioning size. While the number of agents and the number of the neighborhood are fixed by the game environment, it is possible to be the optimal because the partitioning size can be selected without related to the game environment. To do this, the performances of the flocking behavior algorithm were analyzed according to the various partitioning size by using the time complexity and the experiments. The results of the analysis have shown that in the most of 3D environments, the algorithm has the good performance when the partitioning size is   .

Page 111-118