Nello sviluppo del gioco, spesso è necessario collegare qualcosa alla casualità: Unity ha il suo Random per questo, e parallelamente ad esso c'è System.Random. Una volta, in uno dei progetti, ho avuto l'impressione che entrambi potessero funzionare in modo diverso (anche se dovrebbero avere una distribuzione uniforme).
Quindi non sono entrati nei dettagli: è bastato che il passaggio a System.Random risolvesse tutti i problemi. Ora abbiamo deciso di esaminarlo più in dettaglio e di condurre una piccola ricerca: quanto sono “distorti” o prevedibili gli RNG e quale scegliere. Inoltre, ho sentito più di una volta opinioni contrastanti sulla loro "onestà": proviamo a capire come si confrontano i risultati reali con quelli dichiarati.
Il breve programma educativo o RNG è in realtà RNG
Se hai già familiarità con i generatori di numeri casuali, puoi passare immediatamente alla sezione "Test".
I numeri casuali (RN) sono una sequenza di numeri generati utilizzando un processo casuale (caotico), una fonte di entropia. Cioè, questa è una sequenza i cui elementi non sono interconnessi da alcuna legge matematica: non hanno alcuna relazione di causa-effetto.
Ciò che crea il numero casuale è chiamato generatore di numeri casuali (RNG). Sembrerebbe che tutto sia elementare, ma se passiamo dalla teoria alla pratica, in realtà non è così semplice implementare un algoritmo software per generare una tale sequenza.
La ragione risiede nell’assenza dello stesso caos nella moderna elettronica di consumo. Senza di esso, i numeri casuali cessano di essere casuali e il loro generatore si trasforma in una funzione ordinaria di argomenti ovviamente definiti. Per una serie di specialità nel campo IT questo è un problema serio (ad esempio la crittografia), ma per altre esiste una soluzione completamente accettabile.
È necessario scrivere un algoritmo che restituisca, anche se non numeri veramente casuali, ma il più vicino possibile ad essi: i cosiddetti numeri pseudo-casuali (PRN). L'algoritmo in questo caso è chiamato generatore di numeri pseudocasuali (PRNG).
Esistono diverse opzioni per creare un PRNG, ma le seguenti saranno rilevanti per tutti:
- La necessità di un'inizializzazione preliminare.
Il PRNG non ha alcuna fonte di entropia, quindi deve essere dotato di uno stato iniziale prima dell'uso. È specificato come numero (o vettore) ed è chiamato seme (seme casuale). Spesso, come seed viene utilizzato il contatore dell'orologio del processore o l'equivalente numerico dell'ora del sistema.
- 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 PRNG separato 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à. Molto spesso si tratta di una distribuzione normale o uniforme.
Distribuzione normale (a sinistra) e distribuzione uniforme (a destra)
Diciamo che abbiamo un dado equilibrato con 24 facce. Se lo lanci, la probabilità di ottenere un numero uno sarà pari a 1/24 (la stessa probabilità di ottenere qualsiasi altro numero). Se esegui molti lanci e registri i risultati, noterai che tutti i bordi cadono all'incirca con la stessa frequenza. In sostanza, questo dado può essere considerato un RNG con distribuzione uniforme.
Cosa succede se lanci 10 di questi dadi contemporaneamente e conti i punti totali? Verrà mantenuta l’uniformità? NO. Molto spesso, l'importo sarà vicino a 125 punti, ovvero a un valore medio. Di conseguenza, anche prima di effettuare un lancio, puoi stimare approssimativamente il risultato futuro.
Il motivo è che esiste il maggior numero di combinazioni per ottenere il punteggio medio. Quanto più ci si allontana, tanto minori saranno le combinazioni e, di conseguenza, minore sarà la probabilità di una perdita. Se questo dato viene visualizzato, assomiglierà vagamente alla forma di una campana. Pertanto, con un certo allungamento, un sistema di 10 dadi può essere chiamato RNG con una distribuzione normale.
Un altro esempio, solo che questa volta su un aereo: sparare a un bersaglio. Il tiratore sarà un RNG che genera una coppia di numeri (x, y) visualizzati sul grafico.
Concordo sul fatto che l'opzione a sinistra è più vicina alla vita reale: questo è un RNG con una distribuzione normale. Ma se hai bisogno di disperdere le stelle in un cielo buio, allora l'opzione giusta, ottenuta utilizzando RNG con una distribuzione uniforme, è più adatta. In generale, scegli un generatore in base al compito da svolgere.
Ora parliamo dell'entropia della sequenza PNG. 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 controllando la distribuzione.
Sembra quasi uniforme, ma se leggi una sequenza di due numeri e li interpreti come coordinate su un piano, ottieni questo:
I modelli diventano chiaramente visibili. E poiché i dati nella sequenza sono ordinati in un certo modo (cioè hanno una bassa entropia), ciò può dare origine a quella stessa “distorsione”. Come minimo, un PRNG di questo tipo non è molto adatto per 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 tutto vada bene qui, anche sull'aereo:
Diamo un'occhiata al volume (leggi tre numeri alla volta):
E ancora i modelli. Non è più possibile costruire una visualizzazione in quattro dimensioni. Ma possono esistere modelli in questa dimensione e in quelle più grandi.
Nella crittografia, dove ai PRNG vengono imposti i requisiti più severi, una situazione del genere è categoricamente inaccettabile. Pertanto, sono stati sviluppati algoritmi speciali per valutarne la qualità, di cui non parleremo ora. L’argomento è vasto e meriterebbe un articolo a parte.
Test
Se non sappiamo qualcosa con certezza, allora come lavorarci? Vale la pena attraversare la strada se non sai quale semaforo lo consente? Le conseguenze potrebbero essere diverse.
Lo stesso vale per la famigerata casualità in Unity. Va bene se la documentazione rivela i dettagli necessari, ma la storia menzionata all'inizio dell'articolo è avvenuta proprio a causa della mancanza delle specifiche desiderate.
E se non sai come funziona lo strumento, non sarai in grado di usarlo correttamente. In generale, è giunto il momento di verificare e condurre un esperimento per accertarsi finalmente almeno della distribuzione.
La soluzione era semplice ed efficace: raccogliere statistiche, ottenere dati oggettivi e osservare i risultati.
Materia di studio
Esistono diversi modi per generare numeri casuali in Unity: ne abbiamo testati cinque.
- System.Random.Next(). Genera numeri interi in un determinato intervallo di valori.
- System.Random.NextDouble(). Genera numeri a doppia precisione nell'intervallo da [0; 1).
- UnityEngine.Random.Range(). Genera numeri a precisione singola (float) in un determinato intervallo di valori.
- UnityEngine.Valore.casuale. Genera numeri a precisione singola (virgola mobile) nell'intervallo da [0; 1).
- Unity.Mathematics.Random.NextFloat(). Parte della nuova libreria Unity.Mathematics. Genera numeri a precisione singola (float) in un determinato intervallo di valori.
Quasi ovunque nella documentazione è stata specificata una distribuzione uniforme, ad eccezione di UnityEngine.Random.value (dove la distribuzione non è stata specificata, ma per analogia con UnityEngine.Random.Range() era prevista anche uniform) e Unity.Mathematics.Random .NextFloat() (dove in La base è l'algoritmo xorshift, il che significa che ancora una volta è necessario attendere una distribuzione uniforme).
Per impostazione predefinita, i risultati attesi sono stati presi come quelli specificati nella documentazione.
tecnica
Abbiamo scritto una piccola applicazione che generava sequenze di numeri casuali utilizzando ciascuno dei metodi presentati e salvava i risultati per un'ulteriore elaborazione.
La lunghezza di ciascuna sequenza è di 100 numeri.
L'intervallo di 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 ognuno di essi scriveremo una classe wrapper separata, che dovrebbe fornire:
- Possibilità di impostare il range di valori [min/max). Verrà impostato tramite il costruttore.
- Metodo che restituisce MF. Scegliamo float come tipo, poiché è più generale.
- Il nome del metodo di generazione per contrassegnare i risultati. Per comodità restituiremo come valore il nome completo della classe + il nome del metodo utilizzato per generare il MF.
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 impostare un intervallo di valori, ma restituisce numeri interi, ma sono necessari i float. Puoi semplicemente interpretare il numero intero come un float, oppure puoi espandere la gamma di valori di diversi ordini di grandezza, compensandoli con ogni generazione della gamma media. Il risultato sarà qualcosa di simile a un punto fisso con un dato ordine di precisione. Utilizzeremo questa opzione poiché è più vicina al valore float reale.
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, usiamo la 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 impostare un intervallo di valori e restituisce un tipo float. Non è necessario eseguire ulteriori trasformazioni.
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 tipo float da un intervallo fisso di valori [0; 1). Proiettiamolo su un determinato intervallo 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 punto mobile di tipo float e consente di specificare un intervallo di valori. L'unica sfumatura è che ogni istanza di Unity.Mathematics.Random dovrà essere inizializzata con un seme: in questo modo eviteremo di generare 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. Successivamente, è necessario generare sequenze e salvare il set di dati risultante per l'elaborazione. Per fare ciò, creeremo una scena e un piccolo script MainController in Unity, che farà tutto il lavoro necessario e allo stesso tempo sarà responsabile dell'interazione con l'interfaccia utente.
Impostiamo la dimensione del set di dati e l'intervallo di valori MF e otteniamo anche un metodo che restituisca un array di generatori configurati e pronti a funzionare.
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 creiamo un set di dati. In questo caso, la generazione dei dati sarà abbinata alla registrazione dei risultati in un flusso di testo (in formato csv). Per memorizzare i valori di ciascun IRandomGenerator, viene allocata una propria colonna separata e la prima riga contiene 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 richiamare il metodo GenerateCsvDataSet e salvare il risultato in un file oppure trasferire immediatamente i dati in 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 sono a .
Giudizio
Non è successo nessun miracolo. Ciò che si aspettavano è ciò che hanno ottenuto: in ogni caso, una distribuzione uniforme senza alcun accenno di cospirazione. Non vedo il motivo di inserire grafici separati per le piattaforme: mostrano tutti più o meno gli stessi risultati.
La realtà è questa:
Visualizzazione di sequenze su un piano da tutti e cinque i metodi di generazione:
E visualizzazione in 3D. Lascerò solo il risultato di System.Random.Next() per non produrre un mucchio di contenuti identici.
La storia raccontata nell'introduzione sulla normale distribuzione di UnityEngine.Random non si è ripetuta: o inizialmente era errata, oppure da allora qualcosa è cambiato nel motore. Ma ora ne siamo sicuri.
Fonte: habr.com