Penerapan Algoritma Branch and Bound dalamPenentuan Rute Farming 600 Mora Tercepat pada

Game Genshin Impact Versi 1.5Nabil Nabighah 13519168

Program Studi Teknik InformatikaSekolah Teknik Elektro dan Informatika

Institut Teknologi Bandung, Jalan Ganesha 10 BandungE-mail : 13519168@std.stei.itb.ac.id

Abstrak—Perkembangan teknologi sangatlah pesat saat ini.Sudah banyak produk yang dihasilkan karena teknologi salahsatunya adalah permainan atau game. Game memiliki banyakjenisnya, salah satunya adalah game dengan jenis action RPG.Salah satu game yang memenuhi jenis tersebut adalah GameGenshin Impact. Pada game tersebut terdapat sebuah mekanikuntuk melawan musuh yang akan memberikan pemain sejumlahuang dalam bentuk in-game currency yang disebut Mora. Untukmengumpulkan mora tersebut diperlukan rute tercepat agarefisien. Dengan algoritma branch and bound dapat dicari rutetercepat tersebut.

Keywords—Genshin Impact; Branch and Bound; Rute

I. PENDAHULUAN

Perkembangan zaman telah mempengaruhi berbagaibidang di kehidupan. Salah satunya adalah bidang hiburan.Banyak sekali hiburan yang menggunakan teknologi,contohnya adalah permainan atau game. Game memilikibanyak jenisnya. Salah satu yang banyak penggemarnyaadalah game berjenis RPG (Role-Playing Game). Game jenisini adalah game dengan mekanik yaitu pemain akanmemainkan karakter di dalam game. Biasanya permainandengan jenis ini akan disertai dengan cerita-cerita naratif.

Gambar 1 Genshin Impact Ganyu

Sumber : https://www.facebook.com/Genshinimpact

Sampai saat ini, game muncul dalam berbagai macambentuk dan platform untuk memainkannya. Genshin Impactadalah salah satu game yang memiliki genre RPG open world.Open world yang berarti memiliki banyak cara untuk

menyelesaikan suatu objektif pada game tersebut. GenshinImpact dirilis tanggal 28 September 2020. Game ini termasukgame yang populer saat ini. Game ini termasuk gamemulti-platform artinya game ini dapat dimainkan di platformmanapun seperti Windows, Android, PlayStation 4, iOS,PlayStation 5, dan Nintendo Switch. Pada game ini pemaindapat melakukan banyak hal di dalamnya sepertimenyelesaikan quest, melawan mob, menyelesaikan dugeon,melawan boss, mendesain sebuah tempat, dan berpetualangmenjelajahi dunia tersebut.

Gambar 2 Battle Melawan Elite Mob

Sumber : Dokumen Penulis

Salah satu mekanik pada game ini adalah melawan mob.Mob adalah lawan yang dianggap sangat mudah untukdilawan. Biasanya mob memiliki darah yang lebih sedikit darilawan jenis lain. Ketika pemain berhasil menang melawanmob tersebut, pemain akan mendapatkan mora. Mora adalahmata uang pada game ini. Mora dapat digunakan untukberbagai macam hal seperti membeli senjata, item, makanan,menaikkan level karakter yang dimainkan oleh pemain,menaikkan skill yang dimiliki sebuah karakter, enhancesenjata, dan membuat item. Dari mekanik tersebut turunlahsebuah mekanik yang disebut farming. Farming adalahsebuah teknik yang dilakukan secara berulang-ulang untukmendapatkan suatu hal di dalam game seperti uang (Mora).Setelah berhasil melawan mob beberapa mob akan mendropmora sejumlah 600. Mob tersebut adalah elite mob dantersebar di beberapa wilayah pada game ini. Farming sangat

Makalah IF2211 Strategi Algoritma, Semester II Tahun 2019/2020

