Saya memiliki kotak jarahan yang ingin saya isi dengan item acak. Tapi saya ingin setiap item memiliki kesempatan berbeda untuk dipilih. Sebagai contoh:
- 5% peluang 10 emas
- 20% kemungkinan pedang
- 45% kemungkinan perisai
- 20% kemungkinan baju besi
- 10% kemungkinan ramuan
Bagaimana saya bisa membuatnya sehingga saya dapat memilih salah satu item di atas, di mana persentase tersebut adalah peluang masing-masing untuk mendapatkan hasil rampasan?
Jawaban:
Solusi Probabilitas Berkode Lunak
Solusi probabilitas hardcoded memiliki kelemahan yang Anda butuhkan untuk mengatur probabilitas dalam kode Anda. Anda tidak dapat menentukannya saat runtime. Ini juga sulit dipertahankan.
Berikut ini adalah versi dinamis dari algoritma yang sama.
Berikut adalah contoh implementasi di Jawa dalam bentuk kelas templat yang dapat Anda instantiate untuk objek apa pun yang digunakan gim Anda. Anda kemudian dapat menambahkan objek dengan metode
.addEntry(object, relativeWeight)
dan memilih salah satu entri yang Anda tambahkan sebelumnya.get()
Pemakaian:
Ini adalah kelas yang sama yang diimplementasikan dalam C # untuk proyek Unity, XNA atau MonoGame Anda:
Dan di sini ada satu dalam JavaScript :
Pro:
Kontra:
O(n)
kompleksitas runtime). Jadi, ketika Anda memiliki satu set barang yang sangat besar dan menggambar sangat sering, itu mungkin menjadi lambat. Optimalisasi sederhana adalah menempatkan item yang paling memungkinkan terlebih dahulu sehingga algoritma berakhir lebih awal dalam kebanyakan kasus. Optimasi yang lebih kompleks yang dapat Anda lakukan adalah memanfaatkan fakta bahwa array diurutkan dan melakukan pencarian membagi dua. Ini hanya butuhO(log n)
waktu.O(n)
runtime kasus terburuk)sumber
Catatan: Saya membuat perpustakaan C # untuk masalah ini
Solusi lain baik-baik saja jika Anda hanya memiliki sejumlah kecil item dan probabilitas Anda tidak pernah berubah. Namun, dengan banyak item atau perubahan probabilitas (mis. Menghapus item setelah memilihnya) , Anda akan menginginkan sesuatu yang lebih kuat.
Berikut adalah dua solusi paling umum (keduanya termasuk dalam perpustakaan di atas)
Metode Alias Walker
Solusi cerdas yang sangat cepat (
O(1)
!) Jika probabilitas Anda konstan. Intinya, algoritme ini membuat papan panah 2D ("tabel alias") dari probabilitas Anda dan melempar panah ke sana.Ada banyak artikel daring tentang cara kerjanya jika Anda ingin mempelajari lebih lanjut.
Satu-satunya masalah adalah jika probabilitas Anda berubah, Anda perlu membuat ulang tabel alias, yang lambat. Jadi, jika Anda perlu menghapus item setelah diambil, ini bukan solusi untuk Anda.
Solusi berbasis pohon
Solusi umum lainnya adalah membuat array di mana setiap item menyimpan jumlah probabilitasnya dan semua item sebelumnya. Kemudian cukup buat angka acak dari [0,1) dan lakukan pencarian biner untuk mengetahui nomor mana yang masuk dalam daftar.
Solusi ini sangat mudah untuk dikodekan / dipahami, tetapi membuat pilihan lebih lambat daripada Metode Alias Walker, dan masih tetap mengubah probabilitasnya
O(n)
. Kita bisa memperbaikinya dengan mengubah array menjadi pohon pencarian biner, di mana setiap node melacak jumlah probabilitas di semua item dalam subtree-nya. Kemudian ketika kita menghasilkan angka dari [0,1), kita bisa berjalan turun pohon untuk menemukan item yang diwakilinya.Ini memberi kami
O(log n)
untuk memilih item dan mengubah probabilitas! Ini membuatNextWithRemoval()
sangat cepat!Hasil
Berikut adalah beberapa tolok ukur cepat dari perpustakaan di atas, membandingkan dua pendekatan ini
Jadi seperti yang Anda lihat, untuk kasus khusus probabilitas statis (tidak berubah), metode Alias Walker sekitar 50-100% lebih cepat. Tetapi dalam kasus yang lebih dinamis, pohon itu beberapa kali lipat lebih cepat !
sumber
nlog(n)
) yang layak saat menyortir item berdasarkan berat.Solusi Roda Keberuntungan
Anda dapat menggunakan metode ini ketika probabilitas dalam kumpulan item Anda memiliki penyebut umum yang agak besar dan Anda harus sering menggunakannya.
Buat berbagai opsi. Tetapi masukkan setiap elemen ke dalamnya beberapa kali, dengan jumlah duplikat dari setiap elemen sebanding dengan peluangnya untuk muncul. Untuk contoh di atas, semua elemen memiliki probabilitas yang merupakan pengganda 5%, sehingga Anda dapat membuat array 20 elemen seperti ini:
Kemudian cukup pilih elemen acak dari daftar itu dengan menghasilkan satu bilangan bulat acak antara 0 dan panjang array - 1.
Kekurangan:
Keuntungan:
sumber
Epic Scepter of the Apocalypse
. Pendekatan dua tingkat seperti itu memanfaatkan keunggulan kedua pendekatan tersebut.[('gold', 1),('sword',4),...]
menjumlahkan semua bobot, dan kemudian menggulung angka acak dari 0 ke jumlah, kemudian iterate array dan menghitung di mana angka acak mendarat (yaitu areduce
). Berfungsi baik untuk array yang sering diperbarui, dan tidak ada memori utama.Solusi Probabilitas Hard-kode
Cara paling sederhana untuk menemukan item acak dari koleksi tertimbang adalah dengan menelusuri rantai pernyataan if-else, di mana setiap if-else meningkat mungkin, karena yang sebelumnya tidak mencapai.
Alasan kondisional sama dengan kesempatannya ditambah semua peluang kondisional sebelumnya adalah karena kondisional sebelumnya telah menghilangkan kemungkinan itu sebagai item tersebut. Jadi untuk kondisi perisai
else if(rand <= 70)
, 70 sama dengan peluang 45% dari perisai, ditambah 5% peluang emas dan 20% peluang pedang.Keuntungan:
Kekurangan:
sumber
Di C # Anda bisa menggunakan pemindaian Linq untuk menjalankan akumulator Anda untuk memeriksa terhadap nomor acak dalam kisaran 0 hingga 100.0f dan .First () untuk mendapatkan. Jadi seperti satu baris kode.
Jadi sesuatu seperti:
sum
adalah nol integer yang diinisialisasi dana
merupakan daftar prob / item struct / tuple / instance.rand
adalah nomor acak yang dihasilkan sebelumnya dalam kisaran.Ini hanya mengakumulasi jumlah di atas daftar rentang hingga melebihi angka acak yang dipilih sebelumnya, dan mengembalikan item atau null, di mana nol akan dikembalikan jika rentang nomor acak (mis. 100) kurang dari rentang bobot total karena kesalahan , dan nomor acak yang dipilih berada di luar rentang bobot total.
Namun, Anda akan melihat bahwa bobot dalam OP sangat cocok dengan distribusi normal (Bell Curve). Saya pikir secara umum Anda tidak akan menginginkan rentang tertentu, Anda akan cenderung menginginkan distribusi yang berangsur-angsur berkurang baik di sekitar kurva lonceng atau hanya pada kurva eksponensial yang menurun (misalnya). Dalam hal ini Anda bisa menggunakan rumus matematika untuk menghasilkan indeks ke dalam array item, diurutkan dalam urutan probabilitas pilihan. Contoh yang baik adalah CDF dalam distribusi normal
Juga contoh di sini .
Contoh lain adalah bahwa Anda dapat mengambil nilai acak dari 90 derajat hingga 180 derajat untuk mendapatkan kuadran kanan bawah dari sebuah lingkaran, mengambil komponen x menggunakan cos (r) dan menggunakannya untuk mengindeks ke daftar prioritas.
Dengan formula yang berbeda, Anda dapat memiliki pendekatan umum di mana Anda hanya memasukkan daftar prioritas panjang apa pun (misalnya N) dan memetakan hasil rumus (misalnya: cos (x) adalah 0 hingga 1) dengan perkalian (misalnya: Ncos (x) ) = 0 hingga N) untuk mendapatkan indeks.
sumber
Kemungkinan tidak perlu dikodekan dengan keras. Item dan ambang batas bisa bersama-sama dalam sebuah array.
Anda masih harus mengakumulasi ambang, tetapi Anda dapat melakukannya saat membuat file parameter alih-alih mengkodekannya.
sumber
random()
dalam loop?Saya melakukan fungsi ini: https://github.com/thewheelmaker/GDscript_Weighted_Random Now! dalam kasus Anda, Anda dapat menggunakannya seperti ini:
Ini hanya memberikan angka antara 0 hingga 4 tetapi Anda dapat meletakkannya di array di mana Anda mendapatkan item.
Atau dalam fungsi:
Ini kodenya. Saya membuatnya di GDscript, Anda bisa, tetapi bisa mengubah bahasa lain, juga memeriksa kesalahan logika:
Kerjanya seperti ini: on_normal_case ([50,50], 0) Ini memberi 0 atau 1, keduanya memiliki probabilitas yang sama.
on_normal_case ([50,50], 1) Ini memberi 1 atau 2, keduanya memiliki probabilitas yang sama.
on_normal_case ([20,80], 1) Ini memberi 1 atau 2, ia memiliki perubahan yang lebih besar untuk mendapatkan dua.
on_normal_case ([20,80,20,20,30], 1) Ini memberikan angka acak berkisar 1-5 dan angka yang lebih besar lebih mungkin daripada angka yang lebih kecil.
on_normal_case ([20,80,0,0,20,20,30,0,0,0,0,33], 45) Lemparan dadu ini antara angka 45,46,49,50,51,56 yang Anda lihat ketika ada adalah nol tidak pernah terjadi.
Jadi fungsinya mengembalikan hanya satu bilangan acak yang bergantung pada larik array dan jumlah transformm itu, dan int dalam array adalah bobot probabilitas yang mungkin terjadi, di mana bilangan itu terletak pada array, pluss transformm number.
sumber