Implementasi Algoritma K-D Tree pada Pembuatan 3D Dungeon Generator Menggunakan Metode Prosedural Modeling

Abstract

The Gaming industry is one of the largest industries in the world that continues to grow. One of the techniques that support this development is Procedural Content Generation (PCG). PCG is often used to create game environments, especially games with the Role-Playing Game (RPG) genre. In the RPG genre, one of the important elements is the dungeon. However, dungeons created without the PCG method tend to have static layouts, reducing the variety and level of playing experience. This study aims to develop a 3D Dungeon Generator in the form of a plugin that is able to produce a variety of 3D dungeon layouts with the procedural modeling method. The method used is the implementation of the K-D Tree algorithm as a partition technique in forming dungeon rooms. Development was carried out using the Houdini Engine to form a 3D Dungeon Generator which was then tested on the Unity Engine. The results of the study showed that the K-D Tree algorithm was successfully implemented and was able to produce a balanced 2D room partition structure, with corridors connecting all rooms. The resulting dungeon generator was able to produce 3 to 30 rooms with varying layouts. In conclusion, the implementation of the K-D Tree algorithm is effective in supporting the procedural modeling process in creating a 3D Dungeon Generator.