Dalam pengembangan game, Anda sering kali perlu mengandalkan keacakan: Unity memiliki Random-nya sendiri untuk ini, dan System.Random juga ada di sampingnya. Dahulu kala, dalam sebuah proyek, saya mendapat kesan bahwa keduanya mungkin bekerja secara berbeda (meskipun seharusnya memiliki distribusi yang seragam).
Kami tidak membahas detailnya saat itu—sudah cukup bahwa beralih ke System.Random menyelesaikan semua masalah. Sekarang kami memutuskan untuk meneliti lebih dekat dan melakukan studi kecil: seberapa "bias" atau terprediksinya RNG, dan mana yang harus dipilih. Selain itu, saya telah mendengar pendapat yang saling bertentangan tentang "kewajaran" mereka lebih dari sekali—mari kita coba cari tahu bagaimana hasil aktual dibandingkan dengan klaimnya.
Pengenalan singkat tentang RNG atau apakah itu benar-benar RNG?
Jika Anda sudah familier dengan generator angka acak, Anda dapat melompat ke bagian "Pengujian".
Bilangan acak (RN) adalah deret bilangan yang dihasilkan oleh suatu proses acak (chaotic), suatu sumber entropi. Artinya, deret ini adalah deret yang elemen-elemennya tidak saling terkait oleh hukum matematika apa pun—tidak memiliki hubungan sebab-akibat.
Apa yang menciptakan generator angka acak (RNG) disebut generator angka acak (RNG). Meskipun tampak sederhana, penerapan teori dalam praktik menunjukkan bahwa penerapan algoritma perangkat lunak untuk menghasilkan deret tersebut tidaklah semudah itu.
Alasannya terletak pada ketiadaan keacakan ini dalam elektronik konsumen modern. Tanpanya, angka acak berhenti menjadi acak, dan pembangkitnya berubah menjadi fungsi sederhana dari input yang telah ditentukan sebelumnya. Bagi sejumlah profesi TI (misalnya, kriptografi), ini merupakan masalah serius, tetapi bagi yang lain, ada solusi yang sepenuhnya dapat diterima.
Kita perlu menulis algoritma yang mengembalikan angka-angka yang tidak benar-benar acak, tetapi sedekat mungkin dengannya—yang disebut angka pseudo-acak (PRNG). Algoritma dalam kasus ini disebut generator angka pseudo-acak (PRNG).
Ada beberapa pilihan untuk membuat PRNG, tetapi berikut ini akan relevan untuk semuanya:
- Perlu pra-inisialisasi.
PRNG tidak memiliki sumber entropi, sehingga status awal harus ditentukan sebelum digunakan. Status awal ini ditentukan sebagai angka (atau vektor) dan disebut seed (seed acak). Penghitung siklus prosesor atau padanan numerik dari waktu sistem sering digunakan sebagai seed.
- Reproduksibilitas sekuens.
PRNG sepenuhnya deterministik, sehingga benih yang ditentukan selama inisialisasi secara unik menentukan seluruh rangkaian angka di masa mendatang. Ini berarti bahwa satu PRNG yang diinisialisasi dengan benih yang sama (pada waktu yang berbeda, dalam program yang berbeda, pada perangkat yang berbeda) akan menghasilkan rangkaian yang sama.
Anda juga perlu mengetahui distribusi probabilitas yang mencirikan PRNG—angka apa yang akan dihasilkannya dan dengan probabilitas berapa. Umumnya, distribusi ini berupa distribusi normal atau distribusi seragam.
Distribusi normal (kiri) dan distribusi seragam (kanan)
Misalkan kita memiliki dadu 24 sisi yang cukup besar. Jika kita melemparnya, peluang munculnya angka 1 adalah 1/24 (sama seperti peluang munculnya angka lainnya). Jika kita melempar dadu berkali-kali dan mencatat hasilnya, kita akan melihat bahwa semua dadu 24 sisi muncul dengan frekuensi yang kurang lebih sama. Pada dasarnya, dadu ini dapat dianggap sebagai generator bilangan acak terdistribusi seragam.
Bagaimana jika Anda melempar 10 dadu sekaligus dan menghitung skor totalnya? Apakah skornya akan tetap sama? Tidak. Umumnya, skornya akan mendekati 125 poin, yaitu nilai rata-rata. Dengan demikian, Anda dapat memperkirakan hasil di masa mendatang bahkan sebelum Anda melempar dadu.
Alasannya adalah karena terdapat jumlah kombinasi terbanyak untuk mencapai skor rata-rata. Semakin jauh dari rata-rata, semakin sedikit kombinasi yang ada—dan, akibatnya, semakin rendah probabilitas lemparan dadu. Jika data ini divisualisasikan, bentuknya akan menyerupai bentuk lonceng. Oleh karena itu, dengan sedikit modifikasi, sistem 10 dadu dapat disebut sebagai RNG yang terdistribusi normal.
Contoh lain, kali ini di pesawat, adalah menembak sasaran. Penembak adalah generator angka acak (RNG), yang menghasilkan sepasang angka (x, y), yang ditampilkan pada grafik.
Anda pasti setuju bahwa varian kiri lebih mendekati kehidupan nyata—ini adalah generator bilangan acak berdistribusi normal. Namun, jika Anda perlu menyebarkan bintang di langit yang gelap, varian kanan, yang diperoleh menggunakan generator bilangan acak berdistribusi seragam, akan lebih sesuai. Singkatnya, pilihlah generator berdasarkan tugas yang sedang dikerjakan.
Sekarang mari kita bahas entropi deret bilangan acak. Misalnya, ada deret yang dimulai seperti ini:
89, 93, 33, 32, 82, 21, 4, 42, 11, 8, 60, 95, 53, 30, 42, 19, 34, 35, 62, 23, 44, 38, 74, 36, 52, 18, 58, 79, 65, 45, 99, 90, 82, 20, 41, 13, 88, 76, 82, 24, 5, 54, 72, 19, 80, 2, 74, 36, 71, 9, …
Seberapa acakkah angka-angka ini sekilas? Mari kita mulai dengan memeriksa distribusinya.
Tampaknya hampir seragam, tetapi jika Anda membaca urutan dua angka dan menafsirkannya sebagai koordinat pada bidang, Anda mendapatkan ini:
Pola menjadi terlihat jelas. Dan karena data dalam urutan tersebut diurutkan dengan cara tertentu (yaitu, memiliki entropi rendah), hal ini dapat menghasilkan "bias" yang sama. Setidaknya, PRNG semacam itu kurang cocok untuk menghasilkan koordinat pada bidang.
Urutan lainnya:
42, 72, 17, 0, 30, 0, 15, 9, 47, 19, 35, 86, 40, 54, 97, 42, 69, 19, 20, 88, 4, 3, 67, 27, 42, 56, 17, 14, 20, 40, 80, 97, 1, 31, 69, 13, 88, 89, 76, 9, 4, 85, 17, 88, 70, 10, 42, 98, 96, 53, …
Tampaknya semuanya baik-baik saja di sini, bahkan di permukaan yang datar:
Mari kita lihat volume (baca tiga angka):
Dan lagi, pola. Visualisasi dalam empat dimensi sudah tidak mungkin lagi. Namun, pola bisa ada di dimensi ini dan di dimensi yang lebih tinggi.
Dalam kriptografi, di mana persyaratan paling ketat diberlakukan pada PRNG, situasi seperti itu sama sekali tidak dapat diterima. Oleh karena itu, algoritma khusus telah dikembangkan untuk mengevaluasi kualitasnya, yang tidak akan kita bahas di sini. Topik ini sangat luas dan membutuhkan artikel terpisah.
Pengujian
Jika kita tidak tahu pasti, bagaimana kita bisa mengatasinya? Haruskah kita menyeberang jalan jika kita tidak tahu lampu lalu lintas mana yang memperbolehkannya? Konsekuensinya bisa beragam.
Hal yang sama berlaku untuk keacakan yang terkenal di Unity. Memang bagus jika dokumentasi menyediakan detail yang diperlukan, tetapi insiden yang disebutkan di awal artikel muncul justru karena kurangnya spesifisitas yang diinginkan.
Dan tanpa mengetahui cara kerja alat tersebut, Anda tidak dapat menggunakannya dengan benar. Jadi, inilah saatnya untuk mengujinya dan melakukan eksperimen untuk memastikannya, setidaknya terkait distribusinya.
Solusinya sederhana dan efektif: kumpulkan statistik, dapatkan data objektif, dan lihat hasilnya.
Subjek penelitian
Ada beberapa cara untuk menghasilkan angka acak di Unity—kami menguji lima cara.
- System.Random.Next(). Menghasilkan bilangan bulat dalam rentang nilai tertentu.
- System.Random.NextDouble(). Menghasilkan angka presisi ganda dalam rentang [0; 1].
- UnityEngine.Random.Range(). Menghasilkan angka presisi tunggal (float) dalam rentang nilai tertentu.
- UnityEngine.Random.value. Menghasilkan angka presisi tunggal (float) dalam rentang [0; 1].
- Unity.Mathematics.Random.NextFloat(). Bagian dari pustaka Unity.Mathematics yang baru. Menghasilkan angka float presisi tunggal dalam rentang tertentu.
Hampir di semua bagian dokumentasi, distribusi seragam ditetapkan, kecuali UnityEngine.Random.value (di mana distribusinya tidak ditetapkan, tetapi dengan analogi dengan UnityEngine.Random.Range(), distribusi seragam juga diharapkan) dan Unity.Mathematics.Random.NextFloat() (yang didasarkan pada algoritma xorshift, yang berarti bahwa distribusi seragam harus diharapkan lagi).
Secara default, hasil yang diharapkan adalah hasil yang ditetapkan dalam dokumentasi.
Metodologi
Kami menulis aplikasi kecil yang menghasilkan rangkaian angka acak menggunakan setiap metode yang disajikan dan menyimpan hasilnya untuk diproses lebih lanjut.
Panjang setiap urutan adalah 100.000 angka.
Rentang nilai angka acak adalah [0, 100).
Data dikumpulkan dari beberapa platform target:
- Windows
— Unity v2018.3.14f1, Mode Editor, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, Mode Editor, Mono, .NET Standard 2.0
— Unity v5.6.4p4, Mode Editor, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, versi perangkat, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, pembuatan perangkat, il2cpp, .NET Standard 2.0
Implementasi
Kami memiliki beberapa cara berbeda untuk menghasilkan angka acak. Untuk masing-masing cara, kami akan menulis kelas pembungkus terpisah yang akan menyediakan:
- Kemungkinan untuk menentukan rentang nilai [min/maks]. Akan diatur melalui konstruktor.
- Metode yang mengembalikan angka. Kita akan memilih float sebagai tipe datanya karena lebih umum.
- Nama metode pembangkitan untuk pelabelan hasil. Demi kenyamanan, kami akan mengembalikan nama kelas lengkap + nama metode yang digunakan untuk menghasilkan SC sebagai nilai.
Pertama, mari kita nyatakan abstraksi yang akan direpresentasikan oleh antarmuka IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementasi System.Random.Next()
Metode ini memungkinkan Anda menentukan rentang nilai, tetapi mengembalikan bilangan bulat, sementara bilangan float diperlukan. Anda cukup menginterpretasikan bilangan bulat sebagai float, atau Anda dapat memperluas rentang nilai beberapa kali lipat, mengompensasinya setiap kali frekuensi dibangkitkan. Ini akan menghasilkan sesuatu seperti titik tetap dengan tingkat presisi tertentu. Kami akan menggunakan opsi ini karena lebih mendekati nilai float yang sebenarnya.
using System;
namespace RandomDistribution
{
public class SystemIntegerRandomGenerator : IRandomGenerator
{
private const int DefaultFactor = 100000;
private readonly Random _generator = new Random();
private readonly int _min;
private readonly int _max;
private readonly int _factor;
public string Name => "System.Random.Next()";
public SystemIntegerRandomGenerator(float min, float max, int factor = DefaultFactor)
{
_min = (int)min * factor;
_max = (int)max * factor;
_factor = factor;
}
public float Generate() => (float)_generator.Next(_min, _max) / _factor;
}
}Implementasi System.Random.NextDouble()
Di sini, rentang nilai tetapnya adalah [0; 1]. Untuk memproyeksikannya ke nilai yang ditentukan dalam konstruktor, kita menggunakan aritmatika sederhana: X * (maks - min) + min.
using System;
namespace RandomDistribution
{
public class SystemDoubleRandomGenerator : IRandomGenerator
{
private readonly Random _generator = new Random();
private readonly double _factor;
private readonly float _min;
public string Name => "System.Random.NextDouble()";
public SystemDoubleRandomGenerator(float min, float max)
{
_factor = max - min;
_min = min;
}
public float Generate() => (float)(_generator.NextDouble() * _factor) + _min;
}
}Implementasi UnityEngine.Random.Range()
Metode dari kelas UnityEngine.Random statis ini memungkinkan Anda menentukan rentang nilai dan mengembalikan angka acak bertipe float. Tidak diperlukan konversi tambahan.
using UnityEngine;
namespace RandomDistribution
{
public class UnityRandomRangeGenerator : IRandomGenerator
{
private readonly float _min;
private readonly float _max;
public string Name => "UnityEngine.Random.Range()";
public UnityRandomRangeGenerator(float min, float max)
{
_min = min;
_max = max;
}
public float Generate() => Random.Range(_min, _max);
}
}Implementasi UnityEngine.Random.value
Properti nilai dari kelas statis UnityEngine.Random mengembalikan bilangan acak tipe float dari rentang nilai tetap [0; 1]. Kita memproyeksikannya ke rentang yang diberikan dengan cara yang sama seperti saat mengimplementasikan System.Random.NextDouble().
using UnityEngine;
namespace RandomDistribution
{
public class UnityRandomValueGenerator : IRandomGenerator
{
private readonly float _factor;
private readonly float _min;
public string Name => "UnityEngine.Random.value";
public UnityRandomValueGenerator(float min, float max)
{
_factor = max - min;
_min = min;
}
public float Generate() => (float)(Random.value * _factor) + _min;
}
}Implementasi Unity.Mathematics.Random.NextFloat()
Metode NextFloat() dari kelas Unity.Mathematics.Random mengembalikan bilangan acak float dan memungkinkan Anda menentukan rentang nilai. Satu-satunya peringatan adalah bahwa setiap instance Unity.Mathematics.Random harus diinisialisasi dengan seed—ini mencegah pembentukan urutan duplikat.
using Unity.Mathematics;
namespace RandomDistribution
{
public class UnityMathematicsRandomValueGenerator : IRandomGenerator
{
private Random _generator;
private readonly float _min;
private readonly float _max;
public string Name => "Unity.Mathematics.Random.NextFloat()";
public UnityMathematicsRandomValueGenerator(float min, float max)
{
_min = min;
_max = max;
_generator = new Random();
_generator.InitState(unchecked((uint)System.DateTime.Now.Ticks));
}
public float Generate() => _generator.NextFloat(_min, _max);
}
}Implementasi MainController
Beberapa implementasi IRandomGenerator sudah siap. Selanjutnya, kita perlu menghasilkan sekuens dan menyimpan dataset yang dihasilkan untuk diproses. Untuk melakukannya, kita akan membuat sebuah scene di Unity dan sebuah skrip MainController kecil yang akan melakukan semua pekerjaan yang diperlukan dan menangani interaksi UI.
Kami akan menentukan ukuran kumpulan data dan rentang nilai frekuensi, dan juga membuat metode yang mengembalikan serangkaian generator yang dikonfigurasi dan siap digunakan.
namespace RandomDistribution
{
public class MainController : MonoBehaviour
{
private const int DefaultDatasetSize = 100000;
public float MinValue = 0f;
public float MaxValue = 100f;
...
private IRandomGenerator[] CreateRandomGenerators()
{
return new IRandomGenerator[]
{
new SystemIntegerRandomGenerator(MinValue, MaxValue),
new SystemDoubleRandomGenerator(MinValue, MaxValue),
new UnityRandomRangeGenerator(MinValue, MaxValue),
new UnityRandomValueGenerator(MinValue, MaxValue),
new UnityMathematicsRandomValueGenerator(MinValue, MaxValue)
};
}
...
}
}Sekarang kita akan membuat set data. Dalam hal ini, pembuatan data akan digabungkan dengan penulisan hasilnya ke aliran teks (dalam format CSV). Setiap IRandomGenerator akan memiliki kolomnya sendiri, dan baris pertama berisi Nama generator.
namespace RandomDistribution
{
public class MainController : MonoBehaviour
{
...
private void GenerateCsvDataSet(TextWriter writer, int dataSetSize, params IRandomGenerator[] generators)
{
const char separator = ',';
int lastIdx = generators.Length - 1;
// write header
for (int j = 0; j <= lastIdx; j++)
{
writer.Write(generators[j].Name);
if (j != lastIdx)
writer.Write(separator);
}
writer.WriteLine();
// write data
for (int i = 0; i <= dataSetSize; i++)
{
for (int j = 0; j <= lastIdx; j++)
{
writer.Write(generators[j].Generate());
if (j != lastIdx)
writer.Write(separator);
}
if (i != dataSetSize)
writer.WriteLine();
}
}
...
}
}Yang perlu dilakukan selanjutnya adalah memanggil metode GenerateCsvDataSet dan menyimpan hasilnya ke dalam file, atau langsung mentransfer data melalui jaringan dari perangkat akhir ke perangkat penerima. server.
namespace RandomDistribution
{
public class MainController : MonoBehaviour
{
...
public void GenerateCsvDataSet(string path, int dataSetSize, params IRandomGenerator[] generators)
{
using (var writer = File.CreateText(path))
{
GenerateCsvDataSet(writer, dataSetSize, generators);
}
}
public string GenerateCsvDataSet(int dataSetSize, params IRandomGenerator[] generators)
{
using (StringWriter writer = new StringWriter(CultureInfo.InvariantCulture))
{
GenerateCsvDataSet(writer, dataSetSize, generators);
return writer.ToString();
}
}
...
}
}Sumber proyek terletak di .
Temuan
Tidak ada keajaiban. Kami mendapatkan apa yang kami harapkan—distribusi yang merata di semua kasus, tanpa ada tanda-tanda konspirasi. Saya tidak melihat perlunya melampirkan diagram platform terpisah—semuanya menunjukkan hasil yang kurang lebih sama.
Realitanya adalah ini:
Visualisasi urutan pada bidang dari kelima metode pembangkitan:
Dan visualisasi 3D. Saya hanya akan meninggalkan hasil System.Random.Next() untuk menghindari pembuatan banyak konten yang identik.
Kisah yang diceritakan di pendahuluan tentang distribusi normal UnityEngine.Random tidak terulang: entah memang sudah cacat sejak awal, atau ada sesuatu di mesinnya yang telah berubah sejak saat itu. Namun sekarang kami yakin.
Sumber: www.habr.com
