Nel game development è spesso necessario legare qualcosa al caso: Unity ha il suo Random, mentre parallelamente esiste System.Random. Una volta, in uno dei progetti, ha dato l'impressione che entrambi potessero funzionare in modo diverso (anche se dovrebbero avere una distribuzione uniforme).
Allora non ci siamo approfonditi — è bastato che il passaggio a System.Random correggesse tutti i problemi. Ora abbiamo deciso di approfondire e condurre una piccola ricerca: quanto sono 'parziali' o prevedibili i RNG, e quale scegliere. Inoltre, non ho mai smesso di sentire opinioni contraddittorie sulla loro 'onestà' — cerchiamo di capire come i risultati reali si rapportano con quelli dichiarati.
Breve guida o il RNG è in realtà un PRNG
Se siete già familiarità con i generatori di numeri casuali, potete passare direttamente alla sezione 'Test'.
I numeri casuali (NC) sono una sequenza di numeri generata da un certo processo casuale (caotico), fonte di entropia. Vale a dire, è una sequenza i cui elementi non sono legati tra loro da alcuna legge matematica — manca una relazione di causa ed effetto.
Ciò che genera gli NC è chiamato generatore di numeri casuali (RNG). A prima vista, tutto sembra elementare, ma passando dalla teoria alla pratica, in realtà implementare un algoritmo software per generare tale sequenza non è così semplice.
Il motivo sta nell'assenza di quel caos nell'elettronica moderna di consumo. Senza di essa, i numeri casuali smettono di essere casuali e il loro generatore si trasforma in una funzione ordinaria con argomenti ben definiti. Per un certo numero di settori nell'IT, questo rappresenta un serio problema (ad esempio, per la crittografia), mentre per gli altri esiste una soluzione del tutto accettabile.
È necessario scrivere un algoritmo che restituisca, anche se non numeri veramente casuali, almeno quelli massimamente vicini a essi — i cosiddetti numeri pseudocasuali (PRNG). L'algoritmo in questo caso è chiamato generatore di numeri pseudocasuali (PRNG).
Esistono diverse opzioni per creare un PRNG, ma per tutti sarà attuale quanto segue:
- Necessità di un'inizializzazione preliminare.
Il generatore di numeri pseudo casuali (GPC) è privo di una sorgente di entropia, quindi prima dell'uso è necessario specificare lo stato iniziale. Questo viene definito come un numero (o un vettore) e si chiama seme (seed, random seed). Spesso come seed si utilizza un contatore di cicli del processore o l'equivalente numerico del tempo di sistema.
- Riproducibilità della sequenza.
Il GPC è completamente deterministico, quindi il seed specificato in fase di inizializzazione determina univocamente l'intera futura sequenza di numeri. Ciò significa che un dato GPC, inizializzato con lo stesso seed (in tempi diversi, in programmi diversi, su dispositivi diversi) genererà la stessa sequenza.
È necessario anche conoscere la distribuzione di probabilità caratteristica del GPC: quali numeri genererà e con quale probabilità. Di solito questa è o una distribuzione normale (normal distribution) o una distribuzione uniforme (uniform distribution).
Distribuzione normale (a sinistra) e distribuzione uniforme (a destra)
Supponiamo di avere un dado onesto con 24 facce. Se lo lanciamo, la probabilità di ottenere un uno sarà pari a 1/24 (come la probabilità di ottenere qualsiasi altro numero). Se eseguiamo molti lanci e registriamo i risultati, possiamo notare che tutte le facce escono circa con la stessa frequenza. In sostanza, questo dado può essere considerato un GPC con distribuzione uniforme.
E se lanciassimo subito 10 dadi di questo tipo e calcolassimo la somma totale dei punti? La distribuzione rimarrà uniforme? No. Di solito, la somma sarà vicina a 125 punti, ovvero a un certo valore medio. E come conseguenza — anche prima di effettuare il lancio, si può fare una stima approssimativa del risultato futuro.
La ragione è che per ottenere una somma media di punti esistono il maggior numero di combinazioni. Più ci si allontana da essa, meno combinazioni ci sono — e quindi, minore è la probabilità di ottenere quel risultato. Se questi dati venissero visualizzati, avrebbero una forma vagamente simile a un campanile. Pertanto, con un certo sforzo, un sistema di 10 dadi può essere considerato un GPC con distribuzione normale.
Un altro esempio, questa volta in un piano — tiro al bersaglio. Il tiratore sarà un GPC che genera una coppia di numeri (x, y), che vengono visualizzati in un grafico.
Concordate che l'opzione a sinistra è più vicina alla vita reale: è un RNG con distribuzione normale. Ma se si devono spargere le stelle nel cielo scuro, l'opzione a destra, ottenuta con un RNG con distribuzione uniforme, è la scelta migliore. In sostanza, scegliete il generatore in base all'attività che dovete svolgere.
Adesso parliamo dell'entropia della sequenza di RNG. Ad esempio, abbiamo una sequenza che inizia così:
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, …
Quanto sono casuali questi numeri a prima vista? Cominciamo a controllare la distribuzione.
Sembra abbastanza uniforme, ma se leggiamo la sequenza a coppie e le interpretiamo come coordinate su un piano, otteniamo questo:
I pattern diventano chiaramente visibili. Poiché i dati nella sequenza sono ordinati in un certo modo (cioè hanno bassa entropia), questo può generare quella "predisposizione" di cui si parla. Almeno, tale RNG non è molto adatto per generare coordinate sul piano.
Un'altra sequenza:
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, …
Qui sembra andare tutto bene anche sul piano:
Guardiamo in 3D (leggiamo tre numeri alla volta):
E di nuovo i pattern. Costruire una visualizzazione in quattro dimensioni non è più possibile. Ma i pattern possono esistere anche in questa dimensione e in dimensioni superiori.
Nella stessa crittografia, dove gli RNG sono sottoposti ai requisiti più severi, una situazione del genere è categoricamente inaccettabile. Pertanto, sono stati sviluppati algoritmi speciali per valutarne la qualità, di cui ora non parleremo. L'argomento è vasto e giustificherebbe un articolo a parte.
Test
Se non sappiamo qualcosa con certezza, come possiamo affrontarla? Ha senso attraversare la strada se non sai quale segnale semaforico lo permette? Le conseguenze possono variare.
Lo stesso vale per il famigerato random in Unity. Va bene se la documentazione rivela i dettagli necessari, ma la storia menzionata all'inizio dell'articolo è accaduta proprio a causa della mancanza di concretezza desiderata.
Non sapendo come funziona lo strumento, non sarai in grado di applicarlo correttamente. In generale, è tempo di controllare e condurre un esperimento per assicurarsi, almeno riguardo alla distribuzione.
La soluzione era semplice ed efficace: raccogliere statistiche, ottenere dati oggettivi e osservare i risultati.
Oggetto di studio
In Unity esistono diversi modi per generare numeri casuali: abbiamo testato cinque metodi.
- System.Random.Next(). Genera numeri interi (integer) in un intervallo di valori specificato.
- System.Random.NextDouble(). Genera numeri a doppia precisione (double) nell'intervallo [0; 1).
- UnityEngine.Random.Range(). Genera numeri a precisione singola (float) in un intervallo di valori specificato.
- UnityEngine.Random.value. Genera numeri a precisione singola (float) nell'intervallo [0; 1).
- Unity.Mathematics.Random.NextFloat(). Parte della nuova libreria Unity.Mathematics. Genera numeri a precisione singola (float) in un intervallo di valori specificato.
Praticamente ovunque nella documentazione si parlava di distribuzione uniforme, eccetto che per UnityEngine.Random.value (dove la distribuzione non è specificata, ma per analogia con UnityEngine.Random.Range() ci si aspettava una distribuzione uniforme) e Unity.Mathematics.Random.NextFloat() (che si basa su un algoritmo xorshift, quindi si deve aspettare di nuovo una distribuzione uniforme).
Di default, i risultati attesi sono stati considerati quelli indicati nella documentazione.
Metodologia
Abbiamo scritto una piccola applicazione che generava sequenze di numeri casuali utilizzando ciascuno dei metodi presentati e memorizzava i risultati per ulteriori elaborazioni.
La lunghezza di ogni sequenza è di 100.000 numeri.
L'intervallo di valori dei numeri casuali è [0, 100).
I dati sono stati raccolti da diverse piattaforme target:
- Windows
— Unity v2018.3.14f1, modalità Editor, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, modalità Editor, Mono, .NET Standard 2.0
— Unity v5.6.4p4, modalità Editor, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, build per dispositivo, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, build per dispositivo, il2cpp, .NET Standard 2.0
Implementazione
Abbiamo diversi modi per generare numeri casuali. Per ciascuno di essi scriveremo una classe di wrapping separata che deve fornire:
- La possibilità di impostare un intervallo di valori [min/max). Sarà impostato tramite il costruttore.
- Un metodo che restituisce i numeri casuali. Come tipo, sceglieremo float, essendo più generico.
- Il nome del metodo di generazione per l'etichettatura dei risultati. Per comodità, restituiremo come valore il nome completo della classe + il nome del metodo utilizzato per generare i numeri casuali.
Iniziamo a dichiarare l'astrazione che sarà rappresentata dall'interfaccia IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementazione di System.Random.Next()
Questo metodo consente di specificare un intervallo di valori, ma restituisce numeri interi (integer), mentre abbiamo bisogno di float. Possiamo semplicemente interpretare l'integer come float, oppure possiamo espandere l'intervallo di valori su diversi ordini di grandezza, compensandoli ad ogni generazione di numeri casuali. Otterremo qualcosa di simile a un fixed-point con la precisione di ordine specificata. Utilizzeremo quest'ultima opzione, poiché è più vicina al vero valore 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;
}
}Implementazione di System.Random.NextDouble()
Qui c'è un intervallo fisso di valori [0; 1). Per proiettarlo sull'intervallo specificato nel costruttore utilizziamo una semplice aritmetica: 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;
}
}Implementazione di UnityEngine.Random.Range()
Questo metodo della classe statica UnityEngine.Random consente di specificare un intervallo di valori e restituisce un numero casuale di tipo float. Non è necessario eseguire ulteriori conversioni.
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);
}
}Implementazione di UnityEngine.Random.value
La proprietà value della classe statica UnityEngine.Random restituisce un numero casuale di tipo float da un intervallo fisso di valori [0; 1). Proietteremo questo intervallo sull'intervallo specificato nello stesso modo in cui abbiamo realizzato 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;
}
}Implementazione di Unity.Mathematics.Random.NextFloat()
Il metodo NextFloat() della classe Unity.Mathematics.Random restituisce un numero float e consente di impostare un intervallo di valori. L'unica peculiarità è che ogni istanza di Unity.Mathematics.Random deve essere inizializzata con un seed, in modo da evitare la generazione di sequenze ripetute.
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);
}
}Implementazione di MainController
Sono pronte diverse implementazioni di IRandomGenerator. Ora è necessario generare sequenze e salvare il dataset risultante per l'elaborazione. A tal fine, creeremo una scena in Unity e un piccolo script MainController, che effettuerà tutto il lavoro necessario e, nel contempo, gestirà l'interazione con l'interfaccia utente.
Imposteremo la dimensione del dataset e l'intervallo di valori casuali, oltre a dotarci di un metodo che restituisce un array di generatori configurati e pronti all'uso.
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)
};
}
...
}
}E ora formiamo il dataset. In questo caso, la generazione di dati sarà combinata con la registrazione dei risultati in un flusso di testo (in formato csv). A ciascun IRandomGenerator verrà assegnata una colonna separata, mentre la prima riga conterrà il Nome del generatore.
namespace RandomDistribution
{
public class MainController : MonoBehaviour
{
...
private void GenerateCsvDataSet(TextWriter writer, int dataSetSize, params IRandomGenerator[] generators)
{
const char separator = ',';
int lastIdx = generators.Length - 1;
// scrivere intestazione
for (int j = 0; j <= lastIdx; j++)
{
writer.Write(generators[j].Name);
if (j != lastIdx)
writer.Write(separator);
}
writer.WriteLine();
// scrivere dati
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();
}
}
...
}
}Rimane da chiamare il metodo GenerateCsvDataSet e salvare il risultato in un file, oppure trasmettere i dati direttamente attraverso la rete dal dispositivo finale a quello ricevente. 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();
}
}
...
}
}I sorgenti del progetto si trovano su .
Risultati
Non c'è stato alcun miracolo. Ciò che ci si aspettava è esattamente ciò che abbiamo ricevuto: in tutti i casi una distribuzione uniforme senza il minimo accenno a complotti. Non vedo senso nell'allegare grafici separati per le piattaforme: mostrano tutte risultati sostanzialmente simili.
La realtà è la seguente:
Visualizzazione delle sequenze sul piano da tutti e cinque i metodi di generazione:
E visualizzazione in 3D. Lascio solo il risultato di System.Random.Next(), per non creare una montagna di contenuti identici.
La storia raccontata nell'introduzione sulla distribuzione normale di UnityEngine.Random non si è ripetuta: o era errata fin dall'inizio, o qualcosa è cambiato nel motore da allora. Ma ora ne siamo certi.
Fonte: habr.com
