Pri vývoji hier často potrebujete spojiť niečo s náhodnosťou: Unity má na to svoj vlastný Random a paralelne s ním je System.Random. Kedysi som na jednom z projektov nadobudol dojem, že oba môžu fungovať inak (hoci by mali mať rovnomerné rozloženie).
Potom nezachádzali do podrobností - stačilo, že prechod na System.Random opravil všetky problémy. Teraz sme sa rozhodli preskúmať to podrobnejšie a vykonať malý prieskum: aké sú „zaujaté“ alebo predvídateľné RNG a ktorý z nich si vybrať. Navyše som viac ako raz počul protichodné názory na ich „čestnosť“ - skúsme zistiť, ako sa skutočné výsledky porovnávajú s deklarovanými.
Stručný vzdelávací program alebo RNG je vlastne RNG
Ak ste už oboznámení s generátormi náhodných čísel, môžete okamžite prejsť na časť „Testovanie“.
Náhodné čísla (RN) sú sekvenciou čísel generovaných pomocou nejakého náhodného (chaotického) procesu, zdroja entropie. To znamená, že ide o postupnosť, ktorej prvky nie sú prepojené žiadnym matematickým zákonom – nemajú vzťah príčiny a následku.
To, čo vytvára náhodné číslo, sa nazýva generátor náhodných čísel (RNG). Zdalo by sa, že všetko je elementárne, ale ak prejdeme od teórie k praxi, potom v skutočnosti nie je také jednoduché implementovať softvérový algoritmus na generovanie takejto sekvencie.
Dôvodom je absencia rovnakého chaosu v modernej spotrebnej elektronike. Bez nej náhodné čísla prestanú byť náhodné a ich generátor sa zmení na obyčajnú funkciu zjavne definovaných argumentov. Pre množstvo špecializácií v oblasti IT je to vážny problém (napríklad kryptografia), ale pre iných existuje úplne prijateľné riešenie.
Je potrebné napísať algoritmus, ktorý by vracal, aj keď nie skutočne náhodné čísla, ale čo najbližšie k nim – takzvané pseudonáhodné čísla (PRN). Algoritmus sa v tomto prípade nazýva generátor pseudonáhodných čísel (PRNG).
Existuje niekoľko možností na vytvorenie PRNG, ale nasledujúce budú relevantné pre každého:
- Potreba predbežnej inicializácie.
PRNG nemá zdroj entropie, takže pred použitím musí dostať počiatočný stav. Je špecifikovaný ako číslo (alebo vektor) a nazýva sa seed (náhodné semeno). Ako základ sa často používa počítadlo hodín procesora alebo číselný ekvivalent systémového času.
- Sekvenčná reprodukovateľnosť.
PRNG je úplne deterministický, takže seed zadaný počas inicializácie jednoznačne určuje celú budúcu postupnosť čísel. To znamená, že samostatný PRNG inicializovaný s rovnakým zdrojom (v rôznych časoch, v rôznych programoch, na rôznych zariadeniach) vygeneruje rovnakú sekvenciu.
Musíte tiež poznať rozdelenie pravdepodobnosti charakterizujúce PRNG – aké čísla vygeneruje a s akou pravdepodobnosťou. Najčastejšie ide o normálne alebo rovnomerné rozdelenie.
Normálna distribúcia (vľavo) a rovnomerná distribúcia (vpravo)
Povedzme, že máme spravodlivú kocku s 24 stranami. Ak ho hodíte, pravdepodobnosť získania jednotky sa bude rovnať 1/24 (rovnaká ako pravdepodobnosť získania akéhokoľvek iného čísla). Ak urobíte veľa hodov a zaznamenáte výsledky, všimnete si, že všetky hrany vypadávajú s približne rovnakou frekvenciou. V podstate možno túto matricu považovať za RNG s rovnomerným rozložením.
Čo ak hodíte 10 týchto kociek naraz a spočítate celkové body? Zachová sa pre ňu jednotnosť? Nie Najčastejšie sa suma bude blížiť k 125 bodom, teda k nejakej priemernej hodnote. Výsledkom je, že ešte pred vykonaním hodu môžete približne odhadnúť budúci výsledok.
Dôvodom je, že existuje najväčší počet kombinácií na získanie priemerného skóre. Čím ďalej, tým menej kombinácií - a teda aj nižšia pravdepodobnosť straty. Ak sú tieto údaje vizualizované, budú sa nejasne podobať tvaru zvonu. Preto s určitým úsekom možno systém 10 kociek nazvať RNG s normálnym rozdelením.
Ďalší príklad, len tentoraz v lietadle – streľba na cieľ. Strelec bude RNG, ktorý generuje dvojicu čísel (x, y), ktoré sú zobrazené na grafe.
Súhlaste s tým, že možnosť vľavo je bližšie k skutočnému životu - ide o RNG s normálnym rozložením. Ak však potrebujete rozptýliť hviezdy na tmavej oblohe, potom je vhodnejšia správna možnosť získaná pomocou RNG s rovnomerným rozložením. Vo všeobecnosti si vyberte generátor v závislosti od aktuálnej úlohy.
Teraz si povedzme o entropii postupnosti PNG. Existuje napríklad 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, ...
Aké náhodné sú tieto čísla na prvý pohľad? Začnime kontrolou distribúcie.
Vyzerá to takmer uniformne, ale ak si prečítate postupnosť dvoch čísel a interpretujete ich ako súradnice v rovine, dostanete toto:
Vzory budú jasne viditeľné. A keďže dáta v sekvencii sú usporiadané určitým spôsobom (t. j. majú nízku entropiu), môže to viesť k práve tomuto „zaujatosti“. Minimálne takýto PRNG nie je veľmi vhodný na generovanie súradníc v 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 všetko je v poriadku aj v lietadle:
Pozrime sa na objem (čítajte tri čísla naraz):
A opäť vzory. Štvorrozmernú vizualizáciu už nie je možné skonštruovať. Ale vzory môžu existovať v tejto dimenzii a vo väčších.
V kryptografii, kde sú na PRNG kladené najprísnejšie požiadavky, je takáto situácia kategoricky neprijateľná. Na posúdenie ich kvality boli preto vyvinuté špeciálne algoritmy, ktorých sa teraz nebudeme dotýkať. Téma je rozsiahla a zaslúži si samostatný článok.
Testovanie
Ak niečo nevieme s istotou, ako s tým potom pracovať? Oplatí sa prejsť cez cestu, keď neviete, ktorý semafor to umožňuje? Následky môžu byť rôzne.
To isté platí pre notoricky známu náhodnosť v Unity. Je dobré, ak dokumentácia odhaľuje potrebné podrobnosti, ale príbeh spomenutý na začiatku článku sa stal práve kvôli nedostatku požadovaných špecifík.
A ak neviete, ako nástroj funguje, nebudete ho môcť správne používať. Vo všeobecnosti nastal čas na kontrolu a uskutočnenie experimentu, aby sme sa konečne uistili aspoň o distribúcii.
Riešenie bolo jednoduché a efektívne – zbierať štatistiky, získavať objektívne dáta a pozerať sa na výsledky.
Predmet štúdia
V Unity existuje niekoľko spôsobov generovania náhodných čísel – testovali sme päť.
- System.Random.Next(). Generuje celé čísla v danom rozsahu hodnôt.
- System.Random.NextDouble(). Generuje čísla s dvojnásobnou presnosťou v rozsahu od [0; 1).
- UnityEngine.Random.Range(). Generuje jednoduché čísla s presnosťou (pohybuje sa) v danom rozsahu hodnôt.
- UnityEngine.Random.value. Generuje čísla s jednoduchou presnosťou (pohybuje sa) v rozsahu od [0; 1).
- Unity.Mathematics.Random.NextFloat(). Súčasť novej knižnice Unity.Mathematics. Generuje jednoduché čísla s presnosťou (pohybuje sa) v danom rozsahu hodnôt.
Takmer všade v dokumentácii bola špecifikovaná jednotná distribúcia, s výnimkou UnityEngine.Random.value (kde distribúcia nebola špecifikovaná, ale analogicky s UnityEngine.Random.Range() uniforma sa tiež očakávala) a Unity.Mathematics.Random .NextFloat() (kde v Základom je algoritmus xorshift, čo znamená, že opäť musíte počkať na rovnomerné rozdelenie).
Štandardne boli očakávané výsledky brané tak, ako sú uvedené v dokumentácii.
technika
Napísali sme malú aplikáciu, ktorá pomocou každej z prezentovaných metód vygenerovala postupnosti náhodných čísel a výsledky uložila na ďalšie spracovanie.
Dĺžka každej sekvencie je 100 000 čísel.
Rozsah náhodných čísel je [0, 100).
Údaje boli zhromaždené z niekoľkých cieľových platforiem:
- Windows
— Unity v2018.3.14f1, režim editora, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, režim editora, Mono, .NET Standard 2.0
— Unity v5.6.4p4, režim editora, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, zostava na zariadenie, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, zostava na zariadenie, il2cpp, .NET Standard 2.0
Реализация
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 poskytovať:
- Možnosť nastavenia rozsahu hodnôt [min/max). Nastaví sa cez konštruktor.
- Metóda vracia MF. Ako typ zvolíme float, keďže je všeobecnejší.
- Názov metódy generovania na označovanie výsledkov. Pre pohodlie vrátime ako hodnotu celý názov triedy + názov metódy použitej na generovanie MF.
Najprv deklarujme abstrakciu, ktorú bude reprezentovať rozhranie IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementácia System.Random.Next()
Táto metóda vám umožňuje nastaviť rozsah hodnôt, ale vracia celé čísla, ale sú potrebné plávajúce čísla. Celé číslo môžete jednoducho interpretovať ako pohyblivé číslo alebo môžete rozšíriť rozsah hodnôt o niekoľko rádov a kompenzovať ich pri každej generácii stredného rozsahu. Výsledkom bude niečo ako pevný bod s daným poradím presnosti. Túto možnosť použijeme, pretože je bližšie k skutočnej floatovej hodnote.
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 do konštruktora, 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 statickej triedy UnityEngine.Random vám umožňuje nastaviť rozsah hodnôt a vráti typ float. Nemusíte robiť žiadne ďalšie transformácie.
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 statickej triedy UnityEngine.Random vracia typ float z pevného rozsahu hodnôt [0; 1). Premietnime to na daný rozsah rovnakým spôsobom ako pri implementácii 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;
}
}Implementácia Unity.Mathematics.Random.NextFloat()
Metóda NextFloat() triedy Unity.Mathematics.Random vracia plávajúcu desatinnú čiarku typu float a umožňuje vám zadať rozsah hodnôt. Jedinou nuansou je, že každá inštancia Unity.Mathematics.Random bude musieť byť inicializovaná nejakým seedom - týmto spôsobom 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 MainControlleru
Pripravených je niekoľko implementácií IRandomGenerator. Ďalej musíte vygenerovať sekvencie a uložiť výsledný súbor údajov na spracovanie. K tomu si v Unity vytvoríme scénu a malý MainController skript, ktorý urobí všetku potrebnú prácu a zároveň bude zodpovedný za interakciu s UI.
Nastavme veľkosť súboru údajov a rozsah hodnôt MF a získajme tiež metódu, ktorá vráti pole generátorov nakonfigurovaných a pripravených na prácu.
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)
};
}
...
}
}Teraz vytvoríme súbor údajov. V tomto prípade bude generovanie dát spojené so záznamom výsledkov do textového streamu (vo formáte csv). Na uloženie hodnôt každého generátora IRandomGenerator je priradený vlastný samostatný stĺpec a 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();
}
}
...
}
}Ostáva už len zavolať metódu GenerateCsvDataSet a výsledok uložiť 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ú na .
výsledky
Žiadny zázrak sa nekonal. Čo očakávali, to aj dostali – vo všetkých prípadoch rovnomerné rozloženie bez náznaku konšpirácií. Nevidím zmysel uvádzať samostatné grafy pre platformy – všetky ukazujú približne rovnaké výsledky.
Realita je taká:
Vizualizácia sekvencií na rovine zo všetkých piatich metód generovania:
A vizualizácia v 3D. Nechám len výsledok System.Random.Next(), aby nevzniklo množstvo rovnakého obsahu.
V úvode rozprávaný príbeh o normálnej distribúcii UnityEngine.Random sa neopakoval: buď to bolo spočiatku chybné, alebo sa odvtedy niečo v motore zmenilo. Ale teraz sme si istí.
Zdroj: hab.com