I spillutvikling må du ofte knytte noe til tilfeldighet: Unity har sin egen Random for dette, og parallelt med det er det System.Random. En gang i tiden, på et av prosjektene, fikk jeg inntrykk av at begge kunne fungere forskjellig (selv om de burde ha en jevn fordeling).
Så gikk de ikke inn i detaljer - det var nok at overgangen til System.Random løste alle problemene. Nå bestemte vi oss for å se nærmere på det og foreta litt forskning: hvor "partisk" eller forutsigbare RNG-er er, og hvilken vi skal velge. Dessuten har jeg mer enn en gang hørt motstridende meninger om deres "ærlighet" - la oss prøve å finne ut hvordan de virkelige resultatene er sammenlignet med de deklarerte.
Kort utdanningsprogram eller RNG er faktisk RNG
Hvis du allerede er kjent med tilfeldige tallgeneratorer, kan du umiddelbart hoppe til delen "Testing".
Tilfeldige tall (RN) er en sekvens av tall generert ved hjelp av en tilfeldig (kaotisk) prosess, en kilde til entropi. Det vil si at dette er en sekvens hvis elementer ikke er sammenkoblet av noen matematisk lov - de har ingen årsak-virkning-forhold.
Det som skaper det tilfeldige tallet kalles en tilfeldig tallgenerator (RNG). Det ser ut til at alt er elementært, men hvis vi går fra teori til praksis, så er det faktisk ikke så enkelt å implementere en programvarealgoritme for å generere en slik sekvens.
Årsaken ligger i fraværet av det samme kaoset i moderne forbrukerelektronikk. Uten det slutter tilfeldige tall å være tilfeldige, og generatoren deres blir til en vanlig funksjon av åpenbart definerte argumenter. For en rekke spesialiteter innen IT-feltet er dette et alvorlig problem (for eksempel kryptografi), men for andre er det en helt akseptabel løsning.
Det er nødvendig å skrive en algoritme som vil returnere, om enn ikke virkelig tilfeldige tall, men så nært som mulig - de såkalte pseudo-tilfeldige tallene (PRN). Algoritmen i dette tilfellet kalles en pseudorandom number generator (PRNG).
Det er flere alternativer for å lage en PRNG, men følgende vil være relevant for alle:
- Behovet for foreløpig initialisering.
PRNG har ingen kilde til entropi, så den må gis en starttilstand før bruk. Det er spesifisert som et tall (eller vektor) og kalles et frø (tilfeldig frø). Ofte brukes prosessorens klokketeller eller den numeriske ekvivalenten av systemtid som et frø.
- Sekvensreproduserbarhet.
PRNG er fullstendig deterministisk, så frøet som er spesifisert under initialisering bestemmer unikt hele den fremtidige tallsekvensen. Dette betyr at en separat PRNG initialisert med samme frø (til forskjellige tider, i forskjellige programmer, på forskjellige enheter) vil generere den samme sekvensen.
Du må også vite sannsynlighetsfordelingen som karakteriserer PRNG - hvilke tall den vil generere og med hvilken sannsynlighet. Oftest er dette enten en normalfordeling eller en ensartet fordeling.
Normalfordeling (venstre) og enhetlig fordeling (høyre)
La oss si at vi har en rettferdig terning med 24 sider. Hvis du kaster den, vil sannsynligheten for å få en ener være lik 1/24 (det samme som sannsynligheten for å få et hvilket som helst annet tall). Hvis du gjør mange kast og registrerer resultatene, vil du merke at alle kantene faller ut med omtrent samme frekvens. I hovedsak kan denne terningen betraktes som en RNG med en jevn fordeling.
Hva om du kaster 10 av disse terningene på en gang og teller totalt poeng? Vil ensartethet opprettholdes for det? Nei. Oftest vil beløpet være nær 125 poeng, det vil si til en viss gjennomsnittsverdi. Og som et resultat, selv før du kaster, kan du grovt anslå det fremtidige resultatet.
Årsaken er at det er flest kombinasjoner for å oppnå gjennomsnittlig poengsum. Jo lenger unna det, jo færre kombinasjoner - og følgelig jo lavere er sannsynligheten for tap. Hvis disse dataene blir visualisert, vil de vagt ligne formen på en bjelle. Derfor, med litt strekk, kan et system med 10 terninger kalles en RNG med normalfordeling.
Et annet eksempel, bare denne gangen på et fly - å skyte på et mål. Shooteren vil være en RNG som genererer et par tall (x, y) som vises på grafen.
Enig i at alternativet til venstre er nærmere det virkelige liv - dette er en RNG med normalfordeling. Men hvis du trenger å spre stjerner på en mørk himmel, er det riktige alternativet, oppnådd ved å bruke RNG med en jevn fordeling, bedre egnet. Generelt, velg en generator avhengig av oppgaven.
La oss nå snakke om entropien til PNG-sekvensen. For eksempel er det en sekvens som starter slik:
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 tilfeldige er disse tallene ved første øyekast? La oss starte med å sjekke fordelingen.
Den ser nær uniform ut, men hvis du leser en sekvens av to tall og tolker dem som koordinater på et plan, får du dette:
Mønstre blir godt synlige. Og siden dataene i sekvensen er ordnet på en bestemt måte (det vil si at de har lav entropi), kan dette gi opphav til nettopp den "bias". I det minste er en slik PRNG lite egnet for å generere koordinater på et plan.
En annen 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 ut til å være bra her selv på flyet:
La oss se i volum (les tre tall om gangen):
Og igjen mønstrene. Det er ikke lenger mulig å konstruere en visualisering i fire dimensjoner. Men mønstre kan eksistere på denne dimensjonen og på større.
I kryptografi, hvor de strengeste kravene stilles til PRNG-er, er en slik situasjon kategorisk uakseptabel. Det er derfor utviklet spesielle algoritmer for å vurdere kvaliteten, som vi ikke skal berøre nå. Temaet er omfattende og fortjener en egen artikkel.
Testing
Hvis vi ikke vet noe sikkert, hvordan jobber vi med det? Er det verdt å krysse veien hvis du ikke vet hvilket trafikklys som tillater det? Konsekvensene kan være forskjellige.
Det samme gjelder den beryktede tilfeldigheten i Unity. Det er bra hvis dokumentasjonen avslører de nødvendige detaljene, men historien nevnt i begynnelsen av artikkelen skjedde nettopp på grunn av mangelen på de ønskede detaljene.
Og hvis du ikke vet hvordan verktøyet fungerer, vil du ikke kunne bruke det riktig. Generelt er tiden inne for å sjekke og gjennomføre et eksperiment for å endelig sikre seg i det minste om fordelingen.
Løsningen var enkel og effektiv – samle inn statistikk, få objektive data og se på resultatene.
Studieemne
Det er flere måter å generere tilfeldige tall på i Unity – vi testet fem.
- System.Random.Next(). Genererer heltall i et gitt verdiområde.
- System.Random.NextDouble(). Genererer doble presisjonstall i området fra [0; 1).
- UnityEngine.Random.Range(). Genererer enkeltpresisjonstall (flyter) i et gitt verdiområde.
- UnityEngine.Random.value. Genererer enkeltpresisjonstall (flyter) i området fra [0; 1).
- Unity.Mathematics.Random.NextFloat(). En del av det nye Unity.Mathematics-biblioteket. Genererer enkeltpresisjonstall (flyter) i et gitt verdiområde.
Nesten overalt i dokumentasjonen ble det spesifisert en enhetlig fordeling, med unntak av UnityEngine.Random.value (hvor fordelingen ikke var spesifisert, men i analogi med UnityEngine.Random.Range() uniform var også forventet) og Unity.Mathematics.Random .NextFloat() (hvor i Grunnlaget er xorshift-algoritmen, som betyr at du igjen må vente på en enhetlig fordeling).
Som standard ble de forventede resultatene tatt som de som er spesifisert i dokumentasjonen.
teknikk
Vi skrev en liten applikasjon som genererte sekvenser av tilfeldige tall ved å bruke hver av de presenterte metodene og lagret resultatene for videre behandling.
Lengden på hver sekvens er 100 000 tall.
Utvalget av tilfeldige tall er [0, 100).
Data ble samlet inn fra flere målplattformer:
- Windows
— Unity v2018.3.14f1, redigeringsmodus, mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, redigeringsmodus, mono, .NET Standard 2.0
— Unity v5.6.4p4, redigeringsmodus, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, bygget per enhet, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, bygget per enhet, il2cpp, .NET Standard 2.0
implementering
Vi har flere forskjellige måter å generere tilfeldige tall på. For hver av dem vil vi skrive en egen innpakningsklasse, som skal gi:
- Mulighet for å stille inn verdiområdet [min/maks). Vil bli satt via konstruktøren.
- Metode som returnerer MF. La oss velge flyte som type, da den er mer generell.
- Navnet på generasjonsmetoden for merking av resultatene. For enkelhets skyld vil vi returnere som en verdi hele navnet på klassen + navnet på metoden som ble brukt for å generere MF.
Først, la oss erklære en abstraksjon som vil bli representert av IRandomGenerator-grensesnittet:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementering av System.Random.Next()
Denne metoden lar deg angi en rekke verdier, men den returnerer heltall, men flyter er nødvendig. Du kan ganske enkelt tolke heltall som en flyte, eller du kan utvide verdiområdet med flere størrelsesordener, og kompensere dem med hver generasjon av mellomtonen. Resultatet vil være noe sånt som et fast punkt med en gitt rekkefølge av nøyaktighet. Vi vil bruke dette alternativet siden det er nærmere den reelle flyteverdien.
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 av System.Random.NextDouble()
Her det faste verdiområdet [0; 1). For å projisere den på den som er spesifisert i konstruktøren, bruker vi enkel aritmetikk: X * (maks − 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 av UnityEngine.Random.Range()
Denne metoden til UnityEngine.Random statisk klasse lar deg angi en rekke verdier og returnerer en flytetype. Du trenger ikke å gjøre noen ekstra transformasjoner.
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 av UnityEngine.Random.value
value-egenskapen til den statiske klassen UnityEngine.Random returnerer en flytetype fra et fast verdiområde [0; 1). La oss projisere det på et gitt område på samme måte 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 av Unity.Mathematics.Random.NextFloat()
NextFloat()-metoden til Unity.Mathematics.Random-klassen returnerer et flytende punkt av typen float og lar deg spesifisere et verdiområde. Den eneste nyansen er at hver forekomst av Unity.Mathematics.Random må initialiseres med noen frø - på denne måten vil vi unngå å generere repeterende 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 av MainController
Flere implementeringer av IRandomGenerator er klare. Deretter må du generere sekvenser og lagre det resulterende datasettet for behandling. For å gjøre dette vil vi lage en scene og et lite MainController-skript i Unity, som vil gjøre alt nødvendig arbeid og samtidig være ansvarlig for interaksjon med UI.
La oss angi størrelsen på datasettet og rekkevidden av MF-verdier, og også få en metode som returnerer en rekke generatorer som er konfigurert og klare til å fungere.
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)
};
}
...
}
}La oss nå lage et datasett. I dette tilfellet vil datagenerering kombineres med registrering av resultatene i en tekststrøm (i csv-format). For å lagre verdiene til hver IRandomGenerator, tildeles dens egen separate kolonne, og den første linjen inneholder 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();
}
}
...
}
}Alt som gjenstår er å kalle GenerateCsvDataSet-metoden og lagre resultatet til en fil, eller umiddelbart overføre dataene over nettverket fra sluttenheten til mottaksserveren.
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();
}
}
...
}
}Prosjektkildene er på .
Funn
Det skjedde ikke noe mirakel. Det de forventet er det de fikk – i alle tilfeller en jevn fordeling uten snev av konspirasjoner. Jeg ser ikke poenget med å sette separate grafer for plattformer - de viser alle omtrent de samme resultatene.
Realiteten er:
Visualisering av sekvenser på et plan fra alle fem generasjonsmetodene:
Og visualisering i 3D. Jeg vil bare legge igjen resultatet av System.Random.Next() for ikke å produsere en haug med identisk innhold.
Historien som ble fortalt i introduksjonen om normalfordelingen av UnityEngine.Random gjentok seg ikke: enten var det i utgangspunktet feil, eller noe har siden endret seg i motoren. Men nå er vi sikre.
Kilde: www.habr.com