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

본 논문은 컴퓨터 애니메이션에서 많이 활용되는 자동 에이전트에 대한 무리 짓기의 설계 및 구현에 관한 연구이다. 잘 알려진 무리 짓기의 방법을 공개용 게임 엔진인 오우거 게임 엔진에 설계 및 구현하였다. 공개용 게임 엔진에구현함으로써 실험용이 아닌 실제 상황에서 무리 짓기의 성능을 측정하고 분석할 수 있었다. 또한 이웃 에이전트를 제한하는 쿼리 반경을 조정함으로써 무리 짓기의 다양한 형태를 관찰할 수 있었고, 이는 향후 무리 짓기의 애니메이션에서 무리의 형태 제어 기법으로 활용될 수 있다.

플로킹은 컴퓨터 게임에 등장하는 캐릭터들의 집단행동 처리방법으로 활용되고 있다. 본 논문은 트리를 이용하여 무리의 집단행동을 표현하기 위한 자료 구조로 사용한다. 트리는 자료의 추가와 삭제가 쉽고 개체를 표현하기 위한 적합한 자료구조로 사용된다. 트리로 표현된 개체를 블록덮개를 사용하여 단순화된 불록 입방체로 표현한다. 이러한 처리 방식은 정확성도 높이고 성능 및 메모리 사용량을 충분히 낮출 수 있다. 또한 플로킹에 대한 기본 규칙 및 패턴을 분석하고 충돌처리를 통하여 무리의 상태를 제어한다. 효율적인 무리제어를 위하여 무리를 여러 그룹으로 세분화하여 블록덮개로 표현한다. 이벤트의 처리는 세분화되어 개체집단별로 구분되어 처리된다. 블록덮개의 밀도는 정체지역과 다른 개체와의 결합 및 분리를 위한 자료로 사용한다. 영향력 분포 및 시야 범위는 처리량을 제한하기 위한 방법이다. 본 논문에서는 제시된 처리 방법들을 통하여 게임에서 분대 단위의 무리 이동과 전투 등의 이벤트를 수행 할 수 있는 효율적인 지능 시스템을 제시했다.

무리 짓기는 대규모 무리의 사실적인 시뮬레이션으로 게임이나 컴퓨터 그래픽에서 자주 사용된다. 이러한 대규모 무리의 실시간 시뮬레이션은 계산 집약적 작업이기 때문에 효율적인 알고리즘에 대한 많은 연구들이 있었다. 본 논문에서는 기존의 효율적인 무리 짓기 알고리즘이 불필요한 계산을 포함하고 있다는 사실은 실험적으로 찾아내고, 간단한 휴리스틱으로 이러한 단점을 개선하는 새로운 알고리즘을 제안한다. 제안된 방법의 성능을 평가하기 위하여 많은 실험을 수행하였다. 실험의 결과는 제안하는 알고리즘이 기존의 효율적인 알고리즘에 비하여 평균 약 21%정도 성능을 개선한다는 것을 보였다.

논문은 GPU를 이용한 무리 짓기에 대한 병렬 알고리즘을 제안한다. 이를 위하여 GPU의 병렬처리 구조로 CUDA를 사용하였으며, 그것의 특성 및 제한 요소들을 분석하였다. 이의 특성 및 제한 요소를 기초로 무리 짓기에서 가장 많은 비용을 요구하는 이웃 에이전트들을 찾는 것을 병렬화 함으로써 성능을 개선하였다. 제안된 알고리즘을 GTX 285상에서 구현하였고, 그것의 성능을 실험적으로 기존의 공간분할 알고리즘과 비교하였다. 비교의 결과는 제안된 알고리즘이 실행 시간 관점에서 최대 9배 정도 우수하다는 것을 보였다.

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

본 논문에서는 임의적으로 움직이고 미리 정해진 위치가 없는 보이드들의 효율적인 무리짓기 대한 알고리즘을 제안한다. 하나의 보이드에 대하여 근사적으로 kNN을 찾고 행위특성의 값을 계산함으로써 제안하는 알고리즘은 기존의 공간 분할 알고리즘을 개선한다. 이를 위하여, 본 논문은 보이드들의 한 그룹에 대하여 평균 방향과 위치를 갖는 대표 보이드를 정의하여 사용한다. 제안하는 알고리즘은 구현되었으며 기존의 알고리즘과 실험적으로 비교되었다. 실험적 비교 결과로부터 제안하는 알고리즘이 기존의 알고리즘에 비하여 초당 렌더링 프레임 수 관점에서 약 -5~130%까지의 개선 효과가 있음을 알 수 있었다.