U razvoju igara često morate nešto vezati uz slučajnost: Unity za to ima svoj Random, a paralelno s njim postoji System.Random. Jednom davno, na jednom od projekata, stekao sam dojam da oba mogu raditi drugačije (iako bi trebali imati ravnomjernu raspodjelu).
Zatim nisu ulazili u detalje - bilo je dovoljno da je prijelaz na System.Random ispravio sve probleme. Sada smo odlučili to detaljnije proučiti i provesti malo istraživanje: koliko su RNG-ovi "pristrani" ili predvidljivi i koji odabrati. Štoviše, više puta sam čuo oprečna mišljenja o njihovoj "poštenosti" - pokušajmo shvatiti kako se stvarni rezultati uspoređuju s deklariranima.
Kratki obrazovni program ili RNG je zapravo RNG
Ako ste već upoznati s generatorima slučajnih brojeva, odmah možete prijeći na odjeljak "Testiranje".
Slučajni brojevi (RN) su niz brojeva generiran pomoću nekog slučajnog (kaotičnog) procesa, izvora entropije. To jest, ovo je niz čiji elementi nisu međusobno povezani nikakvim matematičkim zakonom - nemaju uzročno-posljedičnu vezu.
Ono što stvara slučajni broj naziva se generator slučajnih brojeva (RNG). Čini se da je sve elementarno, ali ako prijeđemo s teorije na praksu, zapravo nije tako jednostavno implementirati softverski algoritam za generiranje takvog niza.
Razlog leži u nedostatku tog istog kaosa u modernoj potrošačkoj elektronici. Bez njega slučajni brojevi prestaju biti slučajni, a njihov se generator pretvara u običnu funkciju očito definiranih argumenata. Za niz specijalnosti u IT području to je ozbiljan problem (primjerice, kriptografija), ali za druge postoji sasvim prihvatljivo rješenje.
Potrebno je napisati algoritam koji bi vraćao, iako ne stvarno slučajne brojeve, ali što bliže njima - takozvane pseudo-slučajne brojeve (PRN). Algoritam se u ovom slučaju naziva generator pseudoslučajnih brojeva (PRNG).
Postoji nekoliko opcija za stvaranje PRNG-a, ali sljedeće će biti relevantno za sve:
- Potreba za preliminarnom inicijalizacijom.
PRNG nema izvor entropije, pa mu se prije upotrebe mora dati početno stanje. Specificira se kao broj (ili vektor) i naziva se sjeme (slučajno sjeme). Često se brojač takta procesora ili numerički ekvivalent sistemskog vremena koristi kao početna vrijednost.
- Ponovljivost sekvence.
PRNG je potpuno deterministički, tako da početna vrijednost navedena tijekom inicijalizacije jedinstveno određuje cijeli budući niz brojeva. To znači da će zasebni PRNG inicijaliziran s istim sjemenom (u različito vrijeme, u različitim programima, na različitim uređajima) generirati isti niz.
Također morate znati distribuciju vjerojatnosti koja karakterizira PRNG - koje će brojeve generirati i s kojom vjerojatnošću. Najčešće je to ili normalna raspodjela ili jednolika raspodjela.
Normalna raspodjela (lijevo) i ravnomjerna raspodjela (desno)
Recimo da imamo poštenu matricu s 24 strane. Ako ga bacite, vjerojatnost da dobijete jedan bit će jednaka 1/24 (ista je vjerojatnost da dobijete bilo koji drugi broj). Ako napravite mnogo bacanja i zabilježite rezultate, primijetit ćete da svi rubovi ispadaju približno jednakom učestalošću. U biti, ova matrica se može smatrati RNG-om s ravnomjernom distribucijom.
Što ako bacite 10 ovih kockica odjednom i prebrojite ukupne bodove? Hoće li se za njega održati uniformnost? Ne. Najčešće će iznos biti blizu 125 bodova, odnosno nekoj prosječnoj vrijednosti. I kao rezultat toga, čak i prije bacanja, možete grubo procijeniti budući rezultat.
Razlog je što postoji najveći broj kombinacija za dobivanje prosječne ocjene. Što je dalje od njega, to je manje kombinacija - i, shodno tome, manja je vjerojatnost gubitka. Ako se ti podaci vizualiziraju, nejasno će nalikovati obliku zvona. Stoga se, uz malo rastezanja, sustav od 10 kockica može nazvati RNG s normalnom distribucijom.
Još jedan primjer, samo ovaj put u avionu – gađanje mete. Strijelac će biti RNG koji generira par brojeva (x, y) koji se prikazuju na grafikonu.
Složite se da je opcija s lijeve strane bliža stvarnom životu - ovo je RNG s normalnom distribucijom. Ali ako trebate rasuti zvijezde na tamnom nebu, onda je prava opcija, dobivena korištenjem RNG-a s ravnomjernom distribucijom, bolja. Općenito, odaberite generator ovisno o zadatku.
Razgovarajmo sada o entropiji PNG niza. Na primjer, postoji niz koji 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 skoro uniformno, ali ako pročitate niz od dva broja i protumačite ih kao koordinate u ravnini, dobit ćete ovo:
Uzorci postaju jasno vidljivi. A budući da su podaci u nizu poredani na određeni način (to jest, imaju nisku entropiju), to može uzrokovati upravo tu "pristranost". U najmanju ruku, takav PRNG nije baš prikladan za generiranje koordinata u ravnini.
Drugi niz:
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, ...
Čini se da je ovdje sve u redu čak i u avionu:
Pogledajmo volumen (čitajte tri broja odjednom):
I opet šare. Više nije moguće konstruirati vizualizaciju u četiri dimenzije. Ali obrasci mogu postojati na ovoj dimenziji i na većim.
U kriptografiji, gdje se PRNG-ovima nameću najstroži zahtjevi, takva je situacija kategorički neprihvatljiva. Stoga su razvijeni posebni algoritmi za procjenu njihove kvalitete, kojih se sada nećemo doticati. Tema je opsežna i zaslužuje poseban članak.
Testiranje
Ako nešto ne znamo sigurno, kako onda s tim raditi? Isplati li se prelaziti cestu ako ne znaš koji semafor to dopušta? Posljedice mogu biti različite.
Isto vrijedi i za notornu slučajnost u Unityju. Dobro je ako dokumentacija otkriva potrebne detalje, ali priča s početka članka dogodila se upravo zbog nedostatka željenih specifičnosti.
A ako ne znate kako alat radi, nećete ga moći pravilno koristiti. Općenito, došlo je vrijeme da se provjeri i izvede eksperiment kako bi se konačno uvjerili barem u distribuciju.
Rješenje je bilo jednostavno i učinkovito - prikupiti statistiku, dobiti objektivne podatke i pogledati rezultate.
Predmet proučavanja
Postoji nekoliko načina za generiranje nasumičnih brojeva u Unityju - testirali smo pet.
- System.Random.Next(). Generira cijele brojeve u zadanom rasponu vrijednosti.
- System.Random.NextDouble(). Generira brojeve dvostruke preciznosti u rasponu od [0; 1).
- UnityEngine.Random.Range(). Generira brojeve pojedinačne preciznosti (float) u zadanom rasponu vrijednosti.
- UnityEngine.Random.value. Generira brojeve jednostruke preciznosti (float) u rasponu od [0; 1).
- Unity.Mathematics.Random.NextFloat(). Dio nove biblioteke Unity.Mathematics. Generira brojeve pojedinačne preciznosti (float) u zadanom rasponu vrijednosti.
Gotovo posvuda u dokumentaciji specificirana je uniformna distribucija, s izuzetkom UnityEngine.Random.value (gdje distribucija nije navedena, ali po analogiji s UnityEngine.Random.Range() također se očekivala uniformna) i Unity.Mathematics.Random .NextFloat() (gdje je u Osnova xorshift algoritam, što znači da opet morate čekati jednoliku distribuciju).
Prema zadanim postavkama očekivani rezultati uzeti su kao oni navedeni u dokumentaciji.
tehnika
Napisali smo malu aplikaciju koja je generirala nizove slučajnih brojeva koristeći svaku od predstavljenih metoda i spremala rezultate za daljnju obradu.
Dužina svakog niza je 100 brojeva.
Raspon slučajnih brojeva je [0, 100).
Podaci su prikupljeni s nekoliko ciljnih platformi:
- Windows
— Unity v2018.3.14f1, način uređivača, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, način uređivača, Mono, .NET Standard 2.0
— Unity v5.6.4p4, način uređivača, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, verzija po uređaju, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, gradnja po uređaju, il2cpp, .NET Standard 2.0
Provedba
Imamo nekoliko različitih načina za generiranje nasumičnih brojeva. Za svaku od njih napisat ćemo zasebnu klasu omotača koja bi trebala pružiti:
- Mogućnost postavljanja raspona vrijednosti [min/max). Postavlja se preko konstruktora.
- Metoda koja vraća MF. Odaberimo float kao tip, jer je općenitiji.
- Naziv metode generiranja za označavanje rezultata. Radi praktičnosti, vratit ćemo kao vrijednost puni naziv klase + naziv metode korištene za generiranje MF-a.
Prvo, deklarirajmo apstrakciju koja će biti predstavljena sučeljem IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementacija System.Random.Next()
Ova metoda vam omogućuje da postavite raspon vrijednosti, ali vraća cijele brojeve, ali su potrebni brojevi s pomičnim pomikanjem. Možete jednostavno interpretirati cijeli broj kao float ili možete proširiti raspon vrijednosti za nekoliko redova veličine, kompenzirajući ih sa svakom generacijom srednjeg tona. Rezultat će biti nešto poput fiksne točke sa zadanim redoslijedom točnosti. Koristit ćemo ovu opciju jer je bliža stvarnoj float vrijednosti.
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 raspon vrijednosti [0; 1). Da bismo ga projicirali na onaj naveden u konstruktoru, koristimo 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ćuje postavljanje raspona vrijednosti i vraća tip float. Ne morate raditi nikakve dodatne transformacije.
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 vrijednosti statičke klase UnityEngine.Random vraća tip float iz fiksnog raspona vrijednosti [0; 1). Projicirajmo ga na zadani raspon na isti način kao 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 pokretni zarez tipa float i omogućuje vam da odredite raspon vrijednosti. Jedina nijansa je da će se svaka instanca Unity.Mathematics.Random morati inicijalizirati s nekim sjemenom - na taj način ćemo izbjeći generiranje nizova koji se ponavljaju.
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-a
Nekoliko implementacija IRandomGeneratora je spremno. Zatim trebate generirati nizove i spremiti rezultirajući skup podataka za obradu. Da bismo to učinili, napravit ćemo scenu i malu MainController skriptu u Unityju, koja će obaviti sav potreban posao i ujedno biti odgovorna za interakciju s korisničkim sučeljem.
Postavimo veličinu skupa podataka i raspon MF vrijednosti, a također ćemo dobiti metodu koja vraća niz generatora konfiguriranih i spremnih za rad.
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)
};
}
...
}
}Kreirajmo sada skup podataka. U ovom slučaju, generiranje podataka će se kombinirati sa snimanjem rezultata u tekstualni tok (u csv formatu). Za pohranjivanje vrijednosti svakog IRandomGeneratora, dodijeljen je vlastiti zasebni stupac, a prvi redak sadrži naziv 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 samo pozvati metodu GenerateCsvDataSet i rezultat spremiti u datoteku ili podatke odmah prenijeti mrežom s krajnjeg uređaja na poslužitelj primatelja.
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 su na .
Nalazi
Nije se dogodilo nikakvo čudo. Ono što su očekivali to su i dobili – u svim slučajevima ravnomjernu raspodjelu bez trunke zavjere. Ne vidim smisao stavljanja zasebnih grafikona za platforme - svi pokazuju približno iste rezultate.
Stvarnost je:
Vizualizacija nizova na ravnini iz svih pet generacijskih metoda:
I vizualizacija u 3D. Ostavit ću samo rezultat System.Random.Next() kako ne bih proizvodio hrpu identičnog sadržaja.
Priča ispričana u uvodu o normalnoj distribuciji UnityEngine.Randoma nije se ponovila: ili je u početku bila pogrešna ili se u međuvremenu nešto promijenilo u motoru. Ali sada smo sigurni.
Izvor: www.habr.com