Procedural Maze Generation System for Three Dimensional Polygon Surface

미로는 컴퓨터 비디오 게임에 매우 자주 사용되는 형태 중의 하나다. 2차원 격자 형태로 표현되는 미로가 가장 대표적이지만 매우 다양한 형태로 사용된다. 많은 게임 애셋들이 그래픽 디자이너에 의해 만들어지지만 알고리즘에 의해 자동화되는 경우도 매우 많다. 특히 최근에는 프로시저럴 게임 애셋 생성 방법이 각광을 받으며 게임 애셋의 제작에 있어 생산성이 높아질 수 있게 되었다. 제안된 연구에서는 그동안 2차원 미로 생성에 제한되어 있어서 자동화 방법을 3차원 그래픽으로 확장하고자 한다. 2차원 미로 생성 방법은 컴퓨터 사이언스에서 오래된 주제인다. 게임에서는 주로 던전이나 레벨 생성에 주로 사용되고 있다. 최근의 미로에 관련된 연구는 이미지나 사진을 기반으로 이와 닮은 형태의 미로를 생성하는 방법과 이에 대한 사용자 컨트롤, 스타일 생성 등에 대해 이루어지고 있다. 본 연구에서는 이에 대한 3차원 확장으로써 미로 자동 생성 시스템을 제안한다. 경로 생성과 3차원 벽 모델의 생성은 PCG(Procedural Contents Generation)로 이루어지며 미로의 생성 밀도나 형태 제어, 불연속성 제어 등은 사용자가 개입할 수 있는 형태로 구현되었다. 또한 사용자가 지정한 출발, 도착 지점 셀간의 해답 경로를 자동으로 생성하여 준다. 제안된 시스템은 이러한 기능들을 대화형 작업 속도로 지원한다.

Mazes are one of the most commonly used forms for computer video games. The maze expressed in the form of a two-dimensional grid is the most representative, but it is used in a wide variety of forms. Many game assets are created by graphic designers, but are often automated by algorithms. In particular, recently, the method of creating procedural game assets has been in the spotlight, and the productivity of game assets can be increased. The proposed study has been limited to the creation of a 2D maze, so we intend to extend the automation method to 3D graphics. How to create a 2D maze is an old subject in computer science. In games, it is mainly used for dungeons and level creation. A recent maze-related study has been conducted on a method of generating a maze similar to this based on an image or a photograph, user control, style creation, and the like. This study proposes an automatic maze generation system as a three-dimensional extension. Path generation and creation of a 3D wall model consist of PCG (Procedural Contents Generation), and the maze generation density, shape control, and discontinuity control are implemented in a form that can be intervened by the user. In addition, the answer route between the user-specified departure and arrival point cells is automatically generated. The proposed system supports these functions at an interactive working speed.