Pelien kehittämisessä joudutaan usein turvautumaan satunnaisuuteen: Unitylla on tähän oma Random-funktionsa, ja System.Random on olemassa sen rinnalla. Kauan sitten eräässä projektissa sain vaikutelman, että nämä kaksi saattaisivat toimia eri tavalla (vaikka niiden pitäisi olla jakauman tasaisia).
Emme menneet yksityiskohtiin silloin – riitti, että siirtyminen System.Random-järjestelmään korjasi kaikki ongelmat. Nyt olemme päättäneet tarkastella asiaa lähemmin ja tehdä pienen tutkimuksen: kuinka "puolueellisia" tai ennustettavia satunnaislukugeneraattorit ovat ja minkä niistä valita. Lisäksi olen kuullut ristiriitaisia mielipiteitä niiden "oikeudenmukaisuudesta" useammin kuin kerran – yritetään selvittää, miten todelliset tulokset vertautuvat väitteisiin.
Lyhyt johdanto satunnaislukugeneraattoriin (RNG) vai onko se oikeasti satunnaislukugeneraattori?
Jos olet jo perehtynyt satunnaislukugeneraattoreihin, voit siirtyä "Testaus"-osioon.
Satunnaisluvut (RN) ovat satunnaisen (kaoottisen) prosessin generoimia lukusarjoja, jotka ovat entropian lähde. Toisin sanoen ne ovat lukusarjoja, joiden alkiot eivät ole yhteydessä toisiinsa minkään matemaattisen lain mukaan – niillä ei ole syy-seuraussuhdetta.
Satunnaislukugeneraattorin (RNG) luovaa menetelmää kutsutaan satunnaislukugeneraattoriksi (RNG). Vaikka tämä vaikuttaa yksinkertaiselta, teorian soveltaminen käytäntöön osoittaa, että ohjelmistoalgoritmin toteuttaminen tällaisen sekvenssin luomiseksi ei ole niin suoraviivaista.
Syynä on juuri tämän satunnaisuuden puuttuminen nykyaikaisesta kulutuselektroniikasta. Ilman sitä satunnaisluvut lakkaavat olemasta satunnaisia, ja niiden generaattorista tulee yksinkertainen ennalta määrättyjen syötteiden funktio. Useille IT-ammateille (esimerkiksi kryptografia) tämä on vakava ongelma, mutta toisille on olemassa täysin hyväksyttävä ratkaisu.
Meidän täytyy kirjoittaa algoritmi, joka palauttaa lukuja, jotka eivät ole aidosti satunnaisia, mutta ovat mahdollisimman lähellä niitä – niin sanottuja pseudosatunnaisia lukuja (PRNG). Tässä tapauksessa algoritmia kutsutaan pseudosatunnaislukugeneraattoriksi (PRNG).
PRNG:n luomiseen on useita vaihtoehtoja, mutta seuraavat ovat merkityksellisiä kaikille:
- Esialustuksen tarve.
PRNG:llä ei ole entropialähdettä, joten alkutila on määritettävä ennen käyttöä. Tämä alkutila määritetään numerona (tai vektorina) ja sitä kutsutaan siemeneksi (satunnaissiemen). Siemenenä käytetään usein prosessorin syklilaskuria tai järjestelmän ajan numeerista vastinetta.
- Sekvenssin toistettavuus.
PRNG on täysin deterministinen, joten alustuksen aikana määritetty siemenarvo määrittää yksikäsitteisesti koko tulevan numerosarjan. Tämä tarkoittaa, että yksi PRNG, joka on alustettu samalla siemenarvolla (eri aikoina, eri ohjelmissa, eri laitteilla), luo saman sarjan.
Sinun on myös tiedettävä PRNG:lle ominaisen todennäköisyysjakauman eli mitä lukuja se tuottaa ja millä todennäköisyydellä. Useimmiten tämä on joko normaalijakauma tai tasainen jakauma.
Normaalijakauma (vasen) ja tasainen jakauma (oikea)
Oletetaan, että meillä on reilu 24-sivuinen noppa. Jos heitämme sitä, todennäköisyys osua lukuun 1 on 1/24 (aivan kuten todennäköisyys osua mihin tahansa muuhun lukuun). Jos teemme useita heittoja ja kirjaamme tulokset muistiin, huomaamme, että kaikki 24-sivuiset nopat osuvat suunnilleen samalla taajuudella. Pohjimmiltaan tätä noppaa voidaan pitää tasaisesti jakautuneena satunnaislukugeneraattorina.
Entä jos heität kerralla 10 tällaista noppaa ja lasket kokonaispistemäärän? Pysyykö se tasaisena? Ei. Useimmiten pistemäärä on lähellä 125 pistettä eli jonkin keskiarvon. Tämän seurauksena voit karkeasti arvioida tulevan tuloksen jo ennen nopan heittämistä.
Syynä on se, että keskimääräisen pistemäärän saavuttamiseksi on olemassa eniten yhdistelmiä. Mitä kauempana keskiarvosta ollaan, sitä vähemmän yhdistelmiä on – ja sitä pienempi on heiton todennäköisyys. Jos nämä tiedot visualisoitaisiin, ne muistuttaisivat etäisesti kellon muotoa. Siksi pienellä venyttelyllä 10 nopan järjestelmää voitaisiin kutsua normaalijakautuneeksi satunnaislukugeneraattoriksi.
Toinen esimerkki, tällä kertaa lentokoneessa, on ammunta kohteeseen. Ampuja on satunnaislukugeneraattori (RNG), joka luo numeroparin (x, y), joka näytetään kaaviossa.
Olet varmasti samaa mieltä siitä, että vasemmanpuoleinen variantti on lähempänä todellista elämää – se on satunnaislukugeneraattori, jolla on normaalijakauma. Mutta jos sinun täytyy sirotella tähtiä tummalle taivaalle, oikeanpuoleinen variantti, joka saadaan käyttämällä tasaisesti jakautunutta satunnaislukugeneraattoria, olisi sopivampi. Lyhyesti sanottuna, valitse generaattori käsillä olevan tehtävän perusteella.
Puhutaanpa nyt satunnaislukujonon entropiasta. Esimerkiksi on olemassa jono, joka alkaa näin:
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, …
Kuinka satunnaisia nämä luvut ovat ensi silmäyksellä? Aloitetaan tarkistamalla jakauma.
Se näyttää lähes yhtenäiseltä, mutta jos luet kahden numeron sarjan ja tulkitset ne tasokoordinaateiksi, saat tämän:
Kuviot tulevat selvästi näkyviin. Ja koska sekvenssin data on järjestetty tietyllä tavalla (eli sillä on alhainen entropia), tämä voi tuottaa aivan saman "harhan". Ainakin tällainen PRNG ei ole kovin sopiva koordinaattien luomiseen tasossa.
Toinen järjestys:
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, …
Näyttää siltä, että kaikki on täällä hyvin, jopa tasaisella alustalla:
Katsotaanpa äänenvoimakkuutta (lue kolme numeroa):
Ja jälleen kerran, kuviot. Visualisointi neljässä ulottuvuudessa ei ole enää mahdollista. Mutta kuvioita voi olla tässä ulottuvuudessa ja korkeammissa ulottuvuuksissa.
Kryptografiassa, jossa PRNG-koodeille asetetaan tiukimmat vaatimukset, tällainen tilanne on täysin mahdotonta hyväksyä. Siksi niiden laadun arvioimiseksi on kehitetty erityisiä algoritmeja, joita emme käsittele tässä. Aihe on laaja ja ansaitsee erillisen artikkelin.
Testaus
Jos emme tiedä jostakin asiasta varmasti, miten voimme käsitellä sitä? Pitäisikö meidän ylittää tie, jos emme tiedä, mitkä liikennevalot sen sallivat? Seuraukset voivat vaihdella.
Sama pätee Unityn pahamaineiseen satunnaisuuteen. On hienoa, jos dokumentaatio tarjoaa tarvittavat yksityiskohdat, mutta artikkelin alussa mainittu tapaus johtui juuri halutun spesifisyyden puutteesta.
Ja tietämättä, miten työkalu toimii, et voi käyttää sitä oikein. Joten on aika testata sitä ja suorittaa koe varmistaaksesi vihdoin ainakin jakauman.
Ratkaisu oli yksinkertainen ja tehokas: kerätä tilastoja, hankkia objektiivista dataa ja tarkastella tuloksia.
Tutkimuksen aihe
Unityssa on useita tapoja luoda satunnaislukuja – testasimme viittä.
- System.Random.Next(). Luo kokonaislukuja annetun arvoalueen sisällä.
- System.Random.NextDouble(). Luo kaksinkertaisen tarkkuuden omaavia lukuja väliltä [0; 1).
- UnityEngine.Random.Range(). Luo yhden tarkkuuden lukuja (liukulukuja) annetun arvoalueen sisällä.
- UnityEngine.Random.value. Luo yhden tarkkuuden lukuja (liukulukuja) väliltä [0; 1).
- Unity.Mathematics.Random.NextFloat(). Osa uutta Unity.Mathematics-kirjastoa. Luo yhden tarkkuuden liukulukuja tietyllä alueella.
Lähes kaikkialla dokumentaatiossa määriteltiin tasainen jakauma, lukuun ottamatta UnityEngine.Random.value-funktiota (jossa jakaumaa ei ole määritelty, mutta analogisesti UnityEngine.Random.Range()-funktion kanssa odotettiin myös tasaista jakaumaa) ja Unity.Mathematics.Random.NextFloat()-funktiota (joka perustuu xorshift-algoritmiin, mikä tarkoittaa, että jälleen odotetaan tasaista jakaumaa).
Oletusarvoisesti odotetut tulokset olivat dokumentaatiossa määritetyt.
tekniikka
Kirjoitimme pienen sovelluksen, joka generoi satunnaislukusarjoja käyttämällä kutakin esitettyä menetelmää ja tallensi tulokset jatkokäsittelyä varten.
Kunkin sekvenssin pituus on 100 000 numeroa.
Satunnaislukujen arvojen alue on [0, 100].
Dataa kerättiin useilta kohdealustoilta:
- Windows
— Unity v2018.3.14f1, editoritila, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, editoritila, Mono, .NET Standard 2.0
— Unity v5.6.4p4, editoritila, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, laitteen koontiversio, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, laitteen koontiversio, il2cpp, .NET Standard 2.0
Реализация
Meillä on useita eri tapoja luoda satunnaislukuja. Jokaista tapaa varten kirjoitamme erillisen kääreluokan, jonka tulisi tarjota:
- Mahdollisuus määrittää arvoalue [min/max]. Arvo asetetaan konstruktorin kautta.
- Metodi, joka palauttaa luvun. Valitsemme tyypiksi float, koska se on yleisempi.
- Tulosten merkitsemiseen käytettävän luontimenetelmän nimi. Mukavuussyistä palautamme arvona koko luokan nimen + SC:n luomiseen käytetyn metodin nimen.
Ensin määritellään abstraktio, jota edustaa IRandomGenerator-rajapinta:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}System.Random.Next()-funktion toteutus
Tämän metodin avulla voit määrittää arvoalueen, mutta se palauttaa kokonaislukuja, kun taas liukulukuja vaaditaan. Voit tulkita kokonaisluvun liukulukuksi tai laajentaa arvoaluetta useilla suuruusluokilla kompensoiden niitä aina, kun taajuus generoidaan. Tämä johtaa kiinteän pisteen kaltaiseen arvoon, jolla on tietty tarkkuusluokka. Käytämme tätä vaihtoehtoa, koska se on lähempänä todellista liukulukua.
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;
}
}System.Random.NextDouble()-funktion toteutus
Tässä kiinteä arvoalue on [0; 1). Sen projisoimiseksi konstruktorissa määritettyyn arvoalueeseen käytämme yksinkertaista aritmetiikkaa: 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;
}
}UnityEngine.Random.Range()-funktion toteutus
Tämä staattisen UnityEngine.Random-luokan metodi antaa sinun määrittää arvoalueen ja palauttaa liukulukutyyppisen satunnaisluvun. Lisämuunnoksia ei tarvita.
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);
}
}UnityEngine.Random.value-funktion toteutus
Staattisen luokan UnityEngine.Random value-ominaisuus palauttaa liukulukutyyppisen satunnaisluvun kiinteältä arvoväliltä [0; 1]. Projisoimme sen annetulle arvovälille samalla tavalla kuin System.Random.NextDouble()-funktion toteutuksessa.
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;
}
}Unity.Mathematics.Random.NextFloat()-funktion toteutus
Unity.Mathematics.Random-luokan NextFloat()-metodi palauttaa liukulukuisen satunnaisluvun ja antaa sinun määrittää arvoalueen. Ainoa rajoitus on, että jokainen Unity.Mathematics.Random-luokan instanssi on alustettava siemenellä – tämä estää kaksoiskappaleiden luomisen.
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);
}
}MainControllerin toteutus
Useita IRandomGenerator-toteutuksia on valmiina. Seuraavaksi meidän on luotava sekvenssejä ja tallennettava tuloksena oleva datajoukko käsittelyä varten. Tätä varten luomme Unity-skenen ja pienen MainController-skriptin, joka suorittaa kaikki tarvittavat työt ja käsittelee käyttöliittymän vuorovaikutuksen.
Määrittelemme datajoukon koon ja taajuusarvojen alueen ja luomme myös metodin, joka palauttaa taulukon konfiguroituja ja käyttövalmiita generaattoreita.
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)
};
}
...
}
}Nyt luomme datasetin. Tässä tapauksessa datan luominen yhdistetään tulosten kirjoittamiseen tekstivirtaan (CSV-muodossa). Jokaisella IRandomGeneratorilla on oma sarake, ja ensimmäinen rivi sisältää generaattorin nimen.
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();
}
}
...
}
}Jäljelle jää vain kutsua GenerateCsvDataSet-metodia ja tallentaa tulos tiedostoon tai siirtää tiedot välittömästi verkon kautta päätelaitteelta vastaanottavalle laitteelle. palvelin.
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();
}
}
...
}
}Hankkeen lähteet sijaitsevat osoitteessa .
Tulokset
Mitään ihmettä ei tapahtunut. Saimme odotetun tuloksen – tasaisen jakauman kaikissa tapauksissa ilman vihjettäkään salaliitosta. En näe järkeä liittää mukaan erillisiä alustakaavioita – ne kaikki näyttävät suunnilleen samat tulokset.
Todellisuus on tämä:
Sekvenssien visualisointi tasossa kaikilla viidellä generointimenetelmällä:
Ja 3D-visualisointi. Jätän vain System.Random.Next()-funktion tuloksen, jotta vältytään samanlaisen sisällön luomiselta.
Johdannossa kerrottu tarina UnityEngine.Random-moottorin normaalijakaumasta ei toistunut: joko siinä oli alusta asti virheitä tai moottorissa oli jotain muuttunut sen jälkeen. Mutta nyt olemme luottavaisia.
Lähde: will.com
