KUCG :::: Korea University Computer Graphics ::::

1. 연구 개요

하드웨어와 기술의 발달로 인하여 3D 가상 세계에 대한 연구가 가속화되고 있다. 2D 가상 세계와는 다르게 3D 가상 세계의 경우 복잡한 지형과 다양한 형태의 물체들을 포함하는 경우가 많다. 이러한 복잡한 환경에서 목적지까지 적합한 경로를 찾는 것 또한 하나의 문제로서 많은 연구에서 다뤄지고 있다. 본 연구에서는 유저의 경로 데이터를 분석하여 적합한 경로를 찾는데 도움이 될 수 있도록 하였다.

2. 관련 연구

A* 알고리즘은 가상 세계에서 실시간으로 경로를 탐색하는데 있어서 가장 많이 사용된다. 3D 가상 세계의 경우 복잡한 지형 데이터를 포함하고 있는 경우가 많아서 일반적으로 그 지형 데이터 위에 Navigation Mesh를 덮어 씌워서 경로 탐색 알고리즘을 사용한다.
본 연구분야에서는 크게 2부분으로 나눠서 연구가 진행되고 있다. 첫번째로는 경로 탐색 알고리즘을 향상시키는 연구이다. A* 알고리즘의 경우 대부분의 3D 가상 세계에서 잘 작동하지만, 여전히 탐색시간이 오래 걸리고 저장 공간을 차지하는 문제가 있다. 두번째로는 Navigation Mesh 생성에 관한 연구이다. 소규모의 3D 가상 세계의 경우 디자이너들이 수동적으로 Navigation Mesh를 지형 데이터 위에 생성할 수 있지만, 현재 개발된 3D 가상 세계들의 경우 규모가 거대하여 일정수준 자동화에 의존할 수 밖에 없다. 하지만 자동화의 경우 알고리즘에 매우 의존적이며 제대로 생성이 안되는 어려움이 있다.

3. Technical Issue

본 연구에서는 사용자의 경로 데이터를 이용하여 Navigation Mesh를 재생성하고 A* 알고리즘을 향상시키는 방법을 제안하였다. 적은 메모리 사용으로 사용자를 관찰하고 Navigation Mesh를 생성하기 위하여 Region of interest (ROI), Agent of interest (AOI), Discretized path graph (DPG)의 3가지 자동 샘플링 기법을 제안하였다. ROI를 통해 모든 지역을 관찰하지 않고 세부적으로 Navigation Mesh가 필요한 부분만 관찰하고, AOI를 통해 새로운 경로를 찾을만한 사용자만을 관찰한다. 끝으로 DPG를 통해 모아진 경로의 샘플을 통해 Navigation Mesh를 생성한다. 본 기법은 다양한 환경의 3D 가상 세계에 사용가능 함을 확인하였다.

4. 결과

Original navigation meshes (above) and adaptive agent navigation on the newly generated meshes (below)

An NPC routing case (above) and adaptive NPC navigation (below)

5. Related publication

Shin-Jin Kang, YongO Kim and Chang Hun Kim, "Live path: adaptive agent navigation in the interactive virtual world," The Visual Computer, Volume 25, Number 5-7, pp. 469-477, June 2010.

136-713 서울 성북구 안암동5가 고려대학교 우정정보통신관 407B호 그래픽스 연구실
Graphics Lab. 407B Woojung Bldg. Korea University, Anam-dong 5(o)-ga, Seongbuk-gu, Seoul, 136-713 Rep. of KOREA
TEL l 02-3290-3574 / FAX | 02-953-0771
ⓒ KUCG, Korea University