논문에서는 무리 짓기에 대한 공간분할 방법의 성능을 개선하는 알고리즘을 제안한다. 핵심 개념은 무리 속에서 움직이는 개체인 보이드가 지속적으로 자신의 방향과 위치를 변경시키나 자신의 다음 방향의 결정에 영향을 주는 k개의 가장 가까운 이웃인 kNN은 자주 바뀌지 않는다는 사실을 이용하여 성능을 개선하는 것이다. 본 논문에서 이전의 kNN을 이용하여 새로운 kNN이 변경되었는지를 판별하는 방법이 제안되었고, 제안된 방법의 정당성은 정리를 통하여 증명되었다. 제안된 방법은 구현되었으며, 기존의 공간분할 방법과 성능이 비교되었다. 비교 결과로부터 제안된 알고리즘이 초당 프레임 수 관점에서 기존의 알고리즘보다 약 30% 개선 효과를 주는 것을 알 수 있었다.

This paper proposes an algorithm to improve the performance of the spatial partitioning method for flocking behaviors. The core concept is to improve the performance by using the fact that even if a moving entity, boid in flock continuously changes its direction and position, its k-nearest neighbors, kNN to effect on decision of the next direction is not changed frequently. From the previous kNN, the method to check whether new kNN is changed or not is proposed in this paper and then the correctness of the proposed method is proved by two theorems. The proposed algorithm was implemented and its performance was compared with the conventional spatial partitioning method. The results of the comparison show that the proposed algorithm outperforms the conventional one by about 30% with respect to the number of frames per a second.

• 이재문 | Lee, Jae-Moon