Penggunaan Divide and Conquer pada Proses Generasi Map 2D menggunakan Algoritma Wave Function Collapse

Abhinaya, Rajendra (2025) Penggunaan Divide and Conquer pada Proses Generasi Map 2D menggunakan Algoritma Wave Function Collapse. Bachelor Thesis, Universitas Multimedia Nusantara.

	PDF HALAMAN_AWAL.pdf Download (908kB)
	PDF BAB_I.pdf Download (214kB)
	PDF BAB_II.pdf Download (237kB)
	PDF BAB_III.pdf Download (532kB)
	PDF BAB_IV.pdf Restricted to Registered users only Download (4MB)
	PDF BAB_V.pdf Download (208kB)
	PDF DAFTAR_PUSTAKA.pdf Download (214kB)
	PDF LAMPIRAN.pdf Restricted to Registered users only Download (267kB)

Abstract

Procedural content generation merupakan sebuah teknik yang sering digunakan dalam pembuatan konten. Procedural content generation merupakan proses penggunaan algoritma-algoritma untuk dapat membuat konten secara otomatis. Salah satu bentuk konten yang dapat dibuat menggunakan metode ini adalah maps yang digunakan pada sebuah game. Maps merupakan bentuk konten penting yang memberi variasi pada penglaman pemain. Penggunaan procedural content generation untuk membuat maps dapat memberi berbagai keuntungan seperti penghematan biaya, waktu, dan tenaga kerja. Salah satu algoritma yang dapat digunakan adalah wave function collapse. Tetapi, algoritma wave function collapse datang dengan kelemahan yaitu waktu eksekusi yang lama. Melihat ini, terpikirkan cara untuk menggunakan divide and conquer pada algoritma wave function collapse untuk mengatasi kelemahan tersebut. Divide and conquer diimplementasikan dengan membagi map menjadi beberapa potongan bernama chunks yang akan dibangun satu per satu untuk menghasilkan map akhir. Perbandingan lalu dilakukan dengan menjalankan proses pembangunan map berulang kali dengan ukuran map dan jumlah chunks berbeda. Tujuh ukuran map serta empat tingkat penggunaan chunks digunakan. Hasil perbandingan menunjukan bahwa maps yang dibangun menggunakan chunks memiliki waktu eksekusi yang lebih rendah. Map dengan ukuran 32x32 berhasil dibangun 2.08 kali lebih cepat saat menggunakan 2x2 chunks dibandingkan tidak menggunakan chunks sama sekali. Perbedaan ini pun meningkat menjadi 2.86 kali saat ukuran map dinaikan menjadi 64x64. Hal ini menunjukan bahwa dampak divide and conquer menjadi lebih besar seiring dengan meningkatnya ukuran map. Dan, terlihat bahwa map yang menggunakan chunks memiliki skalabilitas yang lebih baik. Saat ukuran map dinaikan dari 16x16 ke 64x64, map yang tidak menggunakan chunks mengalami peningkatan waktu eksekusi sebesar 105.46 kali sedangkan map yang menggunakan 8x8 chunks mengalami peningkatan sebesar 30.63 kali. Dengan ini, dapat disimpulkan bahwa penggunaan divide and conquer memiliki dampak positif terhadap waktu eksekusi pembangunan map menggunakan algoritma wave function collapse.

Item Type:	Thesis (Bachelor Thesis)
Creators:	Abhinaya, Rajendra (00000060445)
Contributors:	Istiono, Wirawan
Keywords:	Divide and Conquer, Maps, Procedural Content Generation, Wave Function Collapse
Subjects:	000 Computer Science, Information and General Works
Divisions:	Faculty of Engineering & Informatics > Informatics
Date Deposited:	09 Sep 2025 11:05
URI:	https://kc.umn.ac.id/id/eprint/40365

Actions (login required)

View Item