A játékfejlesztésben sokszor a véletlenszerűséggel kell valamit lekötni: a Unitynek erre van saját Randomja, és vele párhuzamosan a System.Random. Valamikor réges-régen az egyik projektnél az a benyomásom támadt, hogy mindkettő másképp működhetne (bár egyenletes eloszlásúnak kellene lennie).
Aztán nem mentek bele a részletekbe - elég volt, hogy a System.Random áttérés minden problémát kijavított. Most úgy döntöttünk, hogy részletesebben megvizsgáljuk, és egy kis kutatást végzünk: mennyire „elfogultak” vagy kiszámíthatóak az RNG-k, és melyiket válasszuk. Sőt, nem egyszer hallottam ellentmondó véleményeket az „őszinteségükről” - próbáljuk meg kitalálni, hogy a valós eredmények hogyan viszonyulnak a bejelentettekhez.
A rövid oktatási program vagy RNG valójában RNG
Ha már ismeri a véletlenszám-generátorokat, azonnal ugorhat a „Tesztelés” részre.
A véletlen számok (RN) olyan számsorozatok, amelyeket valamilyen véletlenszerű (kaotikus) folyamat segítségével generálnak, ami entrópiaforrás. Vagyis ez egy olyan sorozat, amelynek elemeit semmilyen matematikai törvény nem köti össze – nincs ok-okozati kapcsolatuk.
A véletlenszám generátort véletlenszám-generátornak (RNG) nevezzük. Úgy tűnik, hogy minden elemi, de ha az elmélettől a gyakorlat felé haladunk, akkor valójában nem olyan egyszerű szoftveres algoritmust megvalósítani egy ilyen sorozat generálására.
Az ok abban rejlik, hogy a modern fogyasztói elektronikában nem tapasztalható ugyanez a káosz. Enélkül a véletlen számok megszűnnek véletlenszerűek lenni, és generátoruk nyilvánvalóan meghatározott argumentumok közönséges függvényévé válik. Az informatikai terület számos szakterülete számára ez komoly probléma (például a kriptográfia), de mások számára van teljesen elfogadható megoldás.
Olyan algoritmust kell írni, amely ugyan nem igazán véletlen számokat ad vissza, de azokhoz a lehető legközelebb - az úgynevezett pszeudo-véletlen számokat (PRN). Az algoritmust ebben az esetben pszeudovéletlenszám-generátornak (PRNG) nevezzük.
Számos lehetőség van a PRNG létrehozására, de a következők mindenki számára relevánsak lesznek:
- Előzetes inicializálás szükségessége.
A PRNG-nek nincs entrópiaforrása, ezért használat előtt meg kell adni egy kezdeti állapotot. Számként (vagy vektorként) van megadva, és magnak (random seed) nevezik. Gyakran a processzor órajel-számlálóját vagy a rendszeridő számszerű megfelelőjét használják magként.
- A szekvencia reprodukálhatósága.
A PRNG teljesen determinisztikus, így az inicializálás során megadott mag egyértelműen meghatározza a teljes jövőbeli számsort. Ez azt jelenti, hogy egy különálló, ugyanazzal a seeddel inicializált PRNG (különböző időpontokban, különböző programokban, különböző eszközökön) ugyanazt a sorozatot generálja.
Ismernie kell a PRNG-t jellemző valószínűségi eloszlást is - milyen számokat fog generálni és milyen valószínűséggel. Leggyakrabban ez normális eloszlás vagy egyenletes eloszlás.
Normál eloszlás (balra) és egyenletes eloszlás (jobbra)
Tegyük fel, hogy van egy 24 oldalas fair die. Ha feldobja, annak a valószínűsége, hogy egyet kap, 1/24 lesz (ugyanannyi a valószínűsége, mint bármely más szám megszerzésének). Ha sok dobást hajt végre, és rögzíti az eredményeket, észre fogja venni, hogy az összes él megközelítőleg azonos gyakorisággal esik ki. Lényegében ez a kocka egyenletes eloszlású RNG-nek tekinthető.
Mi van, ha egyszerre dobsz 10 ilyen kockát, és megszámolod az összes pontot? Megmarad-e az egységesség? Nem. Leggyakrabban az összeg 125 pont közelében lesz, vagyis valamilyen átlagos értékhez. Ennek eredményeként még a dobás előtt nagyjából megbecsülheti a jövőbeni eredményt.
Ennek az az oka, hogy ott van a legtöbb kombináció az átlagos pontszám eléréséhez. Minél távolabb van ettől, annál kevesebb a kombináció - és ennek megfelelően annál kisebb a veszteség valószínűsége. Ha ezeket az adatokat megjelenítjük, homályosan egy harang alakjára fog hasonlítani. Ezért némi nyújtással egy 10 kockából álló rendszert normál eloszlású RNG-nek nevezhetünk.
Egy másik példa, csak ezúttal egy repülőgépen - célba lövés. A lövő egy RNG lesz, amely egy számpárt (x, y) generál, amely megjelenik a grafikonon.
Fogadja el, hogy a bal oldali lehetőség közelebb áll a valós élethez - ez egy normál eloszlású RNG. De ha a csillagokat sötét égbolton kell szétszórnia, akkor a megfelelő lehetőség, amelyet egyenletes eloszlású RNG használatával kapunk, jobban megfelel. Általában az adott feladattól függően válasszon generátort.
Most beszéljünk a PNG szekvencia entrópiájáról. Például van egy sorozat, amely így kezdődik:
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, ...
Mennyire véletlenszerűek ezek a számok első ránézésre? Kezdjük az elosztás ellenőrzésével.
Közel egységesnek tűnik, de ha két számsort olvasunk, és koordinátákként értelmezzük egy síkon, akkor ezt kapjuk:
A minták jól láthatóvá válnak. És mivel a szekvenciában az adatok meghatározott módon vannak elrendezve (azaz alacsony entrópiájú), ez éppen ezt az „elfogultságot” idézheti elő. Legalább egy ilyen PRNG nem nagyon alkalmas síkon történő koordináták generálására.
Egy másik sorrend:
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, ...
Úgy tűnik, itt még a repülőn is minden rendben van:
Nézzük kötetben (egyszerre három számot olvasunk):
És megint a minták. Már nem lehet négydimenziós vizualizációt felépíteni. De létezhetnek minták ezen a dimenzión és a nagyobbakon is.
A kriptográfiában, ahol a legszigorúbb követelményeket támasztják a PRNG-kkel szemben, az ilyen helyzet kategorikusan elfogadhatatlan. Ezért minőségük felmérésére speciális algoritmusokat fejlesztettek ki, amelyekre most nem térünk ki. A téma kiterjedt, és külön cikket érdemel.
tesztelés
Ha valamit nem tudunk biztosan, akkor hogyan dolgozzunk vele? Megéri átkelni az úton, ha nem tudja, melyik lámpa engedi meg? A következmények eltérőek lehetnek.
Ugyanez vonatkozik a Unity hírhedt véletlenszerűségére is. Jó, ha a dokumentációból kiderülnek a szükséges részletek, de a cikk elején említett történet éppen a kívánt konkrétumok hiánya miatt történt.
És ha nem ismeri az eszköz működését, nem fogja tudni megfelelően használni. Általánosságban elmondható, hogy eljött az ideje, hogy ellenőrizzük és végezzünk kísérletet, hogy végre megbizonyosodjunk legalább a terjesztésről.
A megoldás egyszerű és hatékony volt – gyűjtsön statisztikákat, szerezzen objektív adatokat és nézze meg az eredményeket.
Tanulmányi tárgy
Számos módja van véletlen számok generálására a Unityben – ötöt teszteltünk.
- System.Random.Next(). Egész számokat generál adott értéktartományban.
- System.Random.NextDouble(). Dupla pontosságú számokat generál a [0; 1).
- UnityEngine.Random.Range(). Egyedi precíziós számokat generál (lebeg) egy adott értéktartományban.
- UnityEngine.Random.value. Egyedi precíziós számokat generál (lebeg) a [0; 1).
- Unity.Mathematics.Random.NextFloat(). Az új Unity.Mathematics könyvtár része. Egyedi precíziós számokat generál (lebeg) egy adott értéktartományban.
A dokumentációban szinte mindenhol egységes eloszlást határoztak meg, kivéve a UnityEngine.Random.value (ahol az eloszlás nem volt megadva, de a UnityEngine.Random.Range() egységes analógiájára szintén elvárták) és a Unity.Mathematics.Random .NextFloat() (ahol az alap az xorshift algoritmus, ami azt jelenti, hogy ismét meg kell várni az egyenletes eloszlást).
Alapértelmezés szerint a várt eredményeket a dokumentációban megadottak szerint vettük.
technika
Írtunk egy kis alkalmazást, amely a bemutatott módszerek mindegyikével véletlenszám-sorozatokat generált, és az eredményeket elmentette további feldolgozásra.
Minden sorozat hossza 100 000 szám.
A véletlen számok tartománya [0, 100).
Az adatokat több célplatformról gyűjtöttük:
- Windows
— Unity v2018.3.14f1, Szerkesztő mód, Mono, .NET Standard 2.0 - MacOS
— Unity v2018.3.14f1, Szerkesztő mód, Mono, .NET Standard 2.0
— Unity v5.6.4p4, Szerkesztő mód, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, build per eszköz, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, build per eszköz, il2cpp, .NET Standard 2.0
Реализация
Számos különböző módszerünk van véletlen számok generálására. Mindegyikhez külön wrapper osztályt írunk, amely a következőket tartalmazza:
- Lehetőség az értéktartomány beállítására [min/max). A kivitelezőn keresztül lesz beállítva.
- MF visszaadási módszer. Típusnak válasszuk az úszót, mivel az általánosabb.
- Az eredmények jelölésére szolgáló generálási módszer neve. A kényelem kedvéért értékként visszaadjuk az osztály teljes nevét + az MF generálásához használt metódus nevét.
Először deklaráljunk egy absztrakciót, amelyet az IRandomGenerator felület képvisel:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}A System.Random.Next() megvalósítása
Ez a módszer lehetővé teszi egy értéktartomány beállítását, de egész számokat ad vissza, de lebegőpontokra van szükség. Egyszerűen értelmezheti az egész számot lebegőpontként, vagy több nagyságrenddel bővítheti az értékek tartományát, kompenzálva azokat a középtartomány minden generációjával. Az eredmény olyan lesz, mint egy fixpont, adott sorrendben a pontossággal. Ezt az opciót fogjuk használni, mivel közelebb áll a valós lebegőértékhez.
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;
}
}A System.Random.NextDouble() megvalósítása
Itt a rögzített értéktartomány [0; 1). A konstruktorban megadottra vetítéséhez egyszerű aritmetikát használunk: 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;
}
}A UnityEngine.Random.Range() megvalósítása
A UnityEngine.Random statikus osztály ezen metódusa lehetővé teszi egy értéktartomány beállítását, és egy lebegő típust ad vissza. Nem kell további átalakításokat végrehajtania.
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);
}
}A UnityEngine.Random.value megvalósítása
A UnityEngine.Random statikus osztály érték tulajdonsága egy lebegő típust ad vissza egy rögzített értéktartományból [0; 1). Ugyanúgy vetítsük ki egy adott tartományra, mint a System.Random.NextDouble() megvalósításánál.
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;
}
}A Unity.Mathematics.Random.NextFloat() megvalósítása
A Unity.Mathematics.Random osztály NextFloat() metódusa egy float típusú lebegőpontot ad vissza, és lehetővé teszi egy értéktartomány megadását. Az egyetlen árnyalat az, hogy a Unity.Mathematics.Random minden egyes példányát valamilyen seeddel kell inicializálni – így elkerüljük az ismétlődő sorozatok generálását.
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);
}
}A MainController megvalósítása
Az IRandomGenerator számos megvalósítása készen áll. Ezután sorozatokat kell generálnia, és az eredményül kapott adatkészletet el kell mentenie feldolgozásra. Ehhez létrehozunk egy jelenetet és egy kis MainController szkriptet a Unityben, amely elvégzi az összes szükséges munkát, és egyúttal felelős a felhasználói felülettel való interakcióért.
Állítsuk be az adatkészlet méretét és az MF értékek tartományát, és kapjunk egy metódust is, amely konfigurált és működésre kész generátortömböt ad vissza.
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)
};
}
...
}
}Most hozzunk létre egy adatkészletet. Ebben az esetben az adatgenerálás az eredmények szövegfolyamba (csv formátumban) történő rögzítésével párosul. Az egyes IRandomGenerator értékeinek tárolásához külön oszlop van hozzárendelve, és az első sor tartalmazza a generátor nevét.
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();
}
}
...
}
}Nem marad más hátra, mint meghívni a GenerateCsvDataSet metódust, és az eredményt fájlba menteni, vagy azonnal át kell vinni az adatokat a hálózaton keresztül a végeszközről a fogadó szerverre.
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();
}
}
...
}
}A projekt forrásai itt találhatók .
Álláspontja
Nem történt csoda. Amit vártak, azt kapták – minden esetben egyenletes eloszlást, az összeesküvések nyoma nélkül. Nem látom értelmét külön grafikonok hozzáadásának a platformokhoz – mindegyik megközelítőleg ugyanazt az eredményt mutatja.
A valóság a következő:
Szekvenciák megjelenítése síkon mind az öt generálási módszerből:
És vizualizáció 3D-ben. Csak a System.Random.Next() eredményét hagyom meg, hogy ne hozzon létre egy csomó azonos tartalmat.
A bevezetőben elmondott történet a UnityEngine.Random normál eloszlásáról nem ismétlődött meg: vagy kezdetben hibás volt, vagy azóta valami megváltozott a motorban. De most már biztosak vagyunk benne.
Forrás: will.com