MMORPG에서 QuadTree의 단노드를 이용한 그리드 공간 분할 기법

A Grid space partition method using leaf nodes of QuadTree on MMORPG

최근 컴퓨터 하드웨어의 급속한 발전으로 3D 게임 산업이 발전하고 온라인상에서 여러 사용자가 즐기는 3D 온라인 게임이 증가하면서 대규모 실외 지형의 실시간 공간 분할 기법이 중요한 주제로 떠오르고 있다. 본 논문에서는 MMORPG에서 눂이값을 가지지 않는 정적/동적 객체에 대하여 보다 효율적인 공간분할을 할 수 있도록 기존의 공간분할 방법의 하나인 QuadTree기법을 개선하여 보다 빠른 렌더링 향상을 위한 공간 분할 기법을 제안하였다. 또한 기존 공간 분할 기법과의 시뮬레이션 결과를 통하여 제안한 알고리즘이 MMORPG 온라인 게임에서 더 빠른 렌더링 향상을 보였다.

Many geometric algorithms are based on spatial partitions. One of the most popular methods to obtain a composition of space is with a QuadTree. This method is usually used for space partitioning some static objects, moving objects, and massive map in 3D computer games. We present a new method to do space-partitioning for dynamic and static objects using leaf nodes of QuadTree on MMORPG. But this space partition method is not useful when a hero does not moving upward such as jumping or flying. The new method is based on a simple technique for space partitioning using a QuadTree without root nodes. The simulation result shows good rendering frame rate. The response time of the rendering per second is O(logn) in the worst case, and O(1) expected.