baik jika dilakukan secara efisien. Farming efisien haruslahmelihat beberapa faktor, salah satunya yang paling pentingadalah faktor waktu. Karena mob ini tersebar diberbagaiwilayah maka diperlukan rute tercepat agar dapat melawanmob ini dan mengumpulkan mora. Rute tercepat ini dapatdiperoleh dengan menggunakan algoritma branch and bound.Rute dimulai dari sebuah wilayah ke wilayah lainnya dengantepat hanya satu kali.

II. LANDASAN TEORI

A. Algoritma Branch and BoundAlgoritma branch and bound atau BnB adalah sebuah

desain dari algoritma yang digunakan untuk memecahkanpersoalan optimisasi. Persoalan optimisasi adalah persoalanyang meminimalkan atau memaksimalkan tanpa melanggarsuatu batasan (constraints) persoalan tersebut. Pada algoritmaBnB membutuhkan beberapa hal yaitu, nilai dari solusi terbaiksejauh ini dan sebuah jalan yang membuktikan untuk setiapsimpul pada pohon ruang status diperlukan suatu cara untukmenentukan batas (bound) nilai terbaik fungsi objektif padasetiap solusi yang mungkin, dengan menambahkan komponenpada solusi sementara yang direpresentasikan oleh simpul.Pada algoritma BnB, sama seperti algoritma backtrackingyaitu melakukan “pemangkasan” terhadap jalur yang dianggaptidak mengarah ke solusi. Kriteria pemangkasan secara umumyaitu :

1. Nilai simpul tidak lebih baik dari nilai terbaik sejauhini

2. Simpul dianggap tidak merepresentasikan solusi yang‘feasible’ karena terdapat batasan yang dilanggar

3. Solusi pada simpul tersebut hanya terdiri atas satutitik. Artinya tidak ada pilihan lain.

Langkah pengerjaan algoritma BnB pada makalah ini adalahsebagai berikut.

1. Hitung cost simpul akar2. Apabila simpul adalah solusi maka stop3. Masukkan anak-anak dari simpul tersebut kedalam

antrian prioritas (Priority Qeueu) dengan menghitungseluruh cost pada setiap simpul anak.

4. Ambil simpul dengan cost terkecil dari antrianprioritas kemudian cek apakah solusi atau bukan

5. Ulangi langkah 2

B. Reduced Cost Matrix

Reduced cost matrix atau matriks ongkos tereduksi adalahmatriks yang elemen-elemennya berisi ongkos (cost) atau nilaiyang tereduksi. Tereduksi dalam hal ini berarti setiap baris dankolom pada matriks ongkos tersebut memiliki paling sedikitsatu buah angka nol dan elemen-elemen pada matriks tersebutsemunya elemen non-negatif.

Pada makalah ini, algoritma Branch and Bound dipakaiuntuk menyelesaikan masalah travelling salesman problem(TSP). Perlu diketahui hal yang paling penting pada algoritmaBranch and Bound adalah penentuan cost, maka ada beberapacara menentukan cost algoritma Branch and Bound untukpersoalan TSP. Beberapa cara tersebut antara lainmenggunakan matriks ongkos tereduksi, dan bobot minimum

tur lengkap. Pada makalah ini penentuan cost akanmenggunakan metode matriks ongkos-tereduksi.

Gambar 3 Metode matriks ongkos tereduksi

Sumber :https://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2020-20

21/Algoritma-Branchand-Bound-2021-Bagian2.pdf

Misalkan A adalah matriks tereduksi untuk simpul R.Sedangkan S adalah anak dari simpul R sehingga sisi (R, S)pada pohon ruang status berkoresponden dengan sisi (i, j) padaperjalanan. Langkah-langkah menghitung matriksongkos-tereduksi adalah sebagai berikut.

1. Jika S bukan simpul daun maka2. Ubah semua nilai pada baris i dan kolom j menjadi ∞.3. Ubah A(j, 1) menjadi ∞.4. Reduksi kembali semua baris dan kolom pada

matriks A kecuali untuk elemen.5. Hitung nilai r dimana r adalah total semua pengurang

