V hernom vývoji je často potrebné niečo spojiť s randomom: pre Unity na to existuje jeho Random, vedľa neho je aj System.Random. Niekedy dávno sa na jednom z projektov vytvoril pocit, že oba môžu fungovať odlišne (hoci by mali mať rovnomerné rozdelenie).
Vtedy sme sa do detailov nezapodievali — stačilo, že prechod na System.Random opravil všetky problémy. Teraz sme sa rozhodli podrobnejšie rozobrať a vykonať malý prieskum: do akej miery sú „predpojaté“ alebo predvídateľné generátory náhodných čísel a ktorý z nich si vybrať. Navyše som opakovane počul protichodné názory na ich „čestnosť“ — pokúsime sa prísť na to, ako sa reálne výsledky zhodujú s deklarovanými.
Krátke vzdelanie alebo čo sú to vlastne generátory náhodných čísel.
Ak ste už oboznámení s generátormi náhodných čísel, môžete okamžite prejsť na sekciu „Testovanie“.
Náhodné čísla (NC) — to je sekvencia čísel generovaná pomocou nejakého náhodného (chaotického) procesu, zdroja entropie. To znamená, že ide o takú sekvenciu, ktorých prvky nie sú vzájomne prepojené žiadnym matematickým zákonom — chýba im príčinná súvislosť.
To, čo vytvára NC, sa nazýva generátor náhodných čísel (GNC). Zdalo by sa, že ide o elementárnu záležitosť, ale ak prejdeme od teórie k praxi, implementovať programový algoritmus generovania takej sekvencie nie je tak jednoduché.
Príčina spočíva v absencii tej správnej chaotičnosti v modernej spotrebnej elektronike. Bez nej prestávajú byť náhodné čísla náhodnými a ich generátor sa mení na obyčajnú funkciu s vopred určenými argumentmi. Pre celú radu špecializácií v IT oblasti je to vážny problém (napríklad pre kryptografiu), pre ostatných však existuje celkom prijateľné riešenie.
Je potrebné napísať algoritmus, ktorý by vracal aj keď nie pravé náhodné čísla, ale maximálne sa im priblížil — tzv. pseudonáhodné čísla (PNC). Algoritmus sa v takom prípade nazýva generátor pseudonáhodných čísel (GPNC).
Existuje niekoľko variantov vytvorenia GPNC, ale pre všetky bude aktuálne nasledujúce:
- Potrebnosť predbežnej inicializácie.
Generátor pseudonáhodných čísel (GPCH) je zbavený zdroja entropie, preto je pred jeho použitím potrebné určiť počiatočný stav. Ten sa zadáva vo forme čísla (alebo vektora) a nazýva sa semeno (seed, random seed). Často sa ako semeno používa čítač taktov procesora alebo číselný ekvivalent systémového času.
- Reprodukovateľnosť sekvencie.
GPCH je úplne deterministický, preto zadané semeno pri inicializácii jednoznačne určuje celú budúcu sekvenciu čísel. To znamená, že samostatne vzatý GPCH inicializovaný rovnakým semenem (v rôznych časoch, v rôznych programoch, na rôznych zariadeniach) bude generovať rovnakú sekvenciu.
Ešte treba poznať charakteristické rozdelenie pravdepodobnosti GPCH — ktoré čísla bude generovať a s akou pravdepodobnosťou. Najčastejšie ide buď o normálne rozdelenie (normal distribution), alebo o rovnomerné rozdelenie (uniform distribution).
Normálne rozdelenie (vľavo) a rovnomerné rozdelenie (vpravo)
Predpokladajme, že máme férovú hraciu kocku so 24 stranami. Ak ju hodíme, pravdepodobnosť, že padne jednotka, bude 1/24 (rovnako ako pravdepodobnosť, že padne akékoľvek iné číslo). Ak vykonáme množstvo hodov a zaznamenáme výsledky, môžeme si všimnúť, že všetky strany vypadnú približne s rovnakou frekvenciou. V podstate túto hraciu kocku môžeme považovať za generátor náhodných čísel s rovnomerným rozdelením.
A čo keď okamžite hodíme 10 takýchto kostiek a počítame celkový súčet bodov? Bude pre ňu platiť rovnomernosť? Nie. Väčšinou bude súčet blízko 125 bodom, teda niektorému priemernému hodnoteniu. A teda ešte pred hodom môžeme približne odhadnúť budúci výsledok.
Dôvodom je, že na získanie priemerného súčtu bodov existuje najväčšie množstvo kombinácií. Čím ďalej od neho, tým menej kombinácií — a teda aj menšia pravdepodobnosť vypadnutia. Ak tieto údaje vizualizujeme, budú pripomínať tvar zvona. Preto s určitou dávkou voľnosti môžeme systém z 10 kostiek nazvať generátorom náhodných čísel s normálnym rozdelením.
Ešte jeden príklad, ale už v rovine — streľba na terč. Strelcom bude generátor náhodných čísel, ktorý generuje pár čísel (x, y), ktorý sa zobrazuje na grafe.
Súhlasíte, že ľavý variant je bližšie k skutočnému životu — je to generátor náhodných čísel s normálnym rozdelením. Ale ak potrebujete roztrúsiť hviezdy na tmavej oblohe, pravý variant získaný pomocou generátora s rovnomerným rozdelením bude lepší. Všeobecne vyberte generátor v závislosti od zadanej úlohy.
Teraz sa rozprávajme o entropii sekvencie náhodne generovaných čísel. Napríklad existuje sekvencia, ktorá začína takto:
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, …
Ako náhodné sa tieto čísla na prvý pohľad zdajú? Začnime kontrolou rozdelenia.
Vyzerá to skoro ako rovnomerné, ale ak by sme čítali sekvenciu po dvoch číslach a interpretovali ich ako súradnice na rovine, dostaneme toto:
Jasne sa ukazujú vzory. A keďže sú dáta v sekvencii usporiadané určitým spôsobom (čo znamená, že majú nízku entropiu), môže to generovať práve túto "predpojatost". Minimálne, takýto generátor náhodných čísel sa veľmi nehodí na generovanie súradníc na rovine.
Ďalšia sekvencia:
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, …
Zdá sa, že tu je všetko v poriadku, aj na rovine:
Pozrime sa vo vnútorných dimenziách (čítať po troch číslach):
A opäť vzory. Vytvoriť vizualizáciu vo štyroch dimenziách už nebude možné. Ale vzory môžu existovať aj v tejto dimenzii a vo väčších.
V tej istej kryptografii, kde sú kladené najprísnejšie požiadavky na generátory náhodných čísel, je takáto situácia kategoricky neprijateľná. Preto boli vyvinuté špeciálne algoritmy na hodnotenie ich kvality, o ktorých sa teraz nebudeme zaoberať. Téma je rozsiahla a zaslúži si samostatný článok.
Testovanie
Ak nevieme niečo s istotou, ako s tým pracovať? Má zmysel prechádzať cestu, ak neviete, aký signál to povolí? Následky môžu byť rôzne.
To isté platí pre preslávený random v Unity. Je dobre, ak dokumentácia odhalí potrebné podrobnosti, ale spomenutý príbeh na začiatku článku sa presne udial kvôli absencii žiadanej konkrétnosti.
Ak nepoznáte, ako nástroj funguje, nebudete ho môcť správne použiť. V podstate je čas overiť a vykonať experiment, aby ste sa aspoň nakoniec uistili o rozdelení.
Riešenie bolo jednoduché a efektívne — zhromaždiť štatistiku, získať objektívne dáta a pozrieť sa na výsledky.
Predmet výskumu
Vo Unity existuje niekoľko spôsobov generovania náhodných čísel — testovali sme päť.
- System.Random.Next(). Generuje celé čísla (integer) v zadanom rozsahu hodnôt.
- System.Random.NextDouble(). Generuje čísla s dvojitou presnosťou (double) v rozsahu od [0; 1).
- UnityEngine.Random.Range(). Generuje čísla s jednou presnosťou (float) v zadanom rozsahu hodnôt.
- UnityEngine.Random.value. Generuje čísla s jednou presnosťou (float) v rozsahu od [0; 1).
- Unity.Mathematics.Random.NextFloat(). Súčasť novej knižnice Unity.Mathematics. Generuje čísla s jednou presnosťou (float) v zadanom rozsahu hodnôt.
Takmer všade v dokumentácii bolo uvedené rovnomerné rozdelenie, s výnimkou UnityEngine.Random.value (kde nie je uvedené, ale podľa analógie s UnityEngine.Random.Range() sa tiež očakávalo rovnomerné) a Unity.Mathematics.Random.NextFloat() (kde je založené na algoritme xorshift, takže opäť treba čakať rovnomerné rozdelenie).
Ako očakávané výsledky sa brali tie, ktoré sú uvedené v dokumentácii.
Metodológia
Napísali sme malú aplikáciu, ktorá generovala sekvencie náhodných čísel každým z prezentovaných spôsobov a ukladala výsledky na ďalšie spracovanie.
Dĺžka každej sekvencie — 100 000 čísel.
Rozsah hodnôt náhodných čísel — [0, 100).
Údaje sme zhromažďovali z niekoľkých cieľových platforiem:
- Windows
— Unity v2018.3.14f1, Editor mód, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, Editor mód, Mono, .NET Standard 2.0
— Unity v5.6.4p4, Editor mód, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, zostavenie na zariadenie, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, zostavenie na zariadenie, il2cpp, .NET Standard 2.0
Implementácia
Máme niekoľko rôznych spôsobov generovania náhodných čísel. Pre každý z nich napíšeme samostatnú obalovú triedu, ktorá by mala poskytnúť:
- Možnosť zadať rozsah hodnôt [min/max). Bude zadaná prostredníctvom konštruktora.
- Metódu, ktorá vracia SČ. Ako typ zvolíme float, ako všeobecnejší.
- Názov spôsobu generovania pre označovanie výsledkov. Pre pohodlie budeme ako hodnotu vracať plný názov triedy + názov metódy, ktorá sa používa na generovanie SČ.
Najprv oznámime abstrakciu, ktorá bude reprezentovaná rozhraním IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementácia System.Random.Next()
Táto metóda umožňuje nastaviť rozsah hodnôt, ale vracia celé čísla (integer), kým potrebujeme float. Môžeme jednoducho interpretovať integer ako float, alebo môžeme rozšíriť rozsah hodnôt o niekoľko poriadkov, kompenzujúc ich pri každom generovaní náhodného čísla. Dostaneme niečo ako fixed-point so zadanou presnosťou. Budeme používať tento variant, pretože je bližší skutočnej hodnote float.
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;
}
}Implementácia System.Random.NextDouble()
Tu je pevný rozsah hodnôt [0; 1). Aby sme ho premietli na zadaný v konštruktore, použijeme jednoduchú 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;
}
}Implementácia UnityEngine.Random.Range()
Táto metóda statického triedy UnityEngine.Random umožňuje nastaviť rozsah hodnôt a vracia náhodné číslo typu float. Nebudú potrebné žiadne ďalšie konverzie.
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);
}
}Implementácia UnityEngine.Random.value
Vlastnosť value statického triedy UnityEngine.Random vracia náhodné číslo typu float z pevného rozsahu hodnôt [0; 1). Premietneme ho na zadaný rozsah rovnakým spôsobom ako pri implementácii System.Random.NextDouble().
používajúc 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;
}
}Implementácia Unity.Mathematics.Random.NextFloat()
Metóda NextFloat() triedy Unity.Mathematics.Random vracia typ float a umožňuje zadať rozsah hodnôt. Nuansou je, že každý exemplár Unity.Mathematics.Random treba inicializovať nejakým seed — tak sa vyhneme generovaniu opakujúcich sa 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);
}
}Implementácia MainController
Niekoľko implementácií IRandomGenerator je pripravených. Potom je potrebné vygenerovať sekvencie a uložiť výsledný dataset na spracovanie. Na tento účel vytvoríme v Unity scénu a malý skript MainController, ktorý bude vykonávať všetku potrebnú prácu a súčasne zabezpečovať interakciu s UI.
Určíme veľkosť datasetu a rozsah hodnôt vrátane metódy, ktorá vracia pole nastavených a pripravených generátorov.
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 teraz formujeme dataset. V tomto prípade bude generácia údajov kombinovaná so zápisom výsledkov do textového streamu (vo formáte csv). Na uchovávanie hodnôt každého IRandomGenerator je vyhradený vlastný stĺpec, pričom prvý riadok obsahuje názov generátora.
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();
}
}
...
}
}Je potrebné zavolať metódu GenerateCsvDataSet a uložiť výsledok do súboru, alebo okamžite preniesť dáta po sieti z koncového zariadenia na prijímajúci. 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();
}
}
...
}
}Zdroje projektu sú uložené na .
Výsledky
Zázrak sa nestal. Čo sme očakávali, to sme aj dostali — vo všetkých prípadoch rovnomerné rozdelenie bez náznaku sprisahania. Individuálne grafy podľa platforiem nemá zmysel prikladať — všetky ukazujú približne rovnaké výsledky.
Skutočnosť je taká:
Vizualizácia sekvencií na rovine zo všetkých piatich spôsobov generovania:
A vizualizácia v 3D. Nechám len výsledok System.Random.Next(), aby som nevytváral hromadu rovnakého obsahu.
Príbeh uvedený v úvode o normálnom rozdelení UnityEngine.Random sa neopakoval: buď bol pôvodne chybný, alebo sa od tej doby niečo zmenilo v engíne. Teraz sme ale istí.
Zdroj: habr.com
