In der Spieleentwicklung muss oft etwas zufällig generiert werden: Unity hat dafür seinen eigenen Random-Generator, daneben existiert System.Random. Vor langer Zeit hatte ich in einem Projekt den Eindruck, dass beide unterschiedlich arbeiten können (obwohl sie eine gleichmäßige Verteilung haben sollten).
Damals sind wir nicht ins Detail gegangen — es reichte, dass der Übergang zu System.Random alle Probleme behoben hat. Jetzt haben wir beschlossen, genauer zu untersuchen und eine kleine Studie durchzuführen: Wie 'voreingenommen' oder vorhersagbar sind Zufallszahlengeneratoren, und welchen sollte man wählen. Zumal ich mehrfach widersprüchliche Meinungen über ihre 'Ehrlichkeit' gehört habe — lassen Sie uns herausfinden, wie die tatsächlichen Ergebnisse mit den angegebenen zusammenhängen.
Eine kurze Einführung oder Was sind Zufallszahlengeneratoren eigentlich?
Wenn Sie bereits mit Zufallszahlengeneratoren vertraut sind, können Sie direkt zum Abschnitt „Testen“ übergehen.
Zufallszahlen (ZÜ) sind eine Folge von Zahlen, die durch einen bestimmten zufälligen (chaotischen) Prozess oder eine Entropiequelle erzeugt werden. Das bedeutet, dass diese Folge von Elementen nicht durch irgendein mathematisches Gesetz miteinander verbunden ist – ihnen fehlt die kausale Beziehung.
Was ZÜ erstellt, nennt man einen Zufallszahlengenerator (ZÜG). Es scheint alles ganz einfach zu sein, aber wenn man von der Theorie zur Praxis übergeht, stellt man fest, dass es in der Tat nicht so einfach ist, einen Programmalgorithmus zur Generierung einer solchen Folge zu implementieren.
Der Grund liegt im Fehlen dieser Chaotizität in der modernen Verbraucher-Elektronik. Ohne sie hören Zufallszahlen auf, zufällig zu sein, und ihr Generator wird zu einer gewöhnlichen Funktion, die von zuvor festgelegten Argumenten abhängt. Für eine Reihe von Spezialgebieten in der IT-Branche ist das ein ernstes Problem (zum Beispiel für die Kryptographie), für die anderen gibt es jedoch eine durchaus akzeptable Lösung.
Es ist notwendig, einen Algorithmus zu schreiben, der zwar keine wirklich zufälligen Zahlen zurückgibt, aber diesen so nahe wie möglich kommt — sogenannte Pseudozufallszahlen (PZ). Der Algorithmus wird in diesem Fall als Pseudozufallszahlengenerator (PZGenerator) bezeichnet.
Es gibt mehrere Möglichkeiten zur Erstellung eines PZGenerators, aber für alle gilt Folgendes:
- Die Notwendigkeit einer vorherigen Initialisierung.
Der PZGenerator hat keine Entropiequelle, daher muss ihm vor der Verwendung ein Anfangszustand angegeben werden. Dieser wird als Zahl (oder Vektor) festgelegt und als Saat (Seed, random seed) bezeichnet. Häufig wird als Seed ein Zähler der Prozessorzyklen oder der numerische Äquivalent der Systemzeit verwendet.
- Reproduzierbarkeit der Folge.
Der PZGenerator ist vollständig deterministisch, daher bestimmt der bei der Initialisierung festgelegte Seed eindeutig die gesamte zukünftige Zahlenfolge. Das bedeutet, dass ein einzelner PZGenerator, der mit dem gleichen Seed (zu unterschiedlichen Zeiten, in verschiedenen Programmen, auf verschiedenen Geräten) initialisiert wurde, die gleiche Folge erzeugt.
Es ist auch wichtig, die Eigenschaften der Zufallszahlengeneratoren zu kennen — welche Zahlen sie generieren und mit welcher Wahrscheinlichkeit. Am häufigsten handelt es sich dabei um eine Normalverteilung oder eine Gleichverteilung.
Normalverteilung (links) und Gleichverteilung (rechts)
Angenommen, wir haben einen fairen Würfel mit 24 Seiten. Wenn wir ihn werfen, beträgt die Wahrscheinlichkeit, dass eine Eins fällt, 1/24 (genauso wie die Wahrscheinlichkeit, dass jede andere Zahl fällt). Wenn wir viele Würfe durchführen und die Ergebnisse aufzeichnen, wird man feststellen, dass alle Seiten ungefähr mit der gleichen Häufigkeit erscheinen. Im Grunde genommen kann dieser Würfel als Zufallszahlengenerator mit einer Gleichverteilung betrachtet werden.
Aber was passiert, wenn wir gleichzeitig 10 solche Würfel werfen und die Gesamtsumme der Punkte zählen? Wird die Gleichverteilung erhalten bleiben? Nein. Häufig wird die Summe nahe bei 125 Punkten liegen, also bei einem gewissen Mittelwert. Und folglich — schon bevor wir den Wurf machen, können wir das zukünftige Ergebnis ungefähr abschätzen.
Der Grund dafür ist, dass es die meisten Kombinationen gibt, um die durchschnittliche Punktzahl zu erreichen. Je weiter man sich davon entfernt, desto weniger Kombinationen gibt es — und damit sinkt die Wahrscheinlichkeit. Wenn man diese Daten visualisiert, ähneln sie in etwa einer Glockenform. Daher kann man das System mit 10 Würfeln mit etwas Vorbehalt als einen Zufallszahlengenerator mit normaler Verteilung bezeichnen.
Ein weiteres Beispiel, diesmal in der Ebene — das Schießen auf ein Ziel. Der Schütze wird der Zufallszahlengenerator sein, der ein Paar von Zahlen (x, y) erzeugt, das in einem Diagramm angezeigt wird.
Sie werden zustimmen, dass die linke Variante näher an der Realität liegt — das ist ein Zufallszahlengenerator mit normaler Verteilung. Wenn es jedoch darum geht, Sterne am dunklen Himmel zu verteilen, ist die rechte Variante, die mit Hilfe eines Zufallszahlengenerators mit gleichmäßiger Verteilung erzeugt wurde, besser geeignet. Kurz gesagt, wählen Sie den Generator je nach Aufgabe aus.
Jetzt sprechen wir über die Entropie einer Folge von Pseudo-Zufallszahlen. Zum Beispiel gibt es eine Folge, die so beginnt:
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, …
Wie zufällig erscheinen diese Zahlen auf den ersten Blick? Lassen Sie uns mit der Überprüfung der Verteilung beginnen.
Es sieht fast gleichmäßig aus, aber wenn wir die Sequenz in Paare von zwei Zahlen einteilen und sie als Koordinaten auf einer Ebene interpretieren, erhalten wir das:
Muster werden deutlich sichtbar. Und da die Daten in der Sequenz auf eine bestimmte Weise angeordnet sind (das heißt, sie besitzen eine niedrige Entropie), kann das zu der genannten „Voreingenommenheit“ führen. Zumindest ist ein solcher PRNG nicht besonders geeignet, um Koordinaten auf einer Ebene zu generieren.
Eine andere Sequenz:
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, …
Es scheint hier auch auf der Ebene gut auszusehen:
Lassen Sie uns in den Raum schauen (wir lesen in Dreiergruppen):
Und wieder Muster. Eine Visualisierung in vier Dimensionen ist bereits nicht möglich. Aber Muster können auch in dieser Dimension und in höheren Dimensionen existieren.
In der gleichen Kryptografie, in der an die PRNGs die höchsten Anforderungen gestellt werden, ist eine solche Situation absolut nicht akzeptabel. Daher wurden spezielle Algorithmen zur Bewertung ihrer Qualität entwickelt, auf die wir jetzt nicht eingehen werden. Das Thema ist umfangreich und verdient einen eigenen Artikel.
Testen
Wenn wir etwas nicht sicher wissen, wie können wir dann damit umgehen? Sollte man die Straße überqueren, wenn man nicht weiß, welches Signal das erlaubt? Die Konsequenzen können unterschiedlich sein.
Dasselbe gilt für den berüchtigten Zufall in Unity. Es ist gut, wenn die Dokumentation die notwendigen Details preisgibt, aber die eingangs erwähnte Geschichte ist genau aufgrund des Mangels an gewollter Konkretheit entstanden.
Ohne zu wissen, wie das Werkzeug funktioniert, kannst du es nicht korrekt anwenden. Im Allgemeinen ist es an der Zeit, zu prüfen und ein Experiment durchzuführen, um zumindest in Bezug auf die Verteilung endgültig überzeugt zu sein.
Die Lösung war einfach und effektiv: Daten zu sammeln, objektive Informationen zu erhalten und die Ergebnisse anzusehen.
Gegenstand der Forschung
In Unity gibt es mehrere Möglichkeiten zur Generierung von Zufallszahlen – wir haben fünf getestet.
- System.Random.Next(). Generiert ganze Zahlen (Integer) innerhalb eines definierten Wertebereichs.
- System.Random.NextDouble(). Generiert Fließkommazahlen doppelt präzise (Double) im Bereich von [0; 1).
- UnityEngine.Random.Range(). Generiert Fließkommazahlen einfach präzise (Float) innerhalb eines definierten Wertebereichs.
- UnityEngine.Random.value. Generiert Fließkommazahlen einfach präzise (Float) im Bereich von [0; 1).
- Unity.Mathematics.Random.NextFloat(). Teil der neuen Bibliothek Unity.Mathematics. Generiert Fließkommazahlen einfach präzise (Float) innerhalb eines definierten Wertebereichs.
In der Dokumentation wurde fast überall eine gleichmäßige Verteilung angegeben, außer bei UnityEngine.Random.value (wo die Verteilung nicht angegeben ist, aber im Vergleich zu UnityEngine.Random.Range() ebenfalls eine gleichmäßige Verteilung erwartet wurde) und bei Unity.Mathematics.Random.NextFloat() (wo ein xorshift-Algorithmus zugrunde liegt und somit erneut eine gleichmäßige Verteilung zu erwarten ist).
Standardmäßig wurden die erwarteten Ergebnisse, die in der Dokumentation angegeben sind, zugrunde gelegt.
Methodik
Wir haben eine kleine Anwendung geschrieben, die Sequenzen zufälliger Zahlen mit jeder der vorgestellten Methoden generierte und die Ergebnisse zur weiteren Verarbeitung speicherte.
Die Länge jeder Sequenz beträgt 100.000 Zahlen.
Der Wertebereich der zufälligen Zahlen ist [0, 100).
Die Daten wurden von mehreren Zielplattformen gesammelt:
- Windows
— Unity v2018.3.14f1, Editor-Modus, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, Editor-Modus, Mono, .NET Standard 2.0
— Unity v5.6.4p4, Editor-Modus, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, Build für Gerät, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, Build für Gerät, il2cpp, .NET Standard 2.0
Implementierung
Wir haben mehrere verschiedene Methoden zur Generierung von Zufallszahlen. Für jede davon erstellen wir eine eigene Wrapper-Klasse, die Folgendes bereitstellen soll:
- Die Möglichkeit, einen Wertebereich [min/max) festzulegen. Dies geschieht über den Konstruktor.
- Eine Methode, die die Zufallszahl zurückgibt. Als Typ wählen wir float, da er allgemeiner ist.
- Die Bezeichnung der Generierungsmethode zur Kennzeichnung der Ergebnisse. Zur Vereinfachung geben wir den vollständigen Klassennamen + den Namen der Methode zurück, die zur Generierung der Zufallszahl verwendet wird.
Zuerst deklarieren wir die Abstraktion, die über das Interface IRandomGenerator dargestellt wird:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementierung von System.Random.Next()
Diese Methode ermöglicht die Festlegung eines Wertebereichs, gibt jedoch ganze Zahlen (integer) zurück, während float benötigt wird. Man kann integer einfach als float interpretieren oder den Wertebereich um mehrere Größenordnungen erweitern und diese bei jeder Generierung von Zufallszahlen kompensieren. Es wird etwas wie fixed-point mit definierter Genauigkeit entstehen. Wir werden diese Variante verwenden, da sie näher an einem tatsächlichen float-Wert liegt.
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;
}
}Implementierung von System.Random.NextDouble()
Hier ist der feste Wertebereich [0; 1). Um ihn auf den im Konstruktor festgelegten Bereich zu projizieren, verwenden wir einfache Arithmetik: 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;
}
}Implementierung von UnityEngine.Random.Range()
Diese Methode der statischen Klasse UnityEngine.Random ermöglicht es, einen Wertebereich festzulegen und gibt eine float-Zahl zurück. Es sind keine zusätzlichen Umwandlungen erforderlich.
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);
}
}Implementierung von UnityEngine.Random.value
Die Eigenschaft value der statischen Klasse UnityEngine.Random gibt eine float-Zahl aus einem festen Wertebereich [0; 1) zurück. Wir projizieren sie auf den angegebenen Bereich auf die gleiche Weise wie bei der Implementierung von 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;
}
}Implementierung von Unity.Mathematics.Random.NextFloat()
Die Methode NextFloat() der Klasse Unity.Mathematics.Random gibt einen float-Typ zurück und ermöglicht es, einen Wertebereich festzulegen. Das Besondere daran ist, dass jede Instanz von Unity.Mathematics.Random mit einem bestimmten Seed initialisiert werden muss — so vermeiden wir die Generierung von sich wiederholenden Sequenzen.
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);
}
}Implementierung des MainControllers
Einige Implementierungen von IRandomGenerator sind bereit. Jetzt müssen wir Sequenzen generieren und das resultierende Dataset zur Verarbeitung speichern. Dazu erstellen wir in Unity eine Szene und ein kleines Skript namens MainController, das die gesamte erforderliche Arbeit ausführt und gleichzeitig für die Interaktion mit der Benutzeroberfläche verantwortlich ist.
Legen wir die Größe des Datensatzes und den Wertebereich für die Zufallszahlen fest und fügen wir eine Methode hinzu, die ein Array von konfigurierten und einsatzbereiten Generatoren zurückgibt.
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)
};
}
...
}
}Jetzt erstellen wir das Dataset. In diesem Fall wird die Datengenerierung mit dem Schreiben der Ergebnisse in einen Textstream (im CSV-Format) kombiniert. Jede IRandomGenerator-Instanz erhält ihre eigene separate Spalte, während die erste Zeile den Namen des Generators enthält.
namespace RandomDistribution
{
public class MainController : MonoBehaviour
{
...
private void GenerateCsvDataSet(TextWriter writer, int dataSetSize, params IRandomGenerator[] generators)
{
const char separator = ',';
int lastIdx = generators.Length - 1;
// Header schreiben
for (int j = 0; j <= lastIdx; j++)
{
writer.Write(generators[j].Name);
if (j != lastIdx)
writer.Write(separator);
}
writer.WriteLine();
// Daten schreiben
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();
}
}
...
}
}Es bleibt nur noch, die Methode GenerateCsvDataSet aufzurufen und das Ergebnis in einer Datei zu speichern oder die Daten sofort über das Netzwerk vom Endgerät an den Empfänger zu übertragen. der 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();
}
}
...
}
}Die Quellcodes des Projekts liegen unter .
Ergebnisse
Ein Wunder ist nicht geschehen. Was man erwartete, bekam man — in allen Fällen eine gleichmäßige Verteilung ohne einen Hauch von Verschwörung. Ich sehe keinen Sinn darin, die einzelnen Grafiken nach Plattformen beizufügen — sie zeigen alle ungefähr die gleichen Ergebnisse.
Die Realität ist wie folgt:
Visualisierung der Sequenzen auf der Ebene aus allen fünf Generierungsarten:
Und die Visualisierung in 3D. Ich lasse nur das Ergebnis von System.Random.Next() übrig, um keinen Haufen identischen Inhalts zu erzeugen.
Die im Einleitung erzählte Geschichte über die Normalverteilung von UnityEngine.Random hat sich nicht wiederholt: entweder war sie ursprünglich fehlerhaft oder seitdem hat sich etwas in der Engine geändert. Aber jetzt sind wir sicher.
Quelle: habr.com
