Inom spelutveckling behöver man ofta knyta ihop något med slumpmässighet: Unity har sin egen Random för detta, och parallellt med det finns System.Random. En gång i tiden, på ett av projekten, fick jag intrycket att båda kunde fungera olika (även om de borde ha en jämn fördelning).
Sedan gick de inte in på detaljer - det räckte med att övergången till System.Random åtgärdade alla problem. Nu bestämde vi oss för att undersöka det mer i detalj och göra lite forskning: hur "partiska" eller förutsägbara RNG:er är och vilken vi ska välja. Dessutom har jag mer än en gång hört motstridiga åsikter om deras "ärlighet" - låt oss försöka ta reda på hur de verkliga resultaten jämförs med de deklarerade.
Kort utbildningsprogram eller RNG är egentligen RNG
Om du redan är bekant med slumptalsgeneratorer kan du omedelbart hoppa till avsnittet "Testning".
Slumptal (RN) är en sekvens av tal som genereras med hjälp av någon slumpmässig (kaotisk) process, en källa till entropi. Det vill säga, detta är en sekvens vars element inte är sammanlänkade av någon matematisk lag - de har inget orsak- och verkansamband.
Det som skapar slumptalet kallas en slumpgenerator (RNG). Det verkar som att allt är elementärt, men om vi går från teori till praktik är det faktiskt inte så enkelt att implementera en mjukvarualgoritm för att generera en sådan sekvens.
Anledningen ligger i frånvaron av samma kaos i modern hemelektronik. Utan det upphör slumptal att vara slumpmässiga, och deras generator förvandlas till en vanlig funktion av uppenbart definierade argument. För ett antal specialiteter inom IT-området är detta ett allvarligt problem (till exempel kryptografi), men för andra finns det en helt acceptabel lösning.
Det är nödvändigt att skriva en algoritm som skulle returnera, om än inte riktigt slumpmässiga tal, men så nära dem som möjligt - de så kallade pseudoslumptalen (PRN). Algoritmen i detta fall kallas en pseudoslumptalsgenerator (PRNG).
Det finns flera alternativ för att skapa en PRNG, men följande kommer att vara relevant för alla:
- Behovet av preliminär initiering.
PRNG har ingen källa till entropi, så den måste ges ett initialt tillstånd före användning. Det anges som ett tal (eller vektor) och kallas ett frö (slumpmässigt frö). Ofta används processorns klockräknare eller den numeriska ekvivalenten av systemtid som ett frö.
- Sekvensreproducerbarhet.
PRNG är helt deterministisk, så det frö som anges under initialiseringen bestämmer unikt hela den framtida sekvensen av tal. Detta innebär att en separat PRNG initierad med samma seed (vid olika tidpunkter, i olika program, på olika enheter) kommer att generera samma sekvens.
Du måste också känna till sannolikhetsfördelningen som kännetecknar PRNG - vilka tal den kommer att generera och med vilken sannolikhet. Oftast är detta antingen en normalfördelning eller en enhetlig fördelning.
Normalfördelning (vänster) och enhetlig fördelning (höger)
Låt oss säga att vi har en rättvis tärning med 24 sidor. Om du slänger den kommer sannolikheten att få en etta vara lika med 1/24 (samma som sannolikheten att få ett annat tal). Om du gör många kast och registrerar resultatet kommer du att märka att alla kanter faller ut med ungefär samma frekvens. I huvudsak kan denna tärning betraktas som en RNG med en enhetlig fördelning.
Vad händer om du kastar 10 av dessa tärningar på en gång och räknar de totala poängen? Kommer enhetlighet att upprätthållas för det? Nej. Oftast kommer beloppet att vara nära 125 poäng, det vill säga till något medelvärde. Och som ett resultat, även innan du gör ett kast, kan du grovt uppskatta det framtida resultatet.
Anledningen är att det finns det största antalet kombinationer för att få medelpoängen. Ju längre bort, desto färre kombinationer - och följaktligen desto lägre är sannolikheten för en förlust. Om denna data visualiseras kommer den vagt att likna formen på en klocka. Därför, med viss sträckning, kan ett system med 10 tärningar kallas en RNG med normalfördelning.
Ett annat exempel, bara den här gången på ett plan - att skjuta mot ett mål. Shootern kommer att vara en RNG som genererar ett par siffror (x, y) som visas på grafen.
Håller med om att alternativet till vänster är närmare det verkliga livet - det här är en RNG med normalfördelning. Men om du behöver sprida stjärnor på en mörk himmel, är det rätta alternativet, erhållet med RNG med en enhetlig fördelning, bättre lämpat. I allmänhet, välj en generator beroende på uppgiften.
Låt oss nu prata om entropin i PNG-sekvensen. Det finns till exempel en sekvens som börjar så här:
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, ...
Hur slumpmässiga är dessa siffror vid första anblicken? Låt oss börja med att kontrollera distributionen.
Det ser nästan enhetligt ut, men om du läser en sekvens av två tal och tolkar dem som koordinater på ett plan får du detta:
Mönster blir tydligt synliga. Och eftersom data i sekvensen är ordnade på ett visst sätt (det vill säga den har låg entropi), kan detta ge upphov till just den "bias". Som ett minimum är en sådan PRNG inte särskilt lämplig för att generera koordinater på ett plan.
En annan 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, ...
Allt verkar vara bra här även på planet:
Låt oss titta i volym (läs tre siffror åt gången):
Och återigen mönstren. Det går inte längre att konstruera en visualisering i fyra dimensioner. Men mönster kan finnas på denna dimension och på större.
Inom kryptografi, där de strängaste kraven ställs på PRNG:er, är en sådan situation kategoriskt oacceptabel. Därför har speciella algoritmer tagits fram för att bedöma deras kvalitet, vilket vi inte ska beröra nu. Ämnet är omfattande och förtjänar en separat artikel.
testning
Om vi inte vet något säkert, hur ska vi då arbeta med det? Är det värt att korsa vägen om du inte vet vilket trafikljus som tillåter det? Konsekvenserna kan bli olika.
Detsamma gäller den ökända slumpen i Unity. Det är bra om dokumentationen avslöjar de nödvändiga detaljerna, men historien som nämns i början av artikeln hände just på grund av bristen på de önskade detaljerna.
Och om du inte vet hur verktyget fungerar kommer du inte att kunna använda det korrekt. I allmänhet är det dags att kontrollera och genomföra ett experiment för att äntligen åtminstone försäkra sig om fördelningen.
Lösningen var enkel och effektiv – samla in statistik, skaffa objektiv data och titta på resultaten.
Studieämne
Det finns flera sätt att generera slumptal i Unity – vi testade fem.
- System.Random.Next(). Genererar heltal i ett givet värdeintervall.
- System.Random.NextDouble(). Genererar dubbla precisionstal i intervallet från [0; 1).
- UnityEngine.Random.Range(). Genererar enstaka precisionstal (flytande) i ett givet värdeintervall.
- UnityEngine.Random.value. Genererar enstaka precisionstal (flytande) i intervallet från [0; 1).
- Unity.Mathematics.Random.NextFloat(). En del av det nya Unity.Mathematics-biblioteket. Genererar enstaka precisionstal (flytande) i ett givet värdeintervall.
Nästan överallt i dokumentationen angavs en enhetlig fördelning, med undantag för UnityEngine.Random.value (där fördelningen inte specificerades, men i analogi med UnityEngine.Random.Range() förväntades också uniform) och Unity.Mathematics.Random .NextFloat() (där i Grunden är xorshift-algoritmen, vilket betyder att du återigen måste vänta på en enhetlig fördelning).
Som standard togs de förväntade resultaten som de som anges i dokumentationen.
teknik
Vi skrev en liten applikation som genererade sekvenser av slumptal med var och en av de presenterade metoderna och sparade resultaten för vidare bearbetning.
Längden på varje sekvens är 100 000 nummer.
Utbudet av slumptal är [0, 100).
Data samlades in från flera målplattformar:
- Windows
— Unity v2018.3.14f1, Redaktörsläge, Mono, .NET Standard 2.0 - MacOS
— Unity v2018.3.14f1, Redaktörsläge, Mono, .NET Standard 2.0
— Unity v5.6.4p4, redigeringsläge, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, byggd per enhet, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, byggd per enhet, il2cpp, .NET Standard 2.0
genomförande
Vi har flera olika sätt att generera slumptal. För var och en av dem kommer vi att skriva en separat omslagsklass, som ska ge:
- Möjlighet att ställa in värdeintervall [min/max). Kommer att ställas in via konstruktören.
- Metod som returnerar MF. Låt oss välja float som typ, eftersom det är mer generellt.
- Namnet på genereringsmetoden för att markera resultaten. För enkelhetens skull kommer vi att returnera det fullständiga namnet på klassen som ett värde + namnet på metoden som användes för att generera MF.
Låt oss först deklarera en abstraktion som kommer att representeras av IRandomGenerator-gränssnittet:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementering av System.Random.Next()
Den här metoden låter dig ställa in ett värdeintervall, men det returnerar heltal, men flyter behövs. Du kan helt enkelt tolka heltal som ett float, eller så kan du utöka värdeintervallet med flera storleksordningar och kompensera dem med varje generation av mellanregistret. Resultatet blir ungefär som en fixpunkt med en given noggrannhetsordning. Vi kommer att använda det här alternativet eftersom det är närmare det verkliga flytvärdet.
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()
Här det fasta värdeintervallet [0; 1). För att projicera den på den som anges i konstruktorn använder vi enkel 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 av UnityEngine.Random.Range()
Denna metod för UnityEngine.Random statisk klass låter dig ställa in ett värdeintervall och returnerar en flyttyp. Du behöver inte göra några ytterligare 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 av UnityEngine.Random.value
Egenskapen value för den statiska klassen UnityEngine.Random returnerar en flyttyp från ett fast värdeintervall [0; 1). Låt oss projicera det på ett givet intervall på samma sätt som när vi implementerar 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 i klassen Unity.Mathematics.Random returnerar en flytande punkt av typen float och låter dig ange ett värdeintervall. Den enda nyansen är att varje instans av Unity.Mathematics.Random måste initieras med något frö - på så sätt undviker vi att generera upprepade 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
Flera implementeringar av IRandomGenerator är klara. Därefter måste du generera sekvenser och spara den resulterande datamängden för bearbetning. För att göra detta kommer vi att skapa en scen och ett litet MainController-skript i Unity, som kommer att göra allt nödvändigt arbete och samtidigt ansvara för interaktion med UI.
Låt oss ställa in storleken på datamängden och intervallet för MF-värden, och även få en metod som returnerar en rad generatorer som är konfigurerade och redo att fungera.
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)
};
}
...
}
}Låt oss nu skapa en datauppsättning. I det här fallet kommer datagenerering att kombineras med att registrera resultaten i en textström (i csv-format). För att lagra värdena för varje IRandomGenerator tilldelas en egen separat kolumn, och den första raden innehåller namnet på generatorn.
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();
}
}
...
}
}Allt som återstår är att anropa metoden GenerateCsvDataSet och spara resultatet till en fil, eller omedelbart överföra data över nätverket från slutenheten till den mottagande servern.
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();
}
}
...
}
}Projektkällorna finns på .
Resultat
Inget mirakel hände. Vad de förväntade sig är vad de fick – i alla fall en jämn fördelning utan en antydan till konspirationer. Jag ser inte poängen med att sätta separata grafer för plattformar - de visar alla ungefär samma resultat.
Verkligheten är:
Visualisering av sekvenser på ett plan från alla fem generationsmetoderna:
Och visualisering i 3D. Jag lämnar bara resultatet av System.Random.Next() för att inte producera ett gäng identiskt innehåll.
Berättelsen som berättades i inledningen om normalfördelningen av UnityEngine.Random upprepade sig inte: antingen var den initialt felaktig eller så har något förändrats i motorn sedan dess. Men nu är vi säkra.
Källa: will.com