ketika mereduksi matriks.6. Hitung cost pada simpul tersebut

C. Travelling Salesman Problem (TSP)Persoalan travelling salesman problem atau TSP adalah

sebuah persoalan yang termasuk persoalan yang melibatkanproses optimasi. Persoalan ini melibatkan permasalahanmaksimum dan minimum. TSP adalah persoalan mengenaipenentuan sebuah rute yang minimum sedemikian sehinggatempat - tempat yang dilaluinya tepat hanya sekali kemudiankembali ke tempat asal keberangkatan.

III. PENERAPAN ALGORITMA DAN PENGUJIAN

A. Membuat Graf Tidak Berarah

Makalah IF2211 Strategi Algoritma, Semester II Tahun 2019/2020

Gambar 4 Sebagian Peta Game Genshin Impact

Sumber : Dokumen Penulis

Gambar 4 menunjukkan sebagian kecil dari peta padagame Genshin Impact versi 1.5. Pada gambar tersebut terdapatbanyak titik berwarna merah yang menandakan simpul -simpul yang akan digunakan untuk graf berarah. Titikberwarna biru menunjukkan bahwa rute dimulai dari titiktersebut. Dari gambar tersebut diperoleh graf berarah sepertiberikut

Gambar 5 Graf Tak Berarah Rute Farming

Sumber : Dokumen Penulis

Penomoran pada graf tak berarah menyatakan nomorsimpul - simpul pada gambar 4, simpul 1 menunjukkan simpulawal yang pada gambar 4 ditunjukkan dengan titik berwarna

biru. Graf tersebut tidak semua simpul terdapat sisi untuk kesetiap simpul lainnya karena penulis mempertimbangkanwaktu yang dibutuhkan terlalu besar sehingga simpul tersebutdapat dikatakan tidak bertetangga dengan simpul yang jauh.

B. Membuat Matriks Ongkos

Perhitungan ongkos dari simpul satu ke simpul lainnyadengan menggunakan waktu. Satuan waktu yang digunakanadalah satuan detik. Waktu diukur dari sejak karakter bergerakhingga karakter melakukan damage terhadap musuh pertamakali. Apabila waktu yang didapatkan terlalu lama atau lebihbesar dari 70 detik maka jarak simpul satu ke simpul lainnyaadalah tak hingga atau bisa dikatakan simpul satu ke simpullainnya tidak bertetangga. Dengan metode seperti ini,diperoleh matriks ongkos awal adalah sebagai berikut.

sehingga dapat diperoleh matriks ongkos reduksi untuk simpulawal atau simpul akar adalah sebagai berikut.

Dari matriks ongkos reduksi untuk simpul akar terebut,diperoleh ongkos untuk simpul akar sebesar 381. Dari matriks

Makalah IF2211 Strategi Algoritma, Semester II Tahun 2019/2020

ongkos tereduksi untuk simpul akar tersebut dapat diperolehpohon ruang status untuk awal yaitu sebagai berikut.

Gambar 6 Pohon Ruang Status Simpul Awal

Sumber : Dokumen Penulis

Perlu diketahui bahwa nomor pada gambar 6 bukanlahmenyatakan simpul tetapi menyatakan urutan langkah. X padagambar 6 menunjukkan index simpul jadi ketika X = 1 ituberarti simpul x+1 . Dari gambar 6, Terihat jelas bahwa costanak yang paling kecil adalah simpul ke 3. sehingga pastijawaban program harus terdapat jalur dari simpul 1 ke simpul3.

C. Design Algoritma Branch and Bound

