Saya mencoba membuat semacam permainan di mana saya memiliki kotak 20x20 dan saya menampilkan pemain (P), target (T) dan tiga musuh (X). Semua ini memiliki koordinat X dan Y yang ditugaskan menggunakan rand()
. Masalahnya adalah jika saya mencoba untuk mendapatkan lebih banyak poin dalam permainan (isi ulang untuk energi dll) mereka tumpang tindih dengan satu atau lebih poin lainnya karena kisarannya kecil (1 hingga 20 inklusif).
Ini adalah variabel saya dan bagaimana saya menetapkan nilai-nilai kepada mereka: ( COORD
adalah struct
dengan hanya X dan Y)
const int gridSize = 20;
COORD player;
COORD target;
COORD enemy1;
COORD enemy2;
COORD enemy3;
//generate player
srand ( time ( NULL ) );
spawn(&player);
//generate target
spawn(&target);
//generate enemies
spawn(&enemy1);
spawn(&enemy2);
spawn(&enemy3);
void spawn(COORD *point)
{
//allot X and Y coordinate to a point
point->X = randNum();
point->Y = randNum();
}
int randNum()
{
//generate a random number between 1 and gridSize
return (rand() % gridSize) + 1;
}
Saya ingin menambahkan lebih banyak hal ke permainan tetapi kemungkinan tumpang tindih meningkat ketika saya melakukan itu. Apakah ada cara untuk memperbaikinya?
rand()
adalah RNG yang sangat disayangkan, dan lagi pula dengan kisaran sekecil itu, Anda tidak hanya harus mengharapkan tabrakan, mereka hampir dijamin.rand()
adalah RNG yang buruk, mungkin cocok untuk permainan pemain tunggal, dan kualitas RNG bukan masalah di sini.rand()
sepertinya tidak relevan di sini. Tidak ada kriptografi yang terlibat, dan RNG mana pun akan sangat mungkin memberikan tabrakan dalam peta sekecil itu.Jawaban:
Sementara pengguna yang mengeluhkan
rand()
dan merekomendasikan RNG yang lebih baik benar tentang kualitas angka acak, mereka juga kehilangan gambaran yang lebih besar. Duplikat dalam aliran angka acak tidak dapat dihindari, mereka adalah fakta kehidupan. Ini adalah pelajaran dari masalah ulang tahun .Pada kisi 20 * 20 = 400 kemungkinan posisi spawn, duplikasi titik spawn diharapkan (probabilitas 50%) bahkan ketika pemijahan hanya 24 entitas. Dengan 50 entitas (masih hanya 12,5% dari seluruh grid), probabilitas duplikat lebih dari 95%. Anda harus berurusan dengan tabrakan.
Terkadang Anda bisa menggambar semua sampel sekaligus, lalu Anda bisa menggunakan algoritma acak untuk menggambar
n
item yang dijamin berbeda. Anda hanya perlu membuat daftar semua kemungkinan. Jika daftar lengkap kemungkinan terlalu besar untuk disimpan, Anda dapat menghasilkan posisi spawn satu per satu seperti yang Anda lakukan sekarang (hanya dengan RNG yang lebih baik) dan hanya menghasilkan ulang ketika terjadi tabrakan. Meskipun memiliki beberapa tabrakan mungkin terjadi, banyak tabrakan berturut-turut secara eksponensial tidak mungkin bahkan jika sebagian besar grid dihuni.sumber
Jika Anda selalu ingin menghindari memainkan entitas baru di lokasi yang telah dialokasikan untuk sesuatu yang lain, Anda dapat sedikit mengubah proses Anda. Ini akan menjamin lokasi yang unik, tetapi membutuhkan overhead yang lebih sedikit. Berikut langkah-langkahnya:
Selama Anda menghapus lokasi dari set yang Anda pilih, seharusnya tidak ada kemungkinan entitas kedua menerima lokasi yang sama (kecuali Anda memilih lokasi dari lebih dari satu utas sekaligus).
Analog dunia nyata dengan ini akan menggambar kartu dari setumpuk kartu. Saat ini, Anda menyeret geladak, menggambar kartu dan menandainya, meletakkan kartu yang ditarik kembali ke geladak, menyeret kembali dan menggambar lagi. Pendekatan di atas tidak memasukkan kartu kembali ke dalam geladak.
sumber
Berkaitan dengan
rand() % n
kurang idealMelakukan
rand() % n
memiliki distribusi yang tidak seragam. Anda akan mendapatkan jumlah nilai tertentu yang tidak proporsional karena jumlah nilai bukan kelipatan 20Berikutnya,
rand()
biasanya merupakan generator kongruensial linier (ada banyak yang lain , hanya ini yang paling mungkin diterapkan - dan dengan parameter yang kurang ideal (ada banyak cara untuk memilih parameter)). Masalah terbesar dengan ini adalah seringnya bit rendah di dalamnya (yang Anda dapatkan dengan% 20
ekspresi tipe) tidak acak. Saya ingat saturand()
dari tahun lalu di mana bit terendah berganti dari1
ke0
dengan setiap panggilan kerand()
- itu tidak terlalu acak.Dari halaman manual rand (3):
Ini mungkin sekarang diturunkan ke sejarah, tetapi sangat mungkin bahwa Anda masih memiliki implementasi rand () yang buruk yang tersembunyi di suatu tempat di stack. Dalam hal ini, masih cukup berlaku.
Yang harus dilakukan adalah benar-benar menggunakan pustaka angka acak yang baik (yang memberikan angka acak yang baik) dan kemudian meminta angka acak dalam rentang yang Anda inginkan.
Contoh bit kode acak yang bagus (mulai pukul 13:00 di video yang ditautkan)
Bandingkan ini dengan:
Jalankan kedua program ini dan bandingkan seberapa sering angka-angka tertentu muncul (atau tidak muncul) dalam output itu.
Video terkait: rand () dianggap berbahaya
Beberapa aspek historis rand () yang menyebabkan bug di Nethack yang harus diperhatikan dan dipertimbangkan dalam implementasi sendiri:
Masalah Nethack RNG
Walaupun hal di atas berasal dari tahun 2003, hal itu harus tetap diingat karena mungkin tidak semua sistem yang menjalankan game yang Anda tuju akan menjadi sistem Linux terkini dengan fungsi rand () yang bagus.
Jika Anda hanya melakukan ini untuk diri sendiri, Anda dapat menguji seberapa baik generator nomor acak Anda dengan menulis beberapa kode dan menguji output dengan ent .
Pada sifat-sifat angka acak
Ada interpretasi lain 'acak' yang tidak sepenuhnya acak. Dalam aliran data acak, sangat mungkin untuk mendapatkan nomor yang sama dua kali. Jika Anda melempar koin (acak), sangat mungkin untuk mendapatkan dua kepala berturut-turut. Atau melempar dadu dua kali dan mendapatkan nomor yang sama dua kali berturut-turut. Atau memutar roda roulette dan mendapatkan nomor yang sama dua kali di sana.
Distribusi angka
Saat memainkan daftar lagu, orang berharap 'acak' berarti bahwa lagu atau artis yang sama tidak akan diputar untuk kedua kalinya berturut-turut. Memiliki daftar putar bermain The Beatles dua kali berturut-turut dianggap 'tidak acak' (meskipun adalah acak). Persepsi bahwa untuk daftar putar empat lagu diputar total delapan kali:
lebih 'acak' dari:
Lebih lanjut tentang ini untuk 'pengacakan' lagu: Bagaimana cara mengacak lagu?
Pada nilai yang diulang
Jika Anda tidak ingin mengulangi nilai, ada pendekatan berbeda yang harus dipertimbangkan. Hasilkan semua nilai yang mungkin, dan kocok.
Jika Anda menelepon
rand()
(atau generator nomor acak lainnya), Anda memanggilnya dengan pengganti. Anda selalu bisa mendapatkan nomor yang sama dua kali. Satu opsi adalah membuang nilai berulang-ulang sampai Anda memilih satu yang memenuhi persyaratan Anda. Saya akan menunjukkan bahwa ini memiliki runtime non-determistic dan ada kemungkinan bahwa Anda dapat menemukan diri Anda dalam situasi di mana ada infinite loop kecuali Anda mulai melakukan penelusuran balik yang lebih kompleks.Daftar dan Pilih
Pilihan lain adalah membuat daftar semua status yang mungkin valid dan kemudian memilih elemen acak dari daftar itu. Temukan semua tempat kosong (yang memenuhi beberapa aturan) di ruangan dan kemudian pilih satu yang acak dari daftar itu. Dan kemudian lakukan lagi dan lagi sampai selesai.
Acak
Pendekatan lain adalah mengocok seolah-olah setumpuk kartu. Mulailah dengan semua tempat kosong di ruangan itu dan kemudian mulai menugaskan mereka dengan membagikan tempat kosong, satu per satu, untuk setiap aturan / proses meminta tempat kosong. Anda selesai ketika Anda kehabisan kartu atau hal-hal berhenti meminta mereka.
sumber
Next, rand() is typically a linear congruential generator
Ini tidak benar pada banyak platform sekarang. Dari halaman manual rand (3) dari linux: "Versi rand () dan srand () di Linux C Library menggunakan generator nomor acak yang sama seperti acak (3) dan srandom (3), sehingga bit urutan rendah harus acak seperti bit orde tinggi. " Juga, seperti yang ditunjukkan @delnan, kualitas PRNG bukanlah masalah sebenarnya di sini.RAND_MAX
32767 perbedaannya adalah 1638 cara yang mungkin untuk mendapatkan beberapa angka vs 1639 untuk orang lain. Tampaknya tidak membuat banyak perbedaan praktis untuk OP.Solusi paling sederhana untuk masalah ini telah dikutip dalam jawaban sebelumnya: itu adalah membuat daftar nilai acak bersama setiap 400 sel Anda, dan kemudian, untuk mengurutkan daftar acak ini. Daftar sel Anda akan diurutkan sebagai daftar acak, dan dengan cara ini, akan diacak.
Metode ini memiliki keuntungan untuk benar-benar menghindari tumpang tindih sel yang dipilih secara acak.
Kerugiannya adalah Anda harus menghitung nilai acak pada daftar terpisah untuk masing - masing sel Anda. Jadi, Anda lebih suka tidak melakukannya saat gim telah dimulai.
Berikut ini adalah contoh bagaimana Anda dapat melakukannya:
Hasil:
Ubah saja NUMBER_OF_SPAWNS untuk mendapatkan lebih atau kurang sel acak, ini tidak akan mengubah waktu perhitungan yang diperlukan untuk tugas tersebut.
sumber