Pri razvoju iger morate pogosto nekaj povezati z naključnostjo: Unity ima za to svoj Random, vzporedno z njim pa obstaja System.Random. Nekoč sem pri enem od projektov dobil vtis, da bi lahko oba delovala drugače (čeprav bi morala imeti enakomerno porazdelitev).
Potem se niso spuščali v podrobnosti - dovolj je bilo, da je prehod na System.Random odpravil vse težave. Zdaj smo se odločili, da to preučimo podrobneje in izvedemo malo raziskave: kako »pristranski« ali predvidljivi so RNG-ji in katerega izbrati. Poleg tega sem več kot enkrat slišal nasprotujoča si mnenja o njihovi "poštenosti" - poskusimo ugotoviti, kako se resnični rezultati primerjajo z deklariranimi.
Kratek izobraževalni program ali RNG je pravzaprav RNG
Če ste že seznanjeni z generatorji naključnih števil, potem lahko takoj preskočite na razdelek »Testiranje«.
Naključna števila (RN) so zaporedje števil, ustvarjenih z uporabo nekega naključnega (kaotičnega) procesa, ki je vir entropije. To pomeni, da je to zaporedje, katerega elementi niso med seboj povezani z nobenim matematičnim zakonom - nimajo vzročno-posledične zveze.
Tisto, kar ustvari naključno število, se imenuje generator naključnih števil (RNG). Zdi se, da je vse elementarno, a če preidemo iz teorije v prakso, potem v resnici ni tako enostavno implementirati programskega algoritma za generiranje takšnega zaporedja.
Razlog je v odsotnosti istega kaosa v sodobni potrošniški elektroniki. Brez tega naključna števila prenehajo biti naključna in njihov generator se spremeni v navadno funkcijo očitno definiranih argumentov. Za številne specialnosti na področju IT je to resen problem (na primer kriptografija), za druge pa obstaja povsem sprejemljiva rešitev.
Treba je napisati algoritem, ki bi vrnil, čeprav ne resnično naključna števila, vendar čim bližje njim - tako imenovana psevdonaključna števila (PRN). Algoritem v tem primeru imenujemo generator psevdonaključnih števil (PRNG).
Obstaja več možnosti za ustvarjanje PRNG, vendar bo naslednje pomembno za vse:
- Potreba po predhodni inicializaciji.
PRNG nima vira entropije, zato mu je treba pred uporabo dati začetno stanje. Določeno je kot število (ali vektor) in se imenuje seme (naključno seme). Pogosto se kot seme uporablja števec ure procesorja ali numerični ekvivalent sistemskega časa.
- Ponovljivost zaporedja.
PRNG je popolnoma determinističen, zato seme, določeno med inicializacijo, enolično določa celotno prihodnje zaporedje števil. To pomeni, da bo ločen PRNG, inicializiran z istim semenom (ob različnih časih, v različnih programih, na različnih napravah), ustvaril isto zaporedje.
Prav tako morate poznati verjetnostno porazdelitev, ki označuje PRNG – katera števila bo ustvaril in s kakšno verjetnostjo. Najpogosteje je to normalna ali enakomerna porazdelitev.
Normalna porazdelitev (levo) in enakomerna porazdelitev (desno)
Recimo, da imamo pošteno kocko s 24 stranicami. Če jo vržete, bo verjetnost, da dobite eno, enaka 1/24 (enako kot verjetnost, da dobite katero koli drugo številko). Če naredite veliko metov in zabeležite rezultate, boste opazili, da vsi robovi izpadajo približno enako pogosto. V bistvu lahko to matrico štejemo za RNG z enakomerno porazdelitvijo.
Kaj pa, če vržete 10 teh kock hkrati in preštejete skupno število točk? Ali bo zanj ohranjena enotnost? št. Najpogosteje bo znesek blizu 125 točk, torej do neke povprečne vrednosti. In kot rezultat, še preden izvedete met, lahko približno ocenite prihodnji rezultat.
Razlog je v tem, da obstaja največje število kombinacij za pridobitev povprečne ocene. Dlje kot je od njega, manj je kombinacij - in s tem manjša verjetnost izgube. Če te podatke vizualiziramo, bodo nejasno podobni obliki zvona. Zato lahko sistem 10 kock z določeno mero imenujemo RNG z normalno porazdelitvijo.
Še en primer, le da tokrat na letalu – streljanje v tarčo. Strelec bo RNG, ki generira par števil (x, y), ki je prikazan na grafu.
Strinjam se, da je možnost na levi bližje resničnemu življenju - to je RNG z normalno porazdelitvijo. Če pa morate razpršiti zvezde na temnem nebu, potem je prava možnost, pridobljena z uporabo RNG z enakomerno porazdelitvijo, boljša. Na splošno izberite generator glede na nalogo.
Zdaj pa se pogovorimo o entropiji zaporedja PNG. Na primer, obstaja zaporedje, ki se začne takole:
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, ...
Kako naključne so te številke na prvi pogled? Začnimo s preverjanjem distribucije.
Videti je skoraj enotno, a če preberete zaporedje dveh števil in ju interpretirate kot koordinate na ravnini, dobite tole:
Vzorci postanejo jasno vidni. In ker so podatki v zaporedju urejeni na določen način (to pomeni, da imajo nizko entropijo), lahko to povzroči prav to "pristranskost". Vsaj tak PRNG ni zelo primeren za generiranje koordinat na ravnini.
Še eno zaporedje:
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, ...
Zdi se, da je tukaj vse v redu, tudi na letalu:
Poglejmo glasnost (berite tri številke hkrati):
In spet vzorci. Vizualizacije v štirih dimenzijah ni več mogoče zgraditi. Toda vzorci lahko obstajajo na tej dimenziji in na večjih.
V kriptografiji, kjer so najstrožje zahteve za PRNG, je takšno stanje kategorično nesprejemljivo. Zato so bili razviti posebni algoritmi za oceno njihove kakovosti, ki se jih zdaj ne bomo dotaknili. Tema je obsežna in si zasluži ločen članek.
Testiranje
Če nečesa ne vemo zagotovo, kako potem delati s tem? Ali se splača prečkati cesto, če ne veš kateri semafor to dovoljuje? Posledice so lahko različne.
Enako velja za razvpito naključnost v Unityju. Dobro je, če dokumentacija razkrije potrebne podrobnosti, vendar se je zgodba, omenjena na začetku članka, zgodila prav zaradi pomanjkanja želenih posebnosti.
In če ne veste, kako orodje deluje, ga ne boste mogli pravilno uporabljati. Na splošno je prišel čas za preverjanje in izvedbo poskusa, da se končno prepričamo vsaj o distribuciji.
Rešitev je bila preprosta in učinkovita - zbrati statistiko, pridobiti objektivne podatke in pogledati rezultate.
Predmet študija
V Unity obstaja več načinov za ustvarjanje naključnih števil – preizkusili smo jih pet.
- System.Random.Next(). Generira cela števila v danem območju vrednosti.
- System.Random.NextDouble(). Generira števila z dvojno natančnostjo v območju od [0; 1).
- UnityEngine.Random.Range(). Ustvari števila z enojno natančnostjo (floats) v danem obsegu vrednosti.
- UnityEngine.Random.value. Generira števila z enojno natančnostjo (floats) v območju od [0; 1).
- Unity.Mathematics.Random.NextFloat(). Del nove knjižnice Unity.Mathematics. Ustvari števila z enojno natančnostjo (floats) v danem obsegu vrednosti.
Skoraj povsod v dokumentaciji je bila določena enotna porazdelitev, z izjemo UnityEngine.Random.value (kjer porazdelitev ni bila navedena, vendar je bila po analogiji z UnityEngine.Random.Range() prav tako pričakovana enotna) in Unity.Mathematics.Random .NextFloat() (kjer je v Osnova algoritem xorshift, kar pomeni, da morate spet počakati na enakomerno porazdelitev).
Privzeto so bili pričakovani rezultati sprejeti kot tisti, ki so navedeni v dokumentaciji.
Metodologija
Napisali smo majhno aplikacijo, ki je z vsako od predstavljenih metod generirala zaporedja naključnih števil in rezultate shranila za nadaljnjo obdelavo.
Dolžina posameznega zaporedja je 100 številk.
Razpon naključnih števil je [0, 100).
Podatki so bili zbrani iz več ciljnih platform:
- Windows
— Unity v2018.3.14f1, način urejevalnika, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, način urejevalnika, Mono, .NET Standard 2.0
— Unity v5.6.4p4, način urejevalnika, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, gradnja na napravo, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, gradnja na napravo, il2cpp, .NET Standard 2.0
Реализация
Imamo več različnih načinov za ustvarjanje naključnih števil. Za vsakega izmed njih bomo napisali ločen ovojni razred, ki naj zagotavlja:
- Možnost nastavitve obsega vrednosti [min/max). Nastavljen bo preko konstruktorja.
- Metoda vračanja MF. Za tip izberimo float, saj je bolj splošen.
- Ime metode generiranja za označevanje rezultatov. Zaradi udobja bomo kot vrednost vrnili polno ime razreda + ime metode, uporabljene za generiranje MF.
Najprej deklarirajmo abstrakcijo, ki bo predstavljena z vmesnikom IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementacija System.Random.Next()
Ta metoda vam omogoča nastavitev obsega vrednosti, vendar vrne cela števila, vendar so potrebna lebdeča števila. Celo število lahko preprosto interpretirate kot plavajoče ali pa razširite obseg vrednosti za več velikosti in jih kompenzirate z vsako generacijo srednjega tona. Rezultat bo nekaj podobnega fiksni točki z danim vrstnim redom natančnosti. Uporabili bomo to možnost, ker je bližje dejanski vrednosti plavajoče vrednosti.
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()
Tukaj je fiksni obseg vrednosti [0; 1). Da ga projiciramo na tistega, ki je določen v konstruktorju, uporabimo preprosto aritmetiko: 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()
Ta metoda statičnega razreda UnityEngine.Random vam omogoča nastavitev obsega vrednosti in vrne plavajoči tip. Ni vam treba narediti nobenih dodatnih transformacij.
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
Lastnost vrednosti statičnega razreda UnityEngine.Random vrne plavajoči tip iz fiksnega obsega vrednosti [0; 1). Projicirajmo ga na dano območje na enak način kot pri izvajanju 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() razreda Unity.Mathematics.Random vrne plavajočo vejico tipa float in vam omogoča, da določite obseg vrednosti. Edina niansa je, da bo moral biti vsak primerek Unity.Mathematics.Random inicializiran z nekaj semena - na ta način se bomo izognili generiranju ponavljajočih se zaporedij.
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 MainControllerja
Pripravljenih je več izvedb IRandomGenerator. Nato morate ustvariti zaporedja in shraniti nastali nabor podatkov za obdelavo. Da bi to naredili, bomo ustvarili sceno in majhen skript MainController v Unity, ki bo opravil vse potrebno delo in bo hkrati odgovoren za interakcijo z uporabniškim vmesnikom.
Nastavimo velikost nabora podatkov in obseg vrednosti MF ter pridobimo tudi metodo, ki vrne niz generatorjev, konfiguriranih in pripravljenih za delo.
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)
};
}
...
}
}Sedaj pa ustvarimo nabor podatkov. V tem primeru bo generiranje podatkov kombinirano s snemanjem rezultatov v besedilni tok (v formatu csv). Za shranjevanje vrednosti vsakega IRandomGeneratorja je dodeljen svoj ločen stolpec, prva vrstica pa vsebuje ime generatorja.
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();
}
}
...
}
}Preostane le, da pokličemo metodo GenerateCsvDataSet in rezultat shranimo v datoteko ali pa podatke takoj prenesemo po omrežju s končne naprave na sprejemni strežnik.
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();
}
}
...
}
}Viri projekta so na .
Ugotovitve
Ni se zgodil čudež. Kar so pričakovali, to so dobili – v vseh primerih enakomerno porazdelitev brez kančka zarote. Ne vidim smisla v postavljanju ločenih grafov za platforme - vsi kažejo približno enake rezultate.
Resnica je:
Vizualizacija sekvenc na ravnini iz vseh petih generacijskih metod:
In vizualizacija v 3D. Pustil bom samo rezultat System.Random.Next(), da ne ustvarim kopice enake vsebine.
Zgodba o normalni distribuciji UnityEngine.Random, povedana v uvodu, se ni ponovila: ali je bila sprva napačna ali pa se je v motorju nekaj spremenilo. Toda zdaj smo prepričani.
Vir: www.habr.com