U razvoju igara često je potrebno nešto vezati uz slučajnost: u Unityju za to postoji vlastiti Random, dok uz njega postoji i System.Random. Davno, na jednom od projekata, stekao se dojam da oba mogu raditi drugačije (iako bi trebala imati ravnomjerno raspoređenje).
Tada se u detalje nismo zatezali — dovoljno je bilo to što je prijelaz na System.Random ispravio sve probleme. Sada smo odlučili dublje se pozabaviti temom i provesti malo istraživanje: koliko su 'pristrani' ili predvidljivi generatori slučajnih brojeva, i koji odabrati. Što više, nisam jednom čuo oprečne stavove o njihovoj 'poštenosti' — pokušat ćemo shvatiti koliko se stvarni rezultati odnose na ono što je deklarirano.
Kratki uvod ili Što su zapravo generatori slučajnih brojeva
Ako ste već upoznati s generatorima slučajnih brojeva, možete odmah preći na odjeljak 'Testiranje'.
Slučajni brojevi (SB) — to je niz brojeva generiran nekim slučajnim (haotičkim) procesom, izvorom entropije. Drugim riječima, to je niz čiji su elementi međusobno nepovezani nekim matematičkim zakonom — nemaju uzročno-posljedičnu povezanost.
Ono što stvara SB zove se generator slučajnih brojeva (GSB). Činilo bi se da je sve jednostavno, ali kada se s teorije pređe na praksu, zapravo nije lako implementirati programski algoritam za generiranje takvog niza.
Razlog leži u nedostatku te haotičnosti u modernoj potrošačkoj elektronici. Bez nje slučajni brojevi prestaju biti slučajni, a njihov generator postaje obična funkcija s unaprijed definiranim argumentima. Za cijeli niz specijalnosti u IT sektoru to je ozbiljan problem (npr. za kriptografiju), dok za ostale postoji sasvim prihvatljivo rješenje.
Trebate napisati algoritam koji bi vraćao, iako ne istinski slučajne brojeve, ali što bliže njima — takozvane pseudo-slučajne brojeve (PSSB). U tom slučaju algoritam se naziva generatorom pseudo-slučajnih brojeva (GPSB).
Postoji nekoliko opcija za stvaranje GPSB, ali za sve će biti aktualno sljedeće:
- Potrebna prethodna inicijalizacija.
GPRS je lišen izvora entropije, stoga mu je prije korištenja potrebno odrediti početno stanje. To se određuje u obliku broja (ili vektora) i naziva se 'zrncem' (seed, random seed). Često se kao seed koristi brojač taktova procesora ili numerička ekvivalentna vrijednost sistemskog vremena.
- Reproduktivnost sekvence.
GPRS je potpuno deterministički, stoga zadani seed prilikom inicijalizacije jasno određuje cijelu buduću sekvencu brojeva. To znači da će pojedinačni GPRS, inicijaliziran istim seedom (u različito vrijeme, u različitim programima, na različitim uređajima), generirati istu sekvencu.
Također treba znati karakterističnu raspodjelu vjerojatnosti GPRS-a — koje brojeve će generirati i s kojom vjerojatnošću. Najčešće je to ili normalna raspodjela (normal distribution), ili ravnomjerna raspodjela (uniform distribution).
Normalna raspodjela (lijevo) i ravnomjerna raspodjela (desno)
Pretpostavimo da imamo poštenu kocku s 24 strane. Ako je bacimo, vjerojatnost da padne jedinica bit će 1/24 (kao i vjerojatnost da padne bilo koji drugi broj). Ako izvodimo mnogo bacanja i bilježimo rezultate, možemo primijetiti da se sve strane pojavljuju otprilike istom učestalošću. U suštini, ovu kocku možemo smatrati GPRS-om s ravnomjernom raspodjelom.
A što ako bacimo odmah 10 takvih kocki i računamo ukupnu svotu bodova? Hoće li za nju ostati ravnomjernost? Ne. Najčešće će svota biti blizu 125 bodova, tj. nekoj prosječnoj vrijednosti. Kao posljedicu — čak i prije bacanja možemo otprilike procijeniti budući rezultat.
Razlog je u tome što postoji najveći broj kombinacija za dobivanje prosječne svote bodova. Što smo dalje od nje, to je manje kombinacija — a samim tim, manja vjerojatnost pojavljivanja. Ako te podatke vizualiziramo, neće daleko podsjećati na oblik zvona. Stoga se s određenom dozom fleksibilnosti sustav od 10 kocaka može nazvati GPRS-om s normalnom raspodjelom.
Još jedan primjer, samo u ravnini — gađanje mete. Strijelac će biti GPRS koji generira par brojeva (x, y), koji se prikazuju na grafu.
Slažete se da je opcija s lijeve strane bliža stvarnom životu — to je RND s normalnom distribucijom. Međutim, ako trebate rasporediti zvijezde na tamnom nebu, desna opcija koja je dobijena pomoću RND-a s uniformnom distribucijom je bolja. Ukratko, birajte generator ovisno o zadatku.
Sada ćemo razgovarati o entropiji sekvence RND-a. Na primjer, postoji sekvenca koja počinje ovako:
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, …
Koliko su ovi brojevi slučajni na prvi pogled? Počnimo s provjerom distribucije.
Izgleda kao blizu uniformnoj, ali ako čitamo sekvencu po dva broja i tumačimo ih kao koordinate na ravnini, dobijemo ovo:
Šabloni postaju jasno uočljivi. A budući da su podaci u sekvenci uređeni na određeni način (tj. imaju nisku entropiju), to može dovesti do te famozne „pristranosti“. U najmanju ruku, takav RND nije baš pogodan za generiranje koordinata na ravnini.
Druga sekvenca:
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, …
Izgleda kao da je sve u redu i na ravnini:
Pogledajmo u volumenu (čitamo po tri broja):
I opet šabloni. Izgradnja vizualizacije u četiri dimenzije već neće biti moguća. No, šabloni mogu postojati i na ovoj dimenziji, kao i na većim.
U istoj kryptografiji, gdje se pred RND postavljaju najstroži zahtjevi, ovakva situacija je kategorički nepoželjna. Stoga su razvijeni posebni algoritmi za procjenu njihove kvalitete, ali o tome nećemo sada razgovarati. Tema je opširna i zaslužuje poseban članak.
Testiranje
Ako nešto ne znamo sigurno, kako se s tim suočiti? Treba li prijeći ulicu ako ne znaš koji signal semafora to dopušta? Posljedice mogu biti različite.
Isto se odnosi na zloglasni random u Unity-u. Dobro je ako dokumentacija otkriva potrebne detalje, ali priča spomenuta na početku članka dogodila se upravo zbog nedostatka željenih pojedinosti.
Ne znajući kako alat radi, ne možeš ga ispravno primijeniti. Uglavnom, došlo je vrijeme da testiramo i provedemo eksperiment kako bismo se konačno uvjerili, barem što se tiče raspodjele.
Rješenje je bilo jednostavno i učinkovito — prikupiti statistiku, dobiti objektivne podatke i pogledati rezultate.
Predmet istraživanja
U Unityju postoji nekoliko načina generiranja nasumičnih brojeva — testirali smo pet.
- System.Random.Next(). Generira cjelobrojne (integer) vrijednosti unutar zadanog raspona.
- System.Random.NextDouble(). Generira brojeve s dvostrukom preciznošću (double) u rasponu od [0; 1).
- UnityEngine.Random.Range(). Generira brojeve s jednostrukom preciznošću (float) unutar zadanog raspona.
- UnityEngine.Random.value. Generira brojeve s jednostrukom preciznošću (float) u rasponu od [0; 1).
- Unity.Mathematics.Random.NextFloat(). Dio nove biblioteke Unity.Mathematics. Generira brojeve s jednostrukom preciznošću (float) unutar zadanog raspona.
Gotovo svugdje u dokumentaciji navedena je ravnomjerna raspodjela, osim za UnityEngine.Random.value (gdje raspodjela nije navedena, ali se očekivala ravnomjerna na temelju sličnosti s UnityEngine.Random.Range()) i Unity.Mathematics.Random.NextFloat() (gdje se koristi algoritam xorshift, a to znači da opet treba čekati ravnomjernu raspodjelu).
Kao očekivani rezultati uzeti su oni navedeni u dokumentaciji.
Metodologija
Napisali smo malu aplikaciju koja je generirala nizove nasumičnih brojeva svakim od prikazanih metoda i spremala rezultate za daljnju obradu.
Duljina svakog niza — 100 000 brojeva.
Raspon vrijednosti nasumičnih brojeva — [0, 100).
Podaci su prikupljeni s nekoliko ciljanih platformi:
- Windows
— Unity v2018.3.14f1, način rada uređivača, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, način rada uređivača, Mono, .NET Standard 2.0
— Unity v5.6.4p4, način rada uređivača, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, gradnja za uređaj, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, gradnja za uređaj, il2cpp, .NET Standard 2.0
Implementacija
Imamo nekoliko različitih načina generiranja nasumičnih brojeva. Za svaki od njih napisat ćemo posebnu klasu-omotač koja bi trebala pružiti:
- Mogućnost postavljanja raspona vrijednosti [min/max). Bit će postavljena putem konstruktora.
- Metodu koja vraća nasumični broj. Kao tip odabrat ćemo float, kao općenitiji tip.
- Naziv načina generiranja radi označavanja rezultata. Za praktičnost ćemo kao vrijednost vraćati puno ime klase + ime metode koja se koristi za generiranje nasumičnih brojeva.
Prvo ćemo definirati apstrakciju koja će biti predstavljena sučeljem IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementacija System.Random.Next()
Ova metoda omogućuje definiranje opsega vrijednosti, ali vraća cijele brojeve (integer), dok su nam potrebni float. Možemo jednostavno interpretirati integer kao float, ili možemo proširiti opseg vrijednosti za nekoliko redova, kompenzirajući ih pri svakoj generaciji slučajnih brojeva. Dobit ćemo nešto poput fiksne točke s zadano određenom preciznošću. Koristit ćemo ovu opciju jer je bliža pravim float vrijednostima.
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;
}
}Implementacija System.Random.NextDouble()
Ovdje je fiksni opseg vrijednosti [0; 1). Da bismo ga projicirali na onaj definiran u konstruktoru, koristit ćemo jednostavnu aritmetiku: X * (max − 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;
}
}Implementacija UnityEngine.Random.Range()
Ova metoda statičke klase UnityEngine.Random omogućava definiranje opsega vrijednosti i vraća slučajan broj tipa float. Nema potrebe za dodatnim pretvorbama.
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);
}
}Implementacija UnityEngine.Random.value
Svojstvo value statičke klase UnityEngine.Random vraća slučajan broj tipa float iz fiksnog opsega vrijednosti [0; 1). Projicirat ćemo ga na zadan opseg na isti način kao i kod implementacije 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;
}
}Implementacija Unity.Mathematics.Random.NextFloat()
Metoda NextFloat() klase Unity.Mathematics.Random vraća float broj i omogućava definiranje raspona vrijednosti. Ključna točka je da svaki primjerak Unity.Mathematics.Random treba inicijalizirati s određenim seed-om kako bismo izbjegli generiranje ponovljenih sekvenci.
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);
}
}Implementacija MainController
Nekoliko implementacija IRandomGenerator je spremno. Sljedeće je generirati sekvence i pohraniti rezultantni skup podataka za obradu. Za to ćemo u Unity-ju stvoriti scenu i mali skript MainController koji će obaviti sav potrebni rad te također odgovarati za interakciju s UI-jem.
Odredit ćemo veličinu skupa podataka i raspon vrijednosti, kao i osigurati metodu koja vraća niz postavljenih i spremnih za rad generatora.
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)
};
}
...
}
}A sada formiramo skup podataka. U ovom slučaju, generiranje podataka će se spojiti s zapisivanjem rezultata u tekstualni tok (u csv formatu). Za pohranu vrijednosti svakog IRandomGenerator predviđena je posebna kolona, a prvi red sadrži ime generatora.
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();
}
}
...
}
}Preostaje pozvati metodu GenerateCsvDataSet i sačuvati rezultat u datoteku, ili odmah prenijeti podatke putem mreže s krajnjeg uređaja na primatelja. 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();
}
}
...
}
}Izvori projekta leže na .
Rezultati
Čuda se nisu dogodila. Ono što smo očekivali, to smo i dobili — u svim slučajevima ravnomjerna distribucija bez naznake zavjere. Ne vidim smisao u dodavanju pojedinačnih grafikonâ po platformama — svi pokazuju otprilike iste rezultate.
Stvarnost je takva:
Vizualizacija sekvenci na ravnini od svih pet načina generiranja:
I vizualizacija u 3D. Ostavit ću samo rezultat System.Random.Next(), kako ne bih stvorio previše identičnog sadržaja.
Priča ispričana u uvodu o normalnoj distribuciji UnityEngine.Random se nije ponovila: ili je od početka bila netočna, ili se nešto od tada promijenilo u motoru. No, sada smo sigurni.
Izvor: habr.com
