Nello sviluppo di videogiochi, spesso è necessario fare affidamento sulla casualità: Unity ha il suo Random per questo scopo, e System.Random esiste parallelamente. Molto tempo fa, in un progetto, ho avuto l'impressione che i due potessero funzionare in modo diverso (anche se dovrebbero avere una distribuzione uniforme).
All'epoca non siamo entrati nei dettagli: ci è bastato dire che il passaggio a System.Random ha risolto tutti i problemi. Ora abbiamo deciso di approfondire l'argomento e condurre un piccolo studio: quanto sono "di parte" o prevedibili gli RNG e quale scegliere. Inoltre, ho sentito più di una volta opinioni contrastanti sulla loro "equità": proviamo a capire come i risultati effettivi si confrontano con le affermazioni.
Una breve introduzione all'RNG (Realtà Random Number), o è davvero un RNG?
Se hai già familiarità con i generatori di numeri casuali, puoi passare direttamente alla sezione "Test".
I numeri casuali (RN) sono una sequenza di numeri generata da un processo casuale (caotico), fonte di entropia. In altre parole, si tratta di una sequenza i cui elementi non sono correlati tra loro da alcuna legge matematica: non hanno alcuna relazione di causa-effetto.
Ciò che crea il generatore di numeri casuali (RNG) è chiamato generatore di numeri casuali (RNG). Sebbene possa sembrare semplice, mettere in pratica la teoria rivela che implementare un algoritmo software per generare una tale sequenza non è così immediato.
La ragione risiede nell'assenza di questa stessa casualità nell'elettronica di consumo moderna. Senza di essa, i numeri casuali cessano di essere casuali e il loro generatore si trasforma in una semplice funzione di input predeterminati. Per diverse professioni informatiche (ad esempio, la crittografia), questo rappresenta un problema serio, ma per altre esiste una soluzione perfettamente accettabile.
Dobbiamo scrivere un algoritmo che restituisca numeri che non siano realmente casuali, ma che siano il più possibile vicini a essi: i cosiddetti numeri pseudo-casuali (PRNG). L'algoritmo in questo caso è chiamato generatore di numeri pseudo-casuali (PRNG).
Esistono diverse opzioni per creare un PRNG, ma le seguenti sono valide per tutte:
- Necessità di pre-inizializzazione.
Un PRNG non ha una sorgente di entropia, quindi è necessario specificare uno stato iniziale prima dell'uso. Questo stato iniziale è specificato come un numero (o vettore) ed è chiamato seed (seme casuale). Il contatore dei cicli del processore o l'equivalente numerico del tempo di sistema viene spesso utilizzato come seed.
- Riproducibilità della sequenza.
Il PRNG è completamente deterministico, quindi il seme specificato durante l'inizializzazione determina in modo univoco l'intera sequenza futura di numeri. Ciò significa che un singolo PRNG inizializzato con lo stesso seme (in momenti diversi, in programmi diversi, su dispositivi diversi) genererà la stessa sequenza.
È inoltre necessario conoscere la distribuzione di probabilità che caratterizza il PRNG: quali numeri genererà e con quale probabilità. Nella maggior parte dei casi, si tratta di una distribuzione normale o uniforme.
Distribuzione normale (sinistra) e distribuzione uniforme (destra)
Supponiamo di avere un dado a 24 facce. Se lo lanciamo, la probabilità che esca un 1 è 1/24 (proprio come la probabilità che esca qualsiasi altro numero). Se effettuiamo molti lanci e registriamo i risultati, noteremo che tutti i dadi a 24 facce escono all'incirca con la stessa frequenza. In sostanza, questo dado può essere considerato un generatore di numeri casuali uniformemente distribuito.
Cosa succede se si lanciano 10 dadi contemporaneamente e si calcola il punteggio totale? Rimarrà uniforme? No. Il più delle volte, il punteggio sarà vicino a 125 punti, ovvero un valore medio. Di conseguenza, è possibile stimare approssimativamente il risultato futuro anche prima di tirare.
Il motivo è che esiste il maggior numero di combinazioni per raggiungere il punteggio medio. Più ci si allontana dalla media, meno combinazioni ci sono e, di conseguenza, minore è la probabilità di un lancio. Se questi dati fossero visualizzati, assomiglierebbero vagamente a una forma a campana. Pertanto, con un certo margine di errore, un sistema di 10 dadi potrebbe essere definito un RNG a distribuzione normale.
Un altro esempio, questa volta su un aereo, è sparare a un bersaglio. Il tiratore è un generatore di numeri casuali (RNG), che genera una coppia di numeri (x, y), che viene visualizzata su un grafico.
Concorderete sul fatto che la variante di sinistra sia più vicina alla realtà: si tratta di un generatore di numeri casuali con distribuzione normale. Ma se dovete distribuire le stelle in un cielo buio, la variante di destra, ottenuta utilizzando un generatore di numeri casuali con distribuzione uniforme, sarebbe più adatta. In breve, scegliete un generatore in base al compito da svolgere.
Ora parliamo dell'entropia di una sequenza di numeri casuali. Ad esempio, c'è 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 verificarne la distribuzione.
Sembra quasi uniforme, ma se leggi la sequenza di due numeri e li interpreti come coordinate su un piano, ottieni questo:
I pattern diventano chiaramente visibili. E poiché i dati nella sequenza sono ordinati in un certo modo (ovvero, hanno bassa entropia), questo può generare la stessa "distorsione". Come minimo, un PRNG di questo tipo non è molto adatto a generare coordinate su un 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, …
Sembra che qui vada tutto bene, anche sulla superficie piana:
Diamo un'occhiata al volume (leggi tre numeri):
E ancora, schemi. Visualizzare in quattro dimensioni non è più possibile. Ma gli schemi possono esistere in questa dimensione e in quelle superiori.
In crittografia, dove i PRNG sono soggetti ai requisiti più severi, una situazione del genere è assolutamente inaccettabile. Pertanto, sono stati sviluppati algoritmi speciali per valutarne la qualità, che non approfondiremo in questa sede. L'argomento è vasto e meriterebbe un articolo a parte.
Test
Se non sappiamo qualcosa con certezza, come possiamo gestirla? Dovremmo attraversare la strada se non sappiamo quale semaforo lo consente? Le conseguenze possono variare.
Lo stesso vale per la famigerata casualità di Unity. È fantastico quando la documentazione fornisce i dettagli necessari, ma l'incidente menzionato all'inizio dell'articolo è avvenuto proprio a causa della mancanza di specificità desiderata.
E senza sapere come funziona lo strumento, non è possibile utilizzarlo correttamente. Quindi, è il momento di testarlo e condurre un esperimento per esserne finalmente certi, almeno per quanto riguarda la distribuzione.
La soluzione era semplice ed efficace: raccogliere statistiche, ottenere dati oggettivi e osservare i risultati.
Oggetto della ricerca
Esistono diversi modi per generare numeri casuali in Unity: ne abbiamo testati cinque.
- System.Random.Next(). Genera numeri interi all'interno di un intervallo di valori specificato.
- System.Random.NextDouble(). Genera numeri a doppia precisione nell'intervallo [0; 1).
- UnityEngine.Random.Range(). Genera numeri a precisione singola (virgole) all'interno di 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 float a precisione singola all'interno di un intervallo specificato.
Quasi ovunque nella documentazione è stata specificata una distribuzione uniforme, ad eccezione di UnityEngine.Random.value (dove la distribuzione non è specificata, ma per analogia con UnityEngine.Random.Range(), era prevista anche una distribuzione uniforme) e Unity.Mathematics.Random.NextFloat() (che si basa sull'algoritmo xorshift, il che significa che è prevista nuovamente una distribuzione uniforme).
Di default, i risultati attesi erano quelli specificati nella documentazione.
tecnica
Abbiamo scritto una piccola applicazione che generava sequenze di numeri casuali utilizzando ciascuno dei metodi presentati e memorizzava i risultati per un'ulteriore elaborazione.
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 del dispositivo, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, build del dispositivo, il2cpp, .NET Standard 2.0
implementazione
Abbiamo diversi modi per generare numeri casuali. Per ognuno di essi, scriveremo una classe wrapper separata che dovrebbe fornire:
- Possibilità di specificare un intervallo di valori [min/max]. Verrà impostato tramite il costruttore.
- Un metodo che restituisce un numero. Sceglieremo float come tipo, perché è più generale.
- Nome del metodo di generazione per l'etichettatura dei risultati. Per comodità, restituiremo il nome completo della classe + il nome del metodo utilizzato per generare l'SC come valore.
Per prima cosa, dichiariamo un'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, mentre sono richiesti valori float. È possibile interpretare semplicemente l'intero come un float, oppure espandere l'intervallo di valori di diversi ordini di grandezza, compensandoli ogni volta che viene generata la frequenza. Questo si tradurrà in qualcosa di simile a un valore a virgola fissa con un ordine di precisione specificato. Useremo questa opzione, poiché è più vicina a un 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 l'intervallo di valori fisso è [0; 1). Per proiettarlo su quello 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 sono necessarie conversioni aggiuntive.
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]. Lo proiettiamo sull'intervallo specificato nello stesso modo in cui implementiamo 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 casuale float e consente di specificare un intervallo di valori. L'unica avvertenza è che ogni istanza di Unity.Mathematics.Random deve essere inizializzata con un seed, per evitare la generazione di sequenze duplicate.
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 del MainController
Sono disponibili diverse implementazioni di IRandomGenerator. Successivamente, dobbiamo generare sequenze e salvare il set di dati risultante per l'elaborazione. Per fare ciò, creeremo una scena in Unity e un piccolo script MainController che eseguirà tutto il lavoro necessario e gestirà l'interazione con l'interfaccia utente.
Definiremo la dimensione del set di dati e l'intervallo di valori di frequenza, e creeremo anche 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)
};
}
...
}
}Ora creeremo il dataset. In questo caso, la generazione dei dati sarà combinata con la scrittura dei risultati in un flusso di testo (in formato CSV). Ogni IRandomGenerator avrà una propria colonna e 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;
// 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();
}
}
...
}
}Non resta che chiamare il metodo GenerateCsvDataSet e salvare il risultato in un file oppure trasferire immediatamente i dati tramite la rete dal dispositivo finale al server ricevente.
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();
}
}
...
}
}Le fonti del progetto si trovano a .
Giudizio
Non c'è stato nessun miracolo. Abbiamo ottenuto ciò che ci aspettavamo: una distribuzione uniforme in tutti i casi, senza alcun accenno di cospirazione. Non vedo il motivo di allegare grafici di piattaforme separati: mostrano tutti più o meno gli stessi risultati.
La realtà è questa:
Visualizzazione delle sequenze su un piano da tutti e cinque i metodi di generazione:
E visualizzazione 3D. Lascerò solo il risultato di System.Random.Next() per evitare di generare un sacco di contenuti identici.
La storia raccontata nell'introduzione sulla distribuzione normale di UnityEngine.Random non si è ripetuta: o era difettosa fin dall'inizio, o qualcosa nel motore è cambiato da allora. Ma ora siamo fiduciosi.
Fonte: habr.com
