Bij de ontwikkeling van games moet je vaak iets met willekeur verbinden: Unity heeft hiervoor zijn eigen Random, en parallel daaraan is er System.Random. Er was eens, bij een van de projecten, de indruk dat beide anders konden werken (hoewel ze een gelijkmatige verdeling zouden moeten hebben).
Vervolgens gingen ze niet in op details - het was voldoende dat de overgang naar System.Random alle problemen corrigeerde. Nu hebben we besloten er dieper op in te gaan en wat onderzoek te doen: hoe ‘bevooroordeeld’ of voorspelbaar RNG’s zijn, en welke we moeten kiezen. Bovendien heb ik meer dan eens tegenstrijdige meningen gehoord over hun "eerlijkheid" - laten we proberen erachter te komen hoe de echte resultaten zich verhouden tot de verklaarde resultaten.
Kort educatief programma of RNG is eigenlijk RNG
Als u al bekend bent met generatoren van willekeurige getallen, kunt u meteen doorgaan naar het gedeelte 'Testen'.
Willekeurige getallen (RN) zijn een reeks getallen die worden gegenereerd met behulp van een willekeurig (chaotisch) proces, een bron van entropie. Dat wil zeggen, dit is een reeks waarvan de elementen niet met elkaar verbonden zijn door enige wiskundige wet - ze hebben geen oorzaak-en-gevolg-relatie.
Wat het willekeurige getal creëert, wordt een willekeurige nummergenerator (RNG) genoemd. Het lijkt erop dat alles elementair is, maar als we van theorie naar praktijk gaan, is het in feite niet zo eenvoudig om een software-algoritme te implementeren voor het genereren van een dergelijke reeks.
De reden ligt in het ontbreken van diezelfde chaos in de moderne consumentenelektronica. Zonder dit zijn willekeurige getallen niet langer willekeurig en verandert hun generator in een gewone functie van duidelijk gedefinieerde argumenten. Voor een aantal specialismen op IT-gebied is dit een serieus probleem (bijvoorbeeld cryptografie), maar voor anderen is er een volkomen acceptabele oplossing.
Het is noodzakelijk om een algoritme te schrijven dat, zij het niet echt willekeurige getallen, maar zo dicht mogelijk bij deze getallen terugkeert: de zogenaamde pseudo-willekeurige getallen (PRN). Het algoritme wordt in dit geval een pseudorandom number generator (PRNG) genoemd.
Er zijn verschillende opties voor het maken van een PRNG, maar het volgende is voor iedereen relevant:
- De noodzaak van voorlopige initialisatie.
De PRNG heeft geen bron van entropie, dus moet deze vóór gebruik een initiële toestand krijgen. Het wordt gespecificeerd als een getal (of vector) en wordt een zaadje (willekeurig zaadje) genoemd. Vaak wordt de processorklokteller of het numerieke equivalent van de systeemtijd als kiem gebruikt.
- Reproduceerbaarheid van de sequentie.
De PRNG is volledig deterministisch, dus het tijdens de initialisatie gespecificeerde zaad bepaalt op unieke wijze de gehele toekomstige reeks getallen. Dit betekent dat een afzonderlijke PRNG die met hetzelfde zaad is geïnitialiseerd (op verschillende tijdstippen, in verschillende programma's, op verschillende apparaten) dezelfde reeks zal genereren.
Je moet ook de waarschijnlijkheidsverdeling kennen die de PRNG karakteriseert: welke getallen het zal genereren en met welke waarschijnlijkheid. Meestal is dit een normale verdeling of een uniforme verdeling.
Normale verdeling (links) en uniforme verdeling (rechts)
Laten we zeggen dat we een eerlijke dobbelsteen hebben met 24 zijden. Als je ermee gooit, is de kans dat je een één krijgt gelijk aan 1/24 (hetzelfde als de kans dat je een ander getal krijgt). Als je veel worpen maakt en de resultaten noteert, zul je merken dat alle randen met ongeveer dezelfde frequentie eruit vallen. In wezen kan deze dobbelsteen worden beschouwd als een RNG met een uniforme verdeling.
Wat als je 10 van deze dobbelstenen tegelijk gooit en het totaal aantal punten telt? Zal er uniformiteit in stand worden gehouden? Nee. Meestal zal het bedrag bijna 125 punten bedragen, dat wil zeggen een gemiddelde waarde. En daardoor kunt u, zelfs voordat u een worp maakt, het toekomstige resultaat grofweg inschatten.
De reden is dat er het grootste aantal combinaties zijn om de gemiddelde score te behalen. Hoe verder er vandaan, hoe minder combinaties - en dus hoe kleiner de kans op verlies. Als deze gegevens worden gevisualiseerd, zullen deze vaag lijken op de vorm van een bel. Daarom kan een systeem van 10 dobbelstenen met enige rek een RNG met een normale verdeling worden genoemd.
Nog een voorbeeld, alleen deze keer in een vliegtuig: schieten op een doel. De shooter zal een RNG zijn die een paar getallen (x, y) genereert die in de grafiek worden weergegeven.
Mee eens dat de optie aan de linkerkant dichter bij het echte leven ligt - dit is een RNG met een normale distributie. Maar als je sterren aan een donkere hemel moet verspreiden, dan is de juiste optie, verkregen met behulp van RNG met een uniforme verdeling, beter geschikt. Kies over het algemeen een generator, afhankelijk van de taak die moet worden uitgevoerd.
Laten we het nu hebben over de entropie van de PNG-reeks. Er is bijvoorbeeld een reeks die als volgt begint:
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, ...
Hoe willekeurig zijn deze cijfers op het eerste gezicht? Laten we beginnen met het controleren van de distributie.
Het lijkt bijna uniform, maar als je een reeks van twee getallen leest en deze interpreteert als coördinaten in een vlak, krijg je dit:
Patronen worden duidelijk zichtbaar. En aangezien de gegevens in de reeks op een bepaalde manier zijn geordend (dat wil zeggen, ze hebben een lage entropie), kan dit aanleiding geven tot juist die ‘bias’. Op zijn minst is een dergelijke PRNG niet erg geschikt voor het genereren van coördinaten in een vlak.
Nog een reeks:
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, ...
Alles lijkt hier in orde te zijn, zelfs in het vliegtuig:
Laten we eens in volume kijken (lees drie cijfers tegelijk):
En nogmaals de patronen. Het is niet langer mogelijk om een visualisatie in vier dimensies te construeren. Maar er kunnen patronen bestaan op deze dimensie en op grotere dimensies.
In de cryptografie, waar de strengste eisen aan PRNG's worden gesteld, is een dergelijke situatie categorisch onaanvaardbaar. Daarom zijn er speciale algoritmen ontwikkeld om de kwaliteit ervan te beoordelen, waar we nu niet op ingaan. Het onderwerp is omvangrijk en verdient een apart artikel.
Testen
Als we iets niet zeker weten, hoe kunnen we er dan mee werken? Is het de moeite waard om de weg over te steken als je niet weet welk verkeerslicht dit toestaat? De gevolgen kunnen verschillend zijn.
Hetzelfde geldt voor de beruchte willekeur in Unity. Het is goed als de documentatie de nodige details onthult, maar het verhaal dat aan het begin van het artikel wordt genoemd, gebeurde juist vanwege het ontbreken van de gewenste details.
En als u niet weet hoe de tool werkt, kunt u deze niet correct gebruiken. Over het algemeen is het tijd om een experiment te controleren en uit te voeren om eindelijk zeker te zijn van de verdeling.
De oplossing was eenvoudig en effectief: verzamel statistieken, verkrijg objectieve gegevens en bekijk de resultaten.
Onderwerp van studie
Er zijn verschillende manieren om willekeurige getallen te genereren in Unity - we hebben er vijf getest.
- Systeem.Random.Next(). Genereert gehele getallen in een bepaald bereik van waarden.
- Systeem.Random.NextDouble(). Genereert getallen met dubbele precisie in het bereik van [0; 1).
- UnityEngine.Random.Range(). Genereert enkele precisiegetallen (floats) binnen een bepaald bereik van waarden.
- UnityEngine.Random.waarde. Genereert enkele precisiegetallen (floats) in het bereik van [0; 1).
- Unity.Wiskunde.Random.NextFloat(). Onderdeel van de nieuwe Unity.Mathematics-bibliotheek. Genereert enkele precisiegetallen (floats) binnen een bepaald bereik van waarden.
Vrijwel overal in de documentatie werd een uniforme distributie gespecificeerd, met uitzondering van UnityEngine.Random.value (waar de distributie niet gespecificeerd was, maar naar analogie met UnityEngine.Random.Range() ook uniform verwacht werd) en Unity.Mathematics.Random .NextFloat() (waarin De basis het xorshift-algoritme is, wat betekent dat je opnieuw moet wachten op een uniforme verdeling).
Standaard werden de verwachte resultaten genomen zoals gespecificeerd in de documentatie.
techniek
We hebben een kleine applicatie geschreven die reeksen willekeurige getallen genereerde met behulp van elk van de gepresenteerde methoden en de resultaten opsloegen voor verdere verwerking.
De lengte van elke reeks is 100 nummers.
Het bereik van willekeurige getallen is [0, 100).
Er zijn gegevens verzameld van verschillende doelplatforms:
- Dakramen en raamkozijnen
— 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 per apparaat, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, build per apparaat, il2cpp, .NET Standard 2.0
uitvoering
We hebben verschillende manieren om willekeurige getallen te genereren. Voor elk van hen zullen we een afzonderlijke wrapper-klasse schrijven, die het volgende zou moeten bieden:
- Mogelijkheid om het bereik van waarden in te stellen [min/max). Wordt ingesteld via de constructor.
- Methode die MF retourneert. Laten we float als type kiezen, omdat dit algemener is.
- De naam van de generatiemethode voor het markeren van de resultaten. Voor het gemak retourneren we als waarde de volledige naam van de klasse + de naam van de methode die wordt gebruikt om de MF te genereren.
Laten we eerst een abstractie declareren die wordt weergegeven door de IRandomGenerator-interface:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementatie van System.Random.Next()
Met deze methode kunt u een reeks waarden instellen, maar deze retourneert gehele getallen, maar er zijn floats nodig. Je kunt een geheel getal eenvoudigweg interpreteren als een float, of je kunt het bereik van waarden met verschillende ordes van grootte uitbreiden, en ze compenseren met elke generatie van het middenbereik. Het resultaat zal zoiets zijn als een vast punt met een bepaalde nauwkeurigheid. We zullen deze optie gebruiken omdat deze dichter bij de echte float-waarde ligt.
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;
}
}Implementatie van System.Random.NextDouble()
Hier het vaste waardenbereik [0; 1). Om het te projecteren op degene die in de constructor is gespecificeerd, gebruiken we eenvoudige rekenkunde: 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;
}
}Implementatie van UnityEngine.Random.Range()
Met deze methode van de statische klasse UnityEngine.Random kunt u een reeks waarden instellen en een float-type retourneren. U hoeft geen aanvullende transformaties uit te voeren.
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);
}
}Implementatie van UnityEngine.Random.value
De waarde-eigenschap van de statische klasse UnityEngine.Random retourneert een float-type uit een vast bereik van waarden [0; 1). Laten we het op een bepaald bereik projecteren op dezelfde manier als bij het implementeren van 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;
}
}Implementatie van Unity.Mathematics.Random.NextFloat()
De methode NextFloat() van de klasse Unity.Mathematics.Random retourneert een drijvende komma van het type float en biedt u de mogelijkheid een bereik van waarden op te geven. De enige nuance is dat elke instantie van Unity.Mathematics.Random moet worden geïnitialiseerd met een zaadje - op deze manier voorkomen we het genereren van herhalende reeksen.
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);
}
}Implementatie van MainController
Verschillende implementaties van IRandomGenerator zijn klaar. Vervolgens moet u reeksen genereren en de resulterende dataset opslaan voor verwerking. Om dit te doen, zullen we in Unity een scène en een klein MainController-script maken, dat al het nodige werk zal doen en tegelijkertijd verantwoordelijk zal zijn voor de interactie met de gebruikersinterface.
Laten we de grootte van de dataset en het bereik van MF-waarden instellen, en ook een methode verkrijgen die een array van generatoren retourneert die zijn geconfigureerd en klaar om te werken.
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)
};
}
...
}
}Laten we nu een dataset maken. In dit geval wordt het genereren van gegevens gecombineerd met het vastleggen van de resultaten in een tekststroom (in csv-formaat). Om de waarden van elke IRandomGenerator op te slaan, wordt een eigen afzonderlijke kolom toegewezen en bevat de eerste regel de naam van de generator.
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();
}
}
...
}
}Het enige dat overblijft is het aanroepen van de GenerateCsvDataSet-methode en het opslaan van het resultaat in een bestand, of het onmiddellijk overbrengen van de gegevens via het netwerk van het eindapparaat naar de ontvangende 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();
}
}
...
}
}De projectbronnen bevinden zich op .
Bevindingen
Er gebeurde geen wonder. Wat ze verwachtten is wat ze kregen: in alle gevallen een gelijkmatige verdeling zonder een spoor van samenzweringen. Ik zie het nut niet in van het plaatsen van afzonderlijke grafieken voor platforms; ze laten allemaal ongeveer dezelfde resultaten zien.
De realiteit is dit:
Visualisatie van sequenties in een vlak van alle vijf generatiemethoden:
En visualisatie in 3D. Ik laat alleen het resultaat van System.Random.Next() achter om niet een heleboel identieke inhoud te produceren.
Het verhaal dat in de inleiding werd verteld over de normale verdeling van UnityEngine.Random herhaalde zich niet: het was aanvankelijk onjuist, of er is sindsdien iets veranderd in de engine. Maar nu weten we het zeker.
Bron: www.habr.com