[논문]대표 보이드를 이용한 대규모 무리의 효율적인 무리짓기

이재문

대표 보이드를 이용한 대규모 무리의 효율적인 무리짓기
An Efficient Flocking Behaviors for Large Flocks by Using Representative Boid 원문보기

한국게임학회 논문지 = Journal of Korea Game Society, v.8 no.3, 2008년, pp.87 - 95

초록
AI-Helper

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

Abstract ▼ AI-Helper

This paper proposes an algorithm for efficient behaviors of boids which freely move and have no predefined position. By finding the kNN and computing the value of behavioral characteristic of a boid approximately, the proposed algorithm improves the conventional spatial partitioning one. To do this, this paper defines and uses the representative boid which has the average direction and position for a group of boids. The proposed algorithm was implemented and compared with the conventional one experimentally. The results of the experimental comparisons show that the proposed algorithm outperforms the conventional one about $-5{\sim}130%$ in terms of the ratio of the number of rendering frames per the second.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 임의적으로 움직이는 보이드들에 대한 무리짓기 알고리즘을 제안하였다. 기존의 널리 알려진 공간 분할 무리짓기 알고리즘을 개선하는 것으로 근사적 kNN과 분리 특성에 대한 근사적 값을 계산하여 성능을 개선한다.
본 논문은 공간 분할 무리짓기 알고리즘에서 동일한 셀에 속하는 보이드들에 대한 대표 보이드를 정의하고 이를 사용하므로써 [그림 3]에서 kNN을 찾는 것과 ComputeSteerWithBoid를 효율적으로 계산하도록 하여 공간 분할 무리짓기 알고리즘의 성능을 개선한다. [그림 5]는 [그림 2]에서 보이는 공간 분할 무리짓기에서 부분적으로 대표 보이드를 도입하여 대표 보이드를 표시한 것이다.
[그림 3]에서 보이는 공간 분할 무리짓기 알고리즘의 가장 큰 병목요소는 임의의 보이드 b에 대하여 kNN을 찾는 것과 이러한 kNN을 이용하여 정렬벡터, 응집 벡터 및 분리 벡터를 계산하는 ComputeSteerWithBoid이다. 본 논문은 이들에 대한 계산을 근사적으로 함으로써 공간분할 알고리즘의 성능을 개선하고자 하는 것이다. 이를 위하여 본 논문에서는 다음과 같이 대표 보이드를 정의하여 사용한다.

제안 방법

