Procedural content generation map pada game puzzle 3D dengan genetic algorithm

Penelitian ini mengusulkan penggunaan Genetic Algorithm (GA) untuk men-generate map secara prosedural pada game puzzle 3D dengan struktur level kubus enam sisi. Permasalahan utama yang diangkat adalah kesulitan dalam mendesain map yang bervariasi, solvable, menantang, dan memiliki koneksi antar sisi yang logis secara manual, terutama untuk game dengan puluhan hingga ratusan level. Tujuan skripsi ini adalah mengembangkan Procedural Content Generation (PCG) menggunakan GA yang mampu menghasilkan map yang bervariasi, solvable, dan memenuhi kendala yang ditetapkan pada setiap sisi kubus. Metode penelitian mencakup perancangan sistem GA, termasuk representasi kromosom (array 3D 6x10x10) dimana setiap sisi dari kubus merupakan array 10x10 yang saling terhubung dengan sisi lainnya, dan fungsi fitness yang mengevaluasi solvability (menggunakan modified A* yang mensimulasikan gravitasi + interaksi dengan obstacle), panjang jalur, serta distribusi tile. Proses seleksi menggunakan Roulette Wheel, diikuti oleh crossover dimana setiap sisi dari parent dibagi menjadi 4 sisi kemudian menggabungkan region region dari dua parent terpilih untuk membentuk setiap sisi dari child yang dihasilkan, dan mutasi yang memilih 1-4 region secara acak. kemudian dirotasi. Hasil pengujian menunjukkan bahwa GA dapat menghasilkan map yang kompleks dan memiliki distribusi tile yang lebih merata, terutama dengan parameter populasi 40 dan generasi 100. Pada konfigurasi ini, 60% dari 50 level yang dievaluasi memenuhi kriteria yang ditetapkan, dengan highest fitness tercatat 408 dan rata-rata fitness score 293.674988. Hal ini menunjukkan bahwa GA efektif dalam menciptakan map yang dinamis dan meningkatkan replayability, meskipun masih ditemukan kasus map unsolvable atau interaksi switch/door yang minim.

NICHOLAS Hans Juwiantho, S.Kom., M.Kom. (Advisor 1); Liliana (Advisor 2); Justinus Andjarwirawan (Examination Committee 1); Gregorius Satiabudhi (Examination Committee 2) Universitas Kristen Petra Indonesian Digital Theses Undergraduate Thesis Skripsi/Undergraduate Thesis Skripsi No. 01022738/INF/2025; Nicholas (C14210110) GENETIC ALGORITHMS; VIDEO GAMES--DESIGN; THREE-DIMENSIONAL MODELING; ALGORITHMS

Files