I spiludvikling skal man ofte binde noget op med tilfældighed: Unity har sin egen Random til dette, og sideløbende med det er der System.Random. Engang fik jeg på et af projekterne det indtryk, at begge kunne arbejde forskelligt (selvom de skulle have en jævn fordeling).
Så gik de ikke i detaljer - det var nok, at overgangen til System.Random korrigerede alle problemerne. Nu besluttede vi at se nærmere på det og lave lidt research: hvor "biased" eller forudsigelige RNG'er er, og hvilken man skal vælge. Desuden har jeg mere end én gang hørt modstridende meninger om deres "ærlighed" - lad os prøve at finde ud af, hvordan de reelle resultater sammenlignes med de erklærede.
Kort uddannelsesprogram eller RNG er faktisk RNG
Hvis du allerede er bekendt med tilfældige talgeneratorer, kan du straks springe til afsnittet "Test".
Tilfældige tal (RN) er en sekvens af tal genereret ved hjælp af en tilfældig (kaotisk) proces, en kilde til entropi. Det vil sige, at dette er en sekvens, hvis elementer ikke er indbyrdes forbundet af nogen matematisk lov - de har ingen årsag-virkning-forhold.
Det, der skaber det tilfældige tal, kaldes en tilfældig talgenerator (RNG). Det ser ud til, at alt er elementært, men hvis vi bevæger os fra teori til praksis, så er det faktisk ikke så nemt at implementere en softwarealgoritme til at generere en sådan sekvens.
Årsagen ligger i fraværet af det samme kaos i moderne forbrugerelektronik. Uden det ophører tilfældige tal med at være tilfældige, og deres generator bliver til en almindelig funktion af åbenlyst definerede argumenter. For en række specialer inden for IT-området er dette et alvorligt problem (f.eks. kryptografi), men for andre er der en helt acceptabel løsning.
Det er nødvendigt at skrive en algoritme, der ville returnere, omend ikke virkelig tilfældige tal, men så tæt som muligt på dem - de såkaldte pseudo-tilfældige tal (PRN). Algoritmen i dette tilfælde kaldes en pseudorandom number generator (PRNG).
Der er flere muligheder for at oprette en PRNG, men følgende vil være relevant for alle:
- Behovet for foreløbig initialisering.
PRNG'en har ingen entropikilde, så den skal have en indledende tilstand før brug. Det er angivet som et tal (eller vektor) og kaldes et frø (tilfældigt frø). Ofte bruges processorens urtæller eller det numeriske ækvivalent af systemtid som et frø.
- Sekvens reproducerbarhed.
PRNG er fuldstændig deterministisk, så det seed, der er angivet under initialisering, bestemmer entydigt hele den fremtidige talrække. Dette betyder, at en separat PRNG initialiseret med det samme frø (på forskellige tidspunkter, i forskellige programmer, på forskellige enheder) vil generere den samme sekvens.
Du skal også kende sandsynlighedsfordelingen, der karakteriserer PRNG - hvilke tal den vil generere og med hvilken sandsynlighed. Oftest er dette enten en normalfordeling eller en ensartet fordeling.
Normalfordeling (venstre) og ensartet fordeling (højre)
Lad os sige, at vi har en fair terning med 24 sider. Hvis du kaster den, vil sandsynligheden for at få en et være lig med 1/24 (det samme som sandsynligheden for at få et hvilket som helst andet tal). Hvis du laver mange kast og registrerer resultaterne, vil du bemærke, at alle kanter falder ud med nogenlunde samme frekvens. I det væsentlige kan denne matrice betragtes som en RNG med en ensartet fordeling.
Hvad hvis du kaster 10 af disse terninger på én gang og tæller de samlede point? Vil der blive opretholdt ensartethed for det? Ingen. Oftest vil beløbet være tæt på 125 point, altså til en eller anden gennemsnitsværdi. Og som et resultat, selv før du laver et kast, kan du groft estimere det fremtidige resultat.
Årsagen er, at der er det største antal kombinationer for at opnå den gennemsnitlige score. Jo længere fra det, jo færre kombinationer - og følgelig jo lavere er sandsynligheden for et tab. Hvis disse data visualiseres, vil de vagt ligne formen af en klokke. Derfor kan et system med 10 terninger med en vis strækning kaldes en RNG med en normalfordeling.
Et andet eksempel, kun denne gang på et fly - at skyde mod et mål. Skydespilleren vil være en RNG, der genererer et par tal (x, y), der vises på grafen.
Enig, at muligheden til venstre er tættere på det virkelige liv - dette er en RNG med en normalfordeling. Men hvis du har brug for at sprede stjerner på en mørk himmel, så er den rigtige mulighed, opnået ved hjælp af RNG med en ensartet fordeling, bedre egnet. Generelt skal du vælge en generator afhængigt af opgaven.
Lad os nu tale om entropien af PNG-sekvensen. For eksempel er der en sekvens, der starter sådan her:
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, ...
Hvor tilfældige er disse tal ved første øjekast? Lad os starte med at tjekke fordelingen.
Det ser tæt på uniform, men hvis du læser en sekvens af to tal og fortolker dem som koordinater på et plan, får du dette:
Mønstre bliver tydeligt synlige. Og da dataene i sekvensen er ordnet på en bestemt måde (det vil sige, at de har lav entropi), kan dette give anledning til netop den "bias". En sådan PRNG er som minimum ikke særlig velegnet til at generere koordinater på et plan.
En anden sekvens:
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, ...
Alt ser ud til at være fint her selv på flyet:
Lad os se i volumen (læs tre tal ad gangen):
Og igen mønstrene. Det er ikke længere muligt at konstruere en visualisering i fire dimensioner. Men mønstre kan eksistere på denne dimension og på større.
I kryptografi, hvor de strengeste krav stilles til PRNG'er, er en sådan situation kategorisk uacceptabel. Derfor er der udviklet specielle algoritmer til at vurdere deres kvalitet, som vi ikke vil komme ind på nu. Emnet er omfattende og fortjener en separat artikel.
Test
Hvis vi ikke ved noget med sikkerhed, hvordan arbejder vi så med det? Er det værd at krydse vejen, hvis du ikke ved, hvilket lyskryds tillader det? Konsekvenserne kan være anderledes.
Det samme gælder den notoriske tilfældighed i Unity. Det er godt, hvis dokumentationen afslører de nødvendige detaljer, men historien nævnt i begyndelsen af artiklen skete netop på grund af manglen på de ønskede detaljer.
Og hvis du ikke ved, hvordan værktøjet fungerer, vil du ikke kunne bruge det korrekt. Generelt er tiden kommet til at kontrollere og gennemføre et eksperiment for endelig at sikre sig i det mindste om fordelingen.
Løsningen var enkel og effektiv – indsaml statistik, indhent objektiv data og se på resultaterne.
Undersøgelsesemne
Der er flere måder at generere tilfældige tal i Unity - vi testede fem.
- System.Random.Next(). Genererer heltal i et givet værdiområde.
- System.Random.NextDouble(). Genererer dobbelte præcisionstal i området fra [0; 1).
- UnityEngine.Random.Range(). Genererer enkelte præcisionstal (flydende) i et givet værdiområde.
- UnityEngine.Random.value. Genererer enkelte præcisionstal (flydende) i området fra [0; 1).
- Unity.Mathematics.Random.NextFloat(). En del af det nye Unity.Mathematics bibliotek. Genererer enkelte præcisionstal (flydende) i et givet værdiområde.
Næsten overalt i dokumentationen var en ensartet fordeling angivet, med undtagelse af UnityEngine.Random.value (hvor fordelingen ikke var specificeret, men analogt med UnityEngine.Random.Range() var der også forventet uniform) og Unity.Mathematics.Random .NextFloat() (hvor i Grundlaget er xorshift-algoritmen, hvilket betyder, at du igen skal vente på en ensartet fordeling).
Som standard blev de forventede resultater taget som dem, der er angivet i dokumentationen.
teknik
Vi skrev en lille applikation, der genererede sekvenser af tilfældige tal ved hjælp af hver af de præsenterede metoder og gemte resultaterne til videre behandling.
Længden af hver sekvens er 100 tal.
Udvalget af tilfældige tal er [0, 100).
Data blev indsamlet fra flere målplatforme:
- Windows
— Unity v2018.3.14f1, Editor-tilstand, Mono, .NET Standard 2.0 - MacOS
— Unity v2018.3.14f1, Editor-tilstand, Mono, .NET Standard 2.0
— Unity v5.6.4p4, Editor-tilstand, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, bygget pr. enhed, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, bygget pr. enhed, il2cpp, .NET Standard 2.0
implementering
Vi har flere forskellige måder at generere tilfældige tal på. For hver af dem vil vi skrive en separat indpakningsklasse, som skal give:
- Mulighed for at indstille værdiområdet [min/max). Vil blive indstillet via konstruktøren.
- Metode, der returnerer MF. Lad os vælge float som type, da det er mere generelt.
- Navnet på genereringsmetoden til markering af resultaterne. For nemheds skyld returnerer vi som en værdi det fulde navn på klassen + navnet på den metode, der blev brugt til at generere MF.
Lad os først erklære en abstraktion, der vil blive repræsenteret af IRandomGenerator-grænsefladen:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementering af System.Random.Next()
Denne metode giver dig mulighed for at indstille en række værdier, men den returnerer heltal, men der er behov for flydende. Du kan simpelthen fortolke heltal som et flydende tal, eller du kan udvide værdiområdet med flere størrelsesordener og kompensere dem med hver generation af mellemtonen. Resultatet vil være noget som et fikspunkt med en given rækkefølge af nøjagtighed. Vi vil bruge denne mulighed, da den er tættere på den reelle flydende værdi.
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;
}
}Implementering af System.Random.NextDouble()
Her det faste værdiområde [0; 1). For at projicere det på den, der er angivet i konstruktøren, bruger vi simpel aritmetik: 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;
}
}Implementering af UnityEngine.Random.Range()
Denne metode i UnityEngine.Random statisk klasse giver dig mulighed for at indstille en række værdier og returnerer en flydende type. Du behøver ikke at foretage yderligere transformationer.
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);
}
}Implementering af UnityEngine.Random.value
Værdiegenskaben for den statiske klasse UnityEngine.Random returnerer en flydende type fra et fast interval af værdier [0; 1). Lad os projicere det på et givet område på samme måde, som når vi implementerer 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;
}
}Implementering af Unity.Mathematics.Random.NextFloat()
NextFloat()-metoden i klassen Unity.Mathematics.Random returnerer et flydende punkt af typen float og giver dig mulighed for at angive en række værdier. Den eneste nuance er, at hver forekomst af Unity.Mathematics.Random skal initialiseres med nogle frø - på denne måde undgår vi at generere gentagne sekvenser.
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);
}
}Implementering af MainController
Flere implementeringer af IRandomGenerator er klar. Dernæst skal du generere sekvenser og gemme det resulterende datasæt til behandling. For at gøre dette vil vi lave en scene og et lille MainController-script i Unity, som vil udføre alt det nødvendige arbejde og samtidig være ansvarlig for interaktion med UI'en.
Lad os indstille størrelsen af datasættet og intervallet af MF-værdier og også få en metode, der returnerer en række generatorer, der er konfigureret og klar til at arbejde.
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)
};
}
...
}
}Lad os nu oprette et datasæt. I dette tilfælde vil datagenerering blive kombineret med registrering af resultaterne i en tekststrøm (i csv-format). For at gemme værdierne for hver IRandomGenerator tildeles dens egen separate kolonne, og den første linje indeholder navnet på generatoren.
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();
}
}
...
}
}Det eneste, der er tilbage, er at kalde GenerateCsvDataSet-metoden og gemme resultatet i en fil, eller straks overføre dataene over netværket fra slutenheden til den modtagende 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();
}
}
...
}
}Projektkilderne er kl .
Fund
Intet mirakel skete. Det, de forventede, var, hvad de fik – i alle tilfælde en jævn fordeling uden antydning af konspirationer. Jeg kan ikke se meningen med at sætte separate grafer for platforme - de viser alle omtrent de samme resultater.
Virkeligheden er:
Visualisering af sekvenser på et plan fra alle fem generationsmetoder:
Og visualisering i 3D. Jeg efterlader kun resultatet af System.Random.Next() for ikke at producere en masse identisk indhold.
Historien, der blev fortalt i introduktionen om normalfordelingen af UnityEngine.Random gentog sig ikke: enten var den oprindeligt fejlagtig, eller også har noget ændret sig i motoren. Men nu er vi sikre.
Kilde: www.habr.com