이전 k 개의 가장 가까운 이웃을 이용한 무리 짓기에 대한 공간분할 방법의 개선 (An Improvement Of Spatial Partitioning Method For Flocking Behaviors By Using Previous -Nearest Neighbors)

서지정보

· 발행기관 : 한국게임학회
· 수록지 정보 : 한국게임학회 논문지 / 9권 / 2호 / 115 ~ 124페이지
· 저자명 : 이재문

초록

본 논문에서는 무리 짓기에 대한 공간분할 방법의 성능을 개선하는 알고리즘을 제안한다. 핵
심 개념은 무리 속에서 움직이는 개체인 보이드가 지속적으로 자신의 방향과 위치를 변경시키
나 자신의 다음 방향의 결정에 영향을 주는 개의 가장 가까운 이웃인 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.

참고자료

· 없음