A játékiparban gyakran szükség van arra, hogy valamit véletlenszerűségre építsünk: a Unity-nek van saját Random funkciója, de párhuzamosan létezik a System.Random is. Egy régi projekt során az a benyomás alakult ki, hogy a kettő eltérően működhet (bár egyenletes eloszlást kellene biztosítaniuk).
Akkoriban nem mélyedtünk el a részletekbe - elég volt, hogy a System.Random-ra való áttérés megoldotta a problémákat. Most úgy döntöttünk, hogy alaposabban utánajárunk, és elvégezünk egy kis kutatást: mennyire "elfogultak" vagy kiszámíthatóak a véletlenszám-generátorok, és melyiket érdemes választani. Ráadásul nem egyszer hallottam ellentmondásos véleményeket az "őszinteségükről" - próbáljuk megérteni, hogyan állnak a valós eredmények a hirdetettekkel.
Rövid oktatás vagy a véletlenszám-generátorok valójában PSZ.
Ha már ismeri a véletlenszám-generátorokat, átugorhat a "Tesztelés" részre.
A véletlenszámok (SZÁM) egy olyan számok sorozata, amelyet valamilyen véletlenszerű (kaotikus) folyamat, entropiaforrás generál. Ez azt jelenti, hogy ez egy olyan sorozat, amelynek elemei nem állnak összefüggésben matematikai törvénnyel - nincs okozati összefüggés közöttük.
Amit a véletlenszámok létrehoznak, az a véletlenszám-generátor (VG). Igen egyszerűnek tűnik, de ha a elméletről a gyakorlatra térünk, valójában nem egyszerű egy ilyen sorozat generálására szolgáló programozási algoritmust megvalósítani.
Az ok abban rejlik, hogy a modern fogyasztói elektronikai eszközökben hiányzik az a bizonyos kaotikus elem. Nélküle a véletlenszámok már nem véletlenszerűek, a generátoruk pedig egy egyszerű függvényné válik, amely olyan előre meghatározott érvek függvénye. Az IT szektor egyes szakterületein ez komoly probléma (például a kriptográfiában), mások számára azonban van elfogadható megoldás.
Olyan algoritmust kell írni, amely visszaad véletlenszerű számokat, még ha nem is igaziak, de maximálisan közel állnak hozzájuk - ezeket hívjuk úgy, hogy álelszámok (ÁE). Ez az algoritmus a véletlenszerű számok generátoraként (VSG) ismert.
Több lehetőség létezik az ÁEG létrehozására, de mindegyikre vonatkozóan fontos a következő:
- Előzetes inicializálás szükségessége.
A kriptográfiai véletlenszám-generátor (GáGP) nem rendelkezik entropiaforrással, ezért használat előtt meg kell adni a kezdeti állapotot. Ezt egy számként (vagy vektorként) kell megadni, és magvnak (seed, random seed) nevezik. Gyakran a magként a processzor ciklusainak számlálója vagy a rendszeridő numerikus megfelelője szolgál.
- A sorozat reprodukálhatósága.
A GáGP teljes mértékben determinisztikus, ezért a kezdeti mag (seed) egyértelműen meghatározza az összes jövőbeli számot. Ez azt jelenti, hogy egy adott GáGP, amelyet ugyanazzal a maggal inicializálnak (különböző időpontokban, különböző programokban, különböző eszközökön), mindig ugyanazt a sorozatot generálja.
Azt is tudni kell, hogy a GáGP milyen valószínűségi eloszlással rendelkezik - milyen számokat generál és mekkora valószínűséggel. A leggyakrabban ez vagy normál eloszlás (normal distribution), vagy egyenletes eloszlás (uniform distribution).
Normál eloszlás (balra) és egyenletes eloszlás (jobbra)
Tegyük fel, hogy van egy igazságos 24 oldalú dobókockánk. Ha megdobjuk, az az esély, hogy az egyes számot kapunk, 1/24 (mint ahogy bármely más szám esetében is). Ha sok dobást végzünk, és feljegyezzük az eredményeket, észlelhetjük, hogy az összes oldal körülbelül ugyanazzal a gyakorisággal jelenik meg. Tulajdonképpen ezt a dobókockát egyenletes eloszlású GáGP-ként is tekinthetjük.
Mi van, ha egyszerre 10 ilyen kockát dobunk, és számoljuk az összesített pontszámot? Megmarad-e az egyenletesség? Nem. Legtöbbször az összeg körülbelül 125 pont körüli lesz, tehát valamilyen átlagos értékhez közelít. Ennek következményeként - még a dobás előtt - körülbelül megbecsülhetjük a jövőbeli eredményt.
Az az ok, hogy a legmagasabb kombinációk száma a középérték eléréséhez szükséges. Minél távolabb vagyunk tőle, annál kevesebb a kombináció - és ezzel együtt kevesebb az előfordulás valószínűsége. Ha ezeket az adatokat vizualizáljuk, formájukban távolról emlékeztetnek egy harangra. Ezért valamilyen értelemben a 10 kockából álló rendszert normál eloszlású GáGP-ként lehet nevezni.
Még egy példa, de már a síkban - célba lövés. A lövő egy GáGP lesz, amely pár számot (x, y) generál, amely a grafikonon megjelenik.
Egyetérthetünk, hogy a baloldali változat közelebb áll a valósághoz - ez egy normál eloszlású véletlenszám-generátor. De ha csillagokat kell szétszórni a sötét égbolton, akkor a jobb változat, amelyet egy egyenletes eloszlású véletlenszám-generátorral nyertünk, jobban megfelel. Összességében válassza a generátort a feladat függvényében.
Most beszéljünk a véletlenszám sorozatának 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ő látásra? Kezdjük a eloszlás ellenőrzésével.
Úgy tűnik, hogy közel egyenletes, de ha a sorozatot két szám alapján olvassuk, és ezekből koordinátákat értelmezünk a síkon, akkor ez jön ki:
Élesebben megjelennek a minták. Mivel az adatok a sorozatban valamilyen módon rendezettek (tehát alacsony entrópiával rendelkeznek), ez eredményezheti azt a bizonyos „elfogultságot”. Legalábbis egy ilyen Pseudorandom Number Generator (PRNG) nem igazán alkalmas koordináták generálására a síkon.
Egy másik sorozat:
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, …
Itt úgy tűnik, minden rendben van, még a síkon is:
Nézzük meg három dimenzióban (három számot olvasunk):
Ismét minták. Négy dimenzióban már nem tudunk vizualizálni. De a minták létezhetnek ezen a dimenzión és nagyobbakon is.
A kriptográfiában, ahol a PSN-sel szemben a legszigorúbb követelmények vannak, egy ilyen helyzet kategorikusan elfogadhatatlan. Ezért speciális algoritmusokat fejlesztettek ki a minőségük értékelésére, amelyekről most nem fogunk beszélni. A téma széleskörű és külön cikket igényel.
Tesztelés
Ha valamit nem tudunk biztosan, hogyan kell ezzel bánni? Érdemes-e átkelni az úton, ha nem tudod, hogy melyik jelzi a zöld lámpát? A következmények különbözőek lehetnek.
Ugyanez érvényes a hírhedt véletlenszámra a Unityben. Jó, ha a dokumentáció felfedi a szükséges részleteket, de a cikk elején említett eset éppen a kívánt konkretizáció hiányából adódott.
Ha nem tudod, hogyan működik az eszköz, nem tudod megfelelően alkalmazni. Itt az idő, hogy teszteljünk és kísérletezzünk, hogy végleg megbizonyosodjunk legalább a megoszlásról.
A megoldás egyszerű és hatékony volt — statisztikát gyűjteni, objektív adatokat szerezni és megnézni az eredményeket.
A kutatás tárgya
A Unity-ben több módon is lehet véletlenszámokat generálni — öt különböző megoldást teszteltünk.
- System.Random.Next(). Egész számokat (integer) generál a megadott értékhatárok között.
- System.Random.NextDouble(). Kettős pontosságú (double) számokat generál a [0; 1) tartományban.
- UnityEngine.Random.Range(). Egyszeres pontosságú (float) számokat generál a megadott értékhatárok között.
- UnityEngine.Random.value. Egyszeres pontosságú (float) számokat generál a [0; 1) tartományban.
- Unity.Mathematics.Random.NextFloat(). A Unity.Mathematics új könyvtárának része. Egyszeres pontosságú (float) számokat generál a megadott értékhatárok között.
A dokumentáció szinte mindenütt egyenletes eloszlást említ, kivéve a UnityEngine.Random.value-t (ahol az eloszlás nincs megadva, de a UnityEngine.Random.Range()-hez hasonlóan egyenleges eloszlásra lehetett számítani) és a Unity.Mathematics.Random.NextFloat()-ot (ahol az algoritmus xorshift alapú, tehát újra várni kell az egyenletes eloszlásra).
Alapértelmezés szerint a dokumentációban megadott elvárt eredményeket vettük figyelembe.
Módszertan
Írtunk egy kis alkalmazást, amely minden bemutatott módszerrel véletlenszám-sorozatokat generált, és elmentette az eredményeket további feldolgozásra.
Minden sorozat hossza — 100 000 szám.
A véletlenszámok értékhatára — [0, 100).
Az adatokat több céleszközről gyűjtöttük:
- Windows
— Unity v2018.3.14f1, Editor mód, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, Editor mód, Mono, .NET Standard 2.0
— Unity v5.6.4p4, Editor mód, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, eszközre történő építés, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, eszközre történő építés, il2cpp, .NET Standard 2.0
Megvalósítás
Több különböző módunk van véletlenszámok generálására. Mindegyikhez külön osztályt írunk, amely a következőket kell, hogy nyújtsa:
- A számértékek [min/max) határainak megadásának lehetősége. Ezt a konstruktoron keresztül fogjuk megadni.
- Egy metódus, amely visszaadja a véletlenszámot. Típusként a float-ot választjuk, mint általánosabbat.
- A generálási módszer megnevezése az eredmények megjelöléséhez. Az egyszerűség kedvéért a teljes osztály neve + a generáláshoz használt metódus neve lesz az érték.
Először hirdessük meg az absztrakciót, amelyet az IRandomGenerator interfész 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, hogy megadjuk az értékek tartományát, de egész számokat (integer) ad vissza, míg float-okra van szükség. Az integer-t egyszerűen float-ként lehet értelmezni, vagy a tartományt kiterjeszthetjük több nagyságrendre, kompenzálva őket minden egyes véletlenszám generálás során. Valami hasonlót kapunk, mint a fixpontos számok adott pontossággal. Ezt a lehetőséget fogjuk használni, mivel ez közelebb áll a valódi float é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 egy fix értéktartomány [0; 1). Ahhoz, hogy ezt a konstruktorban megadott tartományra vetítsük, 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
Ez a statikus UnityEngine.Random osztály módszere lehetővé teszi, hogy megadjuk az értékek tartományát és float típusú véletlenszámot ad vissza. Nincs szükség további átalakításokra.
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 value tulajdonsága egy float típusú véletlenszámot ad vissza a [0; 1) fix értéktartományból. Ezt a tartományt ugyanazon módszer szerint vetítjük, mint a System.Random.NextDouble() megvalósításakor.
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 float típusú véletlenszámot ad vissza, és lehetővé teszi egy értékkészlet megadását. Az egyetlen apró részlet, hogy minden Unity.Mathematics.Random példányt inicializálni kell egy seed-del, így kerülhetjük el 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
Több IRandomGenerator megvalósítás kész van. Most generálni kell a sorozatokat és elmenteni az eredményül kapott adatbázist feldolgozás céljából. Ehhez létrehozunk egy Unity jelenetet és egy kis MainController szkriptet, amely elvégzi az összes szükséges feladatot, és egyidejűleg felelős lesz a UI-val való interakcióért.
Beállítjuk az adatbázis méretét és a véletlenszámok értékkészletét, valamint létrehozunk egy metódust, amely egy tömböt ad vissza az konfigurált és működésre kész generátorokkal.
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 pedig formáljuk meg az adatbázist. Ebben az esetben az adatok generálása egybeesik az eredmények szöveges streambe való írásával (csv formátumban). Minden IRandomGenerator számára külön oszlopot szánunk, az első sorban pedig a generátor nevét tároljuk.
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();
}
}
...
}
}Meg kell hívni a GenerateCsvDataSet metódust, és el kell menteni az eredményt fájlba, vagy azonnal át kell adni az adatokat a végső eszközről a fogadó félnek. szerver.
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: .
Eredmények
Nem történt csoda. Amit vártunk, azt kaptuk — minden esetben egyenletes eloszlás, mindenféle összeesküvésre utalás nélkül. Nincs értelme külön grafikonokat mellékelni a platformok számára — mind hasonló eredményeket mutat.
A valóság így néz ki:
Az összes öt generálási módszer során a sorozatok vizualizációja a síkban:
És a vizualizáció 3D-ben. Csak a System.Random.Next() eredményét hagyom meg, hogy ne sok azonos tartalmat szaporítsak.
A bevezetőben elmesélt történet az egységes eloszlásról a UnityEngine.Random nem ismétlődött meg: vagy eleve hibás volt, vagy azóta valami megváltozott a motorban. Viszont most már biztosak vagyunk.
Forrás: habr.com