Penulis mendesign algoritma branch and bound dengansebuah array simpul hidup dan sebuah array simpul ekspand.Array simpul hidup berisi seluruh anak-anak dari simpulekspand. Array simpul hidup diimplementasikan denganmenggunakan arrray PriorityQueue. Branch and Bound akanmenentukan cost terkecil dari simpul. Sebagai contoh kasusmenggunakan gambar 6, simpul akar memiliki cost 381kemudian simpul anaknya memiliki cost 441 dan 381.Algoritma branch and bound akan memiliki anak dengan cost381 dan memasukkannya kedalam array fungsi ekspand.Kemudian anak dengan cost 381 menghasilkan anak kembalidan menghitung cost anaknya begitu seterusnya hinggadiperoleh simpul solusi. Ketika sampai ke simpul solusisimpul-simpul dari akar hingga ke simpul solusi tersebutadalah jalur atau jawaban untuk algoritma branch and boundini.

D. Pembuatan Program

Persoalan rute farming ini memiliki banyak simpulsehingga memerlukan program untuk menghitung cost setiapsimpul dengan menggunakan matriks ongkos tereduksi.Penulis membuat program ini dalam bahasa Python. Simpul -simpul pada graf disimpan dalam sebuah class bernama classNode. Isi dari kelas node adalah atribut dan metode. Atributkelas node antara lain matrix, cost, dan array jalur. Atributmatriks berguna untuk menyimpan matriks tereduksi darisebuah simpul, atribut cost berguna untuk menyimpan costsimpul tersebut, begitu juga atribut array jalur untukmenyimpan jalur simpul dimulai dari akar hingga ke simpultersebut. Terdapat beberapa metode untuk menunjangalgoritma ini. Pada kelas Node terdapat metode reduceKolomdan reduceBaris keduanya memiliki fungsi yang sama yaitu

untuk mengubah baris dan kolom menjadi baris dan kolomyang tereduksi. Terdapat pula fungsi bnb yaitu fungsialgoritma bnb dan fungsi costSimpul untuk membuat matrikstereduksi dari simpul dan menghitung cost dari matrikstersebut.

Gambar 7 Kelas Node pada Program Python

Sumber : Dokumen Penulis

Gambar 8 Fungsi costSimpul

Sumber : Dokumen Penulis

Gambar 9 Fungsi Algoritma Branch and Bound

Sumber : Dokumen Penulis

Makalah IF2211 Strategi Algoritma, Semester II Tahun 2019/2020

Fungsi program bnb ini untuk mencari anak-anak padasimpul ekspand kemudian memasukkannya kedalam simpulhidup terurut secara membesar berdasarkan cost menggunakanarray Priority Queue.

Program akan menghitung terlebih dahulu cost pada simpulakar kemudian memasukkan simpul akar tersebut kedalamsimpul hidup.

Gambar 10 Program Mengatasi Simpul Akar

Sumber : Dokumen Penulis

Gambar 11 Program Driver Branch and Bound

Sumber : Dokumen Penulis

Program akan melakukan traversal secara terus menerushingga suatu saat ketika simpul hidup kosong atau ketikasimpul jawaban banyaknya sama dengan jumlah simpul padagraf. Apabila telah setelah traversal maka program akanmenampilkan jalurnya.

E. Pengujian Program

Cara kerja program :

1. Masukkan nama file txt yang berisi matriks ongkos yangtelah dibuat secara manual pada gambar 12 matriksmenggunakan spasi sebagai pembeda baris dan kolomdan menggunakan ongkos -1 sebagai penanda bahwajarak antara simpul tersebut ke simpul lainnya sangatjauh sehingga dapat dibilang infinity atau tak terhingga.

Gambar 12 Contoh matriks ongkos

Sumber : Dokumen Penulis

2. Program akan mulai melakukan traversal sesuai denganprogram python pada gambar 11.

3. Setelah selesai maka program akan menampilkan rutetercepat tersebut.

Gambar 13 Hasil Eksekusi Program

Sumber : Dokumen Penulis

Dari gambar 13 dapat dilihat bahwa algoritma yang telahdibuat memberikan hasil jalur rute tercepat yaitu jalur darisimpul 1 -> 3 -> 2 -> 4 -> 5-> 6 -> 7 -> 8 -> 9 -> 10 -> 12 ->11 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 20. Rutetersebut memberikan cost total sebanyak 436.

