3차원 지형에서 멀티 유닛을 위한 지능형 경로 탐색 기법

An Intelligent Path-Finding Technique for Multi-Unit on 3D Terrain

근래의 게임은 개인용 컴퓨터의 하드웨어와 네트워크 기술의 발달로 인해, 지형 및 캐릭터의 숫자 등 게임의 전반적인 규모가 커지고 있으며, 이에 따라, 게임을 즐기는 유저들의 요구와 기대수준 역시 향상되었고, 게임의 양적 대형화를 뒷받침할 수 있는 인공지능 기술 향항의 필요성이 커지고 있다. 본 논문에서는 그 동안 연구되었던 2차원 지형에서의 경로 탐색 기법을 개량하여 3차원 지형에서 올바르게 작동하는 경로 탐색 기법에 대해 제안한다. 특히 3차원 지형에서 유닛의 집단을 위한 구성 방법과 대형을 유지하면서 이동 가능한 경로 탐색 기법에 대해 연구하며, 연산속도 향상을 위해 GPU 하드웨어 지원 계산이 가능하도록 기반 데이터 구조를 설계하는 연구 과정을 설명한다.

The Massive Multiplayer Online Game(MMOG) is a rapidly growing area in the Computer Hardware industry of 3D Games. Unlike the earlier networked games, MMOG aims to support a very large number of concurrent users and NPCs(Non-Player Character), in terms of thousands and even tens of thousands. Therefore, game developer should consider how they construct vast game terrains and how they control a great number of characters. There are many areas of technical expertise in the development of game. Here, I only consider the area of path-finding issues, such as the A* and Dijkstra's algorithm, and especially consider how to maintain the formation of multi-unit. and for more efficient calculations, I will use GPU(Graphic Processing Unit) based processing.