여기서 SWPS는 StreeringWithPS의 초당 프레임 렌더링 수를 의미하며, SWRB는 StreeringWithRB의 초당 프레임 렌더링 수를 의미한다. 두 알고리즘의 성능은 kNN을 100에서 200까지 증가시키면서 측정하였고, 제안하는 알고리즘 StreeringWithRB에 대해서는 알고리즘에서 제시한 o를 1, 2, 3으로 변화시키면서 측정하였다. o가 증가하면서 StreeringWithRB의 성능이 낮아지는 것은 대표 보이드의 적용이 적어지고 따라서 알고리즘 라인 06～12에서 대표 보이드의 생성이 오버헤드가 되기 때문이다.
실험은 임의의 환경에서 두 알고리즘의 초당 실행 프레임 수를 비교하는 것으로 하였다. 무리짓기의 성능을 측정하고 비교하는 다양한 방법이 있겠으나 논문에서는 공간분할의 수를 변경하면서 성능을 측정하기로 한다. 이를 위하여 전체 보이드의 수는 1,024개로 고정하였으며, 2,000 프레임까지 렌더링하는 시간을 측정하여 초당 평균 렌더링 수를 측정하였다.
이것은 조종층의 계산이 공간상에 존재하는 모든 물체에 대하여 kNN을 찾아야 하고 이들을 이용하여 새로운 방향을 계산하여야 하기 때문이다. 본 논문에서는 무리짓기의 계산을 조종층의 계산으로 한정한다.
이러한 성질을 이용함에 있어서 대표 보이드를 생성하는 것 자체가 많은 계산량을 요구할 수 있다. 본 논문에서는 이의 비용을 줄이기 위하여 kNN을 찾을 때마다 대표 보이드를 생성하는 것이 아니라 알고리즘의 초기화의 일환으로 모든 셀에 대하여 대표 보이드를 사전에 생성하고, 이들을 kNN을 찾을때 마다 반복하여 사용하도록 한다. [그림 6]은 대표 보이드를 이용한 공간분할 무리짓기 알고리즘이다.
본 논문에서는 임의의 보이드 b의 kNN에 대하여 정리 1, 2, 4의 성질을 만족하는 부분적 보이드들에 대하여 대표 보이드를 계산하고, 이를 이용하여 근사적인 kNN, 정렬벡터, 응집벡터 및 분리벡터를 구함으로써 공간분할 무리짓기의 속도를 개선한다.
본 논문에서는 제안하는 알고리즘 StreeringWithRB의 성능을 측정하고 이를 비교하기 위하여 알고리즘 StreeringWithPS와 StreeringWithRB를 직접 구현하였다. 구현은 MS사의 비주얼 스튜디오 2005를 사용하여 C++로 구현하였고 OpenGL을 사용하였다.
본 논문에서는 후자의 방법에 대한 연구로써 근사적 kNN을 찾고, 이들에 대한 대표 보이드를 사용하여 정렬 규칙, 응집 규칙 및 분리 규칙을 근사적으로 계산하도록 하므로써 기존의 무리짓기 알고리즘의 성능을 개선한다. 2장에서는 정렬 규칙, 응집 규칙 및 분리 규칙의 계산 방법과 기존의 알고리즘에 대하여 설명하며, 3장에서는 새로운 알고리즘을 제안하며, 4장에서는 기존의 알고리즘과 제안하는 알고리즘의 성능을 비교 분석한다.
실험은 임의의 환경에서 두 알고리즘의 초당 실행 프레임 수를 비교하는 것으로 하였다. 무리짓기의 성능을 측정하고 비교하는 다양한 방법이 있겠으나 논문에서는 공간분할의 수를 변경하면서 성능을 측정하기로 한다.
기존의 널리 알려진 공간 분할 무리짓기 알고리즘을 개선하는 것으로 근사적 kNN과 분리 특성에 대한 근사적 값을 계산하여 성능을 개선한다. 이를 위하여 대표 보이드를 정의하였으며, 이를 이용하여 근사적 kNN을 찾고 무리짓기의 특성을 계산하도록 하였다. 제안하는 알고리즘의 성능을 측정하기 위하여 이를 구현하였으며, 기존의 알고리즘과 성능을 비교하였다.
무리짓기의 성능을 측정하고 비교하는 다양한 방법이 있겠으나 논문에서는 공간분할의 수를 변경하면서 성능을 측정하기로 한다. 이를 위하여 전체 보이드의 수는 1,024개로 고정하였으며, 2,000 프레임까지 렌더링하는 시간을 측정하여 초당 평균 렌더링 수를 측정하였다. 제안하는 알고리즘의 성능을 다양하게 측정하기 위하여 k를 변화시키면서 성능을 측정하였다.
예를 들어 (4, 4)-셀에서의 대표 보이드는 [그림 2]에서 (4, 4)-셀에 있는 3개의 보이드에 대한 대표 보이드이다. 제안하는 알고리즘은 보이드 b에 대한 kNN을 구할 때 모든 kNN을 구하는 대신에 [그림 5]에서와 같이 반경 o와 r사이에 있는 보이드들에 대해서 필요하다면 대표 보이드를 구함으로써 kNN을 탐색하는 비용을 줄이고 ComputeSteerWithBoid를 효율적으로 계산하는 것이다. 반경 o와 r사이에 있는 보이드들에 대하여 대표 보이드를 적용하는 것은 정리 4의 성질을 이용하고자 하는 것이다.
이를 위하여 전체 보이드의 수는 1,024개로 고정하였으며, 2,000 프레임까지 렌더링하는 시간을 측정하여 초당 평균 렌더링 수를 측정하였다. 제안하는 알고리즘의 성능을 다양하게 측정하기 위하여 k를 변화시키면서 성능을 측정하였다.

대상 데이터

구현은 MS사의 비주얼 스튜디오 2005를 사용하여 C++로 구현하였고 OpenGL을 사용하였다. 실험 환경으로는 펜티움4 2.5GHZ, 메모리 2GB의 PC를 사용하였고 운영체제로는 윈도우즈 XP를 사용하였다.

데이터처리

본 논문에서는 제안하는 알고리즘 StreeringWithRB의 성능을 측정하고 이를 비교하기 위하여 알고리즘 StreeringWithPS와 StreeringWithRB를 직접 구현하였다. 구현은 MS사의 비주얼 스튜디오 2005를 사용하여 C++로 구현하였고 OpenGL을 사용하였다. 실험 환경으로는 펜티움4 2.
이를 위하여 대표 보이드를 정의하였으며, 이를 이용하여 근사적 kNN을 찾고 무리짓기의 특성을 계산하도록 하였다. 제안하는 알고리즘의 성능을 측정하기 위하여 이를 구현하였으며, 기존의 알고리즘과 성능을 비교하였다. 성능 비교 결과 환경에 따라 -5～130%까지의 개선 효과를 주었다.

성능/효과

제안하는 알고리즘의 성능을 측정하기 위하여 이를 구현하였으며, 기존의 알고리즘과 성능을 비교하였다. 성능 비교 결과 환경에 따라 -5～130%까지의 개선 효과를 주었다.
그렇지만 o가 작다는 것은 더 많은 보이드에 대하여 대표 보이드를 적용하는 것이고 따라서 정리 3과 4의 결과로부터 예측할 수 있듯이 보이드들의 행동에 대한 자연스러움이 떨어질 수 있다. 실험 결과 o가 3인 경우 제안하는 알고리즘에서의 보이드들의 움직임과 기존의 알고리즘에서의 보이드들의 움직임이 다르다는 것을 시각적으로 구별할 수 있는 정도였고, o가 2 이하인 경우 두 알고리즘에서의 보이드들에 대한 움직임의 차이를 시각적으로 구별할 수 없었다.
[7]에서는 효율적으로 인접 셀을 찾는 알고리즘을 제시하고 있다. 알고리즘으로부터 k가 전체 보이드의 수 n에 대하여 작은 값일 경우 매우 빠른 성능을 보일 것을 알 수 있다. [그림 3]에서 라인 10～21이 k번 반복되므로 이 알고리즘의 전체 시간 복잡도는 O(kn)이 된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	주어진 반경 내에 있는 모든 다른 보이드들을 선택하는 방법은 어떤 단점을 가지고 있나?	후자의 방법을 일반적으로 kNN(k-nearest neighbors)이라 부른다. 전자는 비교적 간단한 알고리즘에 비하여 임의의 보이드들에 대하여 영향을 주는 주변 보이드들의 수가 일정하지 않다는 단점을 갖고 있다. 후자는 전자의 단점을 보완하는 것으로 항상 k개의 가장 가까운 이웃 보이드들만 영향을 주도록 제어할 수 있는 반면 k번째 주변에 많은 보이드가 존재하는 경우 이들에 대하여 정확한 식별이 필요하므로 비용이 많이 든다.
	무리짓기란 무엇인가?	무리짓기란 메뚜기 떼와 같이 무리를 지어서 다니는 동종의 수많은 보이드(정해진 위치가 없이 자유롭게 움직이는 객체)들의 자동 움직임을 말한다. 이러한 무리의 특징은 무리를 이끄는 우두머리도 없을 뿐만 아니라 어디로 이동할지 예측하지 못한다는 것이다.
	무리짓기의 가장 주목할 만한 특징은?	무리짓기의 가장 주목할 만한 특징은 각각의 보이드는 무리에 대한 어떠한 정보도 가지지 않는다는 점이다. 즉, 각각의 보이드는 매 순간마다 자신의 주변을 다시 평가할 뿐, 무리에 대한 정보는 전혀 가지고 있지 않다.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증