Program algoritma branch and bound yang telah dibuatdalam bahasa Python telah cukup mangkus dalam segikompleksitas waktu untuk simpul berukuran 20 simpuldaripada algoritma - algoritma lainnya seperti brute force. Halini karena pada algoritma branch and bound jumlah eksekusiyang dilakukan lebih sedikit dibandingkan algoritma bruteforce.

Program yang telah dibuat masih memiliki kelemahan,salah satunya adalah simpul yang ingin menjadi akar hanyalahsimpul nomor 1 sehingga simpul yang ingin menjadi akarperlu diletakkan pada index 0 di file txt. Apabila inginmengganti nomor simpul awal program tersebut perlu digantipada bagian simpul akar. Data pada program ini masihmemiliki kelemahan karena di game tersebut ada mekanismesprint yang berarti dapat menambah kecepatan lari dalambeberapa waktu dan gliding yaitu membuat karakter terbangmenggunakan sebuah sayap. sprint dan gliding memiliki batas

Makalah IF2211 Strategi Algoritma, Semester II Tahun 2019/2020

waktu yang berbeda-beda setiap pemain karena sprint dangliding memerlukan stamina yang setiap pemain berbeda-bedajumlah staminanya sesuai dengan level pemain sehingga datayang digunakan mungkin masih memiliki beberapa tidakcocokan dengan kenyataannya. Perlu diketahui juga bahwagame Genshin Impact adalah game yang selalu diperbaharuisetiap beberapa bulan sekali sehingga bisa jadi dimasa depanakan ada penambahan simpul - simpul untuk farming 600mora ini.

IV. KESIMPULAN

Algoritma branch and bound dapat mencari pencarian rutetercepat berserta costnya dengan menggunakan metodematriks ongkos tereduksi. Diperoleh rute tercepat untukmelakukan farming pada game Genshin Impact adalah sebagaiberikut.

Gambar 14 Rute Pada Map Genshin Impact Sesuai Hasilyang diperoleh

Secara keseluruhan algoritma branch and bound dapatmenghitung jarak tercepat untuk farming 600 mora. Tetapialgoritma ini mungkin saja bukan algoritma terbaik untukmenghitung persoalan optimasi karena mungkin ada algoritmalain yang lebih baik untuk menyelesaikannya.

VIDEO LINK AT YOUTUBE

Video mengenai demo masalah pada makalah ini dapatdilihat pada link berikut https://youtu.be/h0ZA6VJEeTQ

UCAPAN TERIMA KASIH

Penulis mengucapkan puji dan syukur kepada Allah Azzawa Jalla atas kehendaknya penulis dapat menyelesaikan karyatulis ini. Selain itu, penulis mengucapkan terima kasih kepadaBapak Rinaldi Munir dan seluruh dosen mata kuliah StrategiAlgoritma IF2211 Semester 2 2020/2021 yang telahmembimbing penulis untuk menyelesaikan karya tulis ini. Taklupa penulis mengucapkan terima kasih kepada teman - temanpenulis yang telah menyemangati penulis dalam penyusunankarya tulis ini.

REFERENSI

[1] Levitin, “Intriduction to the Design and Analysis of Algorithms”, 2011[2] https://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2020-2021/Algorit

ma-Branchand-Bound-2021-Bagian2.pdf[3] https://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2020-2021/Algorit

ma-Branch-and-Bound-2021-Bagian1.pdf[4] https://genshin-impact-map.appsample.com/#/[5] https://genshin-impact.fandom.com/

PERNYATAANDengan ini saya menyatakan bahwa makalah yang saya tulisini adalah tulisan saya sendiri, bukan saduran, atau terjemahandari makalah orang lain, dan bukan plagiasi.

Bandung, 11 Mei 2021

Nabil Nabighah 13519168

Makalah IF2211 Strategi Algoritma, Semester II Tahun 2019/2020