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

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      

요약   ABSTRACT   I. 서론   II. 공간분할 알고리즘    1. 무리 짓기 공간분할 알고리즘    2. 이웃 에이전트들 찾기의 성능 요소   III. 이웃 에이전트 찾기 분석    1. 시간복잡도를 이용한 분석    2. 실험을 이용한 분석   IV. 결론   참고문헌

• 이재문(한성대학교 멀티미디어공학과) | Jae Moon Lee
• 김성동(계원디자인예술대학 게임웨어과) | Sung Dong Kim