Při vývoji her je často potřeba spojit něco s náhodností: Unity k tomu má svůj vlastní Random a paralelně s ním je System.Random. Kdysi dávno jsem na jednom z projektů nabyl dojmu, že oba by mohly fungovat jinak (byť by měly mít rovnoměrné rozložení).
Pak už nezacházeli do detailů – stačilo, že přechod na System.Random všechny problémy napravil. Nyní jsme se rozhodli na to podívat podrobněji a provést malý průzkum: jak jsou RNG „zaujaté“ nebo předvídatelné a který z nich si vybrat. Navíc jsem více než jednou slyšel protichůdné názory na jejich „poctivost“ - zkusme zjistit, jak se skutečné výsledky porovnávají s deklarovanými.
Stručný vzdělávací program neboli RNG je ve skutečnosti RNG
Pokud jste již obeznámeni s generátory náhodných čísel, můžete okamžitě přeskočit do sekce „Testování“.
Náhodná čísla (RN) jsou posloupností čísel generovaných pomocí nějakého náhodného (chaotického) procesu, zdroje entropie. To znamená, že se jedná o posloupnost, jejíž prvky nejsou vzájemně propojeny žádným matematickým zákonem – nemají žádný vztah příčiny a následku.
To, co vytváří náhodné číslo, se nazývá generátor náhodných čísel (RNG). Zdálo by se, že vše je elementární, ale pokud přejdeme od teorie k praxi, pak ve skutečnosti není tak jednoduché implementovat softwarový algoritmus pro generování takové sekvence.
Důvod spočívá v absenci stejného chaosu v moderní spotřební elektronice. Bez něj náhodná čísla přestanou být náhodná a jejich generátor se změní v obyčejnou funkci zjevně definovaných argumentů. Pro řadu specializací v oblasti IT je to vážný problém (například kryptografie), pro jiné však existuje zcela přijatelné řešení.
Je nutné napsat algoritmus, který by vracel, byť ne skutečně náhodná čísla, ale co nejblíže jim – tzv. pseudonáhodná čísla (PRN). Algoritmus se v tomto případě nazývá generátor pseudonáhodných čísel (PRNG).
Existuje několik možností pro vytvoření PRNG, ale následující budou relevantní pro každého:
- Nutnost předběžné inicializace.
PRNG nemá žádný zdroj entropie, takže před použitím musí mít počáteční stav. Zadává se jako číslo (nebo vektor) a nazývá se seed (náhodné semeno). Jako základ se často používá počítadlo hodin procesoru nebo číselný ekvivalent systémového času.
- Reprodukovatelnost sekvence.
PRNG je zcela deterministický, takže seed zadaný během inicializace jednoznačně určuje celou budoucí sekvenci čísel. To znamená, že samostatný PRNG inicializovaný stejným seedem (v různých časech, v různých programech, na různých zařízeních) vygeneruje stejnou sekvenci.
Musíte také znát rozdělení pravděpodobnosti charakterizující PRNG – jaká čísla bude generovat as jakou pravděpodobností. Nejčastěji se jedná buď o normální rozdělení, nebo o rovnoměrné rozdělení.
Normální rozložení (vlevo) a rovnoměrné rozložení (vpravo)
Řekněme, že máme spravedlivou kostku s 24 stranami. Pokud jej hodíte, pravděpodobnost získání jedničky bude rovna 1/24 (stejná jako pravděpodobnost získání jakéhokoli jiného čísla). Pokud provedete mnoho hodů a zaznamenáte výsledky, všimnete si, že všechny hrany vypadávají s přibližně stejnou frekvencí. V podstatě lze tuto matrici považovat za RNG s rovnoměrným rozložením.
Co když hodíte 10 těchto kostek najednou a spočítáte celkové body? Bude pro něj zachována jednotnost? Ne. Nejčastěji se částka bude blížit 125 bodům, tedy nějaké průměrné hodnotě. A ve výsledku můžete ještě před provedením hodu zhruba odhadnout budoucí výsledek.
Důvodem je, že existuje největší počet kombinací pro získání průměrného skóre. Čím dále od ní, tím méně kombinací - a tím nižší je pravděpodobnost ztráty. Pokud jsou tato data vizualizována, budou matně připomínat tvar zvonu. Proto s určitým úsekem lze systém 10 kostek nazvat RNG s normálním rozdělením.
Další ukázka, tentokrát pouze v letadle - střelba na cíl. Střelec bude RNG, který generuje dvojici čísel (x, y), která se zobrazí v grafu.
Souhlaste s tím, že možnost vlevo je blíže skutečnému životu - jedná se o RNG s normální distribucí. Pokud však potřebujete rozptýlit hvězdy na tmavé obloze, pak je vhodnější správná možnost získaná pomocí RNG s rovnoměrným rozložením. Obecně vybírejte generátor v závislosti na aktuálním úkolu.
Nyní si povíme něco o entropii posloupnosti PNG. Existuje například sekvence, která začíná 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, ...
Jak náhodná jsou tato čísla na první pohled? Začněme kontrolou distribuce.
Vypadá to téměř uniformně, ale pokud přečtete posloupnost dvou čísel a interpretujete je jako souřadnice v rovině, dostanete toto:
Vzory jsou jasně viditelné. A protože data v posloupnosti jsou uspořádána určitým způsobem (to znamená, že mají nízkou entropii), může to vést k onomu „zkreslení“. Minimálně takový PRNG není příliš vhodný pro generování souřadnic v rovině.
Další sekvence:
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á se, že vše je v pořádku i v letadle:
Podívejme se na objem (čti tři čísla najednou):
A opět vzory. Zkonstruovat vizualizaci ve čtyřech rozměrech již není možné. Ale vzory mohou existovat v této dimenzi a ve větších.
V kryptografii, kde jsou na PRNG kladeny ty nejpřísnější požadavky, je taková situace kategoricky nepřijatelná. Pro posouzení jejich kvality byly proto vyvinuty speciální algoritmy, kterých se nyní nebudeme dotýkat. Téma je rozsáhlé a zaslouží si samostatný článek.
Testování
Pokud něco nevíme jistě, jak s tím tedy pracovat? Vyplatí se přecházet silnici, když nevíte, který semafor to umožňuje? Důsledky mohou být různé.
Totéž platí pro notoricky známou náhodnost v Unity. Je dobré, když dokumentace odhaluje potřebné podrobnosti, ale příběh zmíněný na začátku článku se stal právě kvůli nedostatku požadovaných specifik.
A pokud nevíte, jak nástroj funguje, nebudete jej moci správně používat. Obecně platí, že nastal čas zkontrolovat a provést experiment, abychom se konečně ujistili alespoň o distribuci.
Řešení bylo jednoduché a efektivní – sbírat statistiky, získávat objektivní data a dívat se na výsledky.
Předmět studia
Existuje několik způsobů, jak generovat náhodná čísla v Unity - testovali jsme pět.
- System.Random.Next(). Generuje celá čísla v daném rozsahu hodnot.
- System.Random.NextDouble(). Generuje čísla s dvojnásobnou přesností v rozsahu od [0; 1).
- UnityEngine.Random.Range(). Generuje jednotlivá čísla s přesností (plovoucí) v daném rozsahu hodnot.
- UnityEngine.Random.value. Generuje jednotlivá čísla s přesností (plovoucí) v rozsahu od [0; 1).
- Unity.Mathematics.Random.NextFloat(). Část nové knihovny Unity.Mathematics. Generuje jednotlivá čísla s přesností (plovoucí) v daném rozsahu hodnot.
Téměř všude v dokumentaci byla specifikována jednotná distribuce, s výjimkou UnityEngine.Random.value (kde distribuce nebyla specifikována, ale analogicky s UnityEngine.Random.Range() uniforma byla také očekávána) a Unity.Mathematics.Random .NextFloat() (kde v Základem je algoritmus xorshift, což znamená, že opět musíte počkat na jednotné rozdělení).
Ve výchozím nastavení byly očekávané výsledky brány jako výsledky uvedené v dokumentaci.
Metodologie
Napsali jsme malou aplikaci, která pomocí každé z prezentovaných metod generovala posloupnosti náhodných čísel a ukládala výsledky pro další zpracování.
Délka každé sekvence je 100 000 čísel.
Rozsah náhodných čísel je [0, 100).
Data byla shromážděna z několika cílových platforem:
- Windows
— Unity v2018.3.14f1, režim editoru, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, režim editoru, Mono, .NET Standard 2.0
— Unity v5.6.4p4, režim editoru, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, sestavení na zařízení, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, sestavení na zařízení, il2cpp, .NET Standard 2.0
uskutečnění
Máme několik různých způsobů, jak generovat náhodná čísla. Pro každý z nich napíšeme samostatnou obalovou třídu, která by měla poskytovat:
- Možnost nastavení rozsahu hodnot [min/max). Nastaví se pomocí konstruktoru.
- Metoda vrací MF. Jako typ zvolíme plovoucí, jelikož je obecnější.
- Název metody generování pro označení výsledků. Pro usnadnění vrátíme jako hodnotu celý název třídy + název metody použité pro vygenerování MF.
Nejprve deklarujme abstrakci, která bude reprezentována rozhraním IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementace System.Random.Next()
Tato metoda umožňuje nastavit rozsah hodnot, ale vrací celá čísla, ale je potřeba plovoucí. Celé číslo můžete jednoduše interpretovat jako plovoucí nebo můžete rozšířit rozsah hodnot o několik řádů a kompenzovat je s každou generací středního rozsahu. Výsledkem bude něco jako pevný bod s daným řádem přesnosti. Tuto možnost použijeme, protože se blíží skutečné hodnotě 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;
}
}Implementace System.Random.NextDouble()
Zde je pevný rozsah hodnot [0; 1). K jejímu promítnutí na tu zadanou v konstruktoru použijeme jednoduchou 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;
}
}Implementace UnityEngine.Random.Range()
Tato metoda statické třídy UnityEngine.Random umožňuje nastavit rozsah hodnot a vrací typ float. Nemusíte provádět žádné další transformace.
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);
}
}Implementace UnityEngine.Random.value
Vlastnost value statické třídy UnityEngine.Random vrací typ float z pevného rozsahu hodnot [0; 1). Promítněme to na daný rozsah stejným způsobem jako při implementaci 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;
}
}Implementace Unity.Mathematics.Random.NextFloat()
Metoda NextFloat() třídy Unity.Mathematics.Random vrací plovoucí desetinnou čárku typu float a umožňuje zadat rozsah hodnot. Jedinou nuancí je, že každá instance Unity.Mathematics.Random bude muset být inicializována nějakým semenem - tímto způsobem se vyhneme generování opakujících se sekvencí.
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);
}
}Implementace MainControlleru
Několik implementací IRandomGenerator je připraveno. Dále je potřeba vygenerovat sekvence a uložit výslednou datovou sadu pro zpracování. K tomu si v Unity vytvoříme scénu a malý MainController skript, který udělá veškerou potřebnou práci a zároveň bude zodpovědný za interakci s UI.
Pojďme nastavit velikost datové sady a rozsah hodnot MF a také získat metodu, která vrátí pole generátorů nakonfigurovaných a připravených k práci.
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)
};
}
...
}
}Nyní vytvoříme datovou sadu. V tomto případě bude generování dat spojeno se záznamem výsledků do textového streamu (ve formátu csv). Pro uložení hodnot každého IRandomGenerator je přidělen jeho vlastní samostatný sloupec a první řádek obsahuje název generátoru.
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();
}
}
...
}
}Nezbývá než zavolat metodu GenerateCsvDataSet a výsledek uložit do souboru, případně data ihned přenést po síti z koncového zařízení na přijímající 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 jsou na .
výsledky
Žádný zázrak se nekonal. Očekávali to, co dostali – ve všech případech rovnoměrné rozložení bez náznaku konspirací. Nevidím smysl vkládat samostatné grafy pro platformy – všechny ukazují přibližně stejné výsledky.
Realita je taková:
Vizualizace sekvencí na rovině ze všech pěti metod generování:
A vizualizace ve 3D. Nechám pouze výsledek System.Random.Next(), aby nevznikla hromada identického obsahu.
Příběh vyprávěný v úvodu o normální distribuci UnityEngine.Random se neopakoval: buď to bylo zpočátku chybné, nebo se od té doby něco v enginu změnilo. Ale teď jsme si jisti.
Zdroj: www.habr.com