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

• 영문명: Performance Analysis for Partitioning Size in Flocking Behavior Algorithm Based on Spatial Partitioning Method
• 발행기관: 한국컴퓨터게임학회
• 저자명: 이재문(Jae Moon Lee) 김성동(Seong Dong Kim)
• 간행물 정보: 『한국컴퓨터게임학회논문지』제20호, 111~118쪽, 전체 8쪽
• 주제분류: 공학 > 컴퓨터학
• 파일형태: PDF
• 발행일자: 2010.03.30

국문 초록

본 논문은 공간분할에 기초한 무리 짓기 알고리즘에서 적절한 분할의 크기를 제시한다. 이것은 공간분할에 기초한 무리 짓기의 알고리즘의 성능이 에이전트의 수, 이웃 에이전트들의 수뿐만 아니라 분할의 크기에도 의존하기 때문이다. 에이전트 수 및 이웃 에이전트들의 수는 게임 환경에 의하여 고정되는 반면, 분할의 크기는 게임 환경에 관계없이 선택될 수 있기 때문에 최적화가 가능하다. 이를 위하여, 공간분할에 기초한 무리 짓기 알고리즘의 성능은 시간 복잡도 및 실험적 방법을 통하여 다양한 분할의 크기에 따라 분석되었다. 분석 결과는 대부분의 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 ？？ ？煬諱？ ？？   ？？ .

목차

1. 서 론

Ⅱ. 공간분할 알고리즘

Ⅲ. 이웃 에이전트 찾기 분석

Ⅳ. 결론

참 고 문 헌

키워드

무리 짓기 에이전트 k-개의 가장 가까운 이웃 공간분할 시간 복잡도 Flocking behavior Agent k-nearest neighbor Spatial partitioning Time complexity