În dezvoltarea de jocuri, este adesea necesar să se folosească ceva legat de întâmplare: Unity are propriul său Random, iar alături de acesta există System.Random. Cu mult timp în urmă, într-unul dintre proiecte, s-a conturat impresia că ambele ar putea funcționa diferit (deși ar trebui să aibă o distribuție uniformă).
Atunci nu am aprofundat detaliile — a fost suficient faptul că trecerea la System.Random a rezolvat toate problemele. Acum am decis să ne lămurim mai bine și să facem o mică cercetare: cât de «părtinitor» sau predictibil este un generator de numere aleatoare și pe care să-l alegem. Mai ales că am auzit de nenumărate ori opinii contradictorii despre «corectitudinea» acestora — vom încerca să înțelegem cum se corelează rezultatele reale cu cele anunțate.
Un scurt ghid sau Ce este, de fapt, un generator de numere aleatoare
Dacă sunteți deja familiarizați cu generatorii de numere aleatoare, puteți să treceți direct la secțiunea «Testare».
Numerele aleatoare (NA) sunt o succesiune de numere generate printr-un anumit proces aleator (haotic), o sursă de entropie. Cu alte cuvinte, aceasta este o astfel de succesiune, a cărei elemente nu sunt legate între ele printr-o normă matematică — nu există o legătură de cauzalitate.
Ceea ce produce numere aleatoare se numește generator de numere aleatoare (GNA). Părea simplu, dar dacă trecem de la teorie la practică, realizarea unui algoritm software pentru generarea unei astfel de succesiuni nu este deloc simplă.
Motivul se află în absența acelei haoticități în electronica de consum modernă. Fără ea, numerele aleatoare încetează să mai fie aleatoare, iar generatorul lor devine o funcție obișnuită a unor argumente deja cunoscute. Pentru o serie de specialități din domeniul IT, aceasta este o problemă serioasă (de exemplu, pentru criptografie), iar pentru celelalte există o soluție acceptabilă.
Trebuie să scriem un algoritm care să returneze numere care, deși poate nu sunt cu adevărat aleatoare, să fie cât mai apropiate de acestea — așa numitele, numere pseudo-aleatoare (PNA). Algoritmul în acest caz se numește generator de numere pseudo-aleatoare (GNPA).
Există mai multe variante de creare a GNPA, dar pentru toate se va aplica următoarea cerință:
- Necesitatea inițializării prealabile.
Un generator de numere aleatorii (GNR) nu are o sursă de entropie, așa că înainte de a fi utilizat, trebuie să i se indice o stare inițială. Aceasta este definită sub formă de număr (sau vector) și se numește seminței (seed, random seed). Adesea, ca seed se folosește un contor de cicluri al procesorului sau echivalentul numeric al timpului sistemului.
- Reproducibilitatea secvenței.
GNR este complet determinist, deci semințea stabilită la inițializare definită în mod unic întreaga secvență viitoare de numere. Aceasta înseamnă că un anumit GNR, inițializat cu aceeași semință (la momente diferite, în programe diferite, pe dispozitive diferite) va genera aceeași secvență.
De asemenea, trebuie să cunoaștem distribuția de probabilitate caracteristică a GNR - ce numere va genera și cu ce probabilitate. Cel mai frecvent aceasta este fie distribuția normală (normal distribution), fie distribuția uniformă (uniform distribution).
Distribuția normală (stânga) și distribuția uniformă (dreapta)
Presupunem că avem un zar corect cu 24 de fețe. Dacă îl aruncăm, probabilitatea de a obține un unu va fi de 1/24 (la fel ca și probabilitatea de a obține orice alt număr). Dacă facem multe aruncări și notăm rezultatele, vom observa că toate fețele apar aproximativ cu aceeași frecvență. În esență, acest zar poate fi considerat un GNR cu distribuție uniformă.
Și dacă aruncăm imediat 10 astfel de zaruri și calculăm suma totală a punctelor? Va păstra uniformitatea? Nu. Cel mai frecvent, suma va fi apropiată de 125 de puncte, adică de o anumită valoare medie. Ca urmare, chiar și înainte de a face aruncarea, putem evalua aproximativ rezultatul viitor.
Motivul este că pentru a obține suma medie a punctelor există cele mai multe combinații. Cu cât ne îndepărtăm de aceasta, cu atât mai puține combinații - și, în consecință, o probabilitate mai mică de apariție. Dacă aceste date sunt vizualizate, vor aminti vag de forma unei clopote. Prin urmare, cu o oarecare strângere de inimă, sistemul format din 10 zaruri poate fi numit un GNR cu distribuție normală.
Un alt exemplu, dar deja în plan - tragerea la țintă. Tragatorul va fi un GNR care generează o pereche de numere (x, y), care este afișată pe grafic.
Sunteți de acord că varianta din stânga este mai apropiată de viața reală – acesta este un GCS cu o distribuție normală. Dar dacă trebuie să împrăștiem stelele pe cerul întunecat, atunci varianta din dreapta, obținută printr-un GCS cu o distribuție uniformă, este mai potrivită. În general, alegeți generatorul în funcție de sarcina de îndeplinit.
Acum să vorbim despre entropia secvenței PCȘ. De exemplu, există o secvență care începe astfel:
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, …
Cât de aleatorii sunt aceste numere, la o primă vedere? Să începem prin verificarea distribuției.
Arată aproape uniform, dar dacă citim secvența doi câte doi și le interpretăm ca coordonate pe un plan, obținem asta:
Devine evident că există modele. Și, având în vedere că datele din secvență sunt ordonate într-un anumit mod (adică au entropie scăzută), aceasta poate genera acea "bias". Cel puțin, acest GCPȘ nu este foarte potrivit pentru a genera coordonate pe plan.
O altă secvență:
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, …
Se pare că aici totul este bine chiar și pe plan:
Să ne uităm în volum (citind trei numere):
Și din nou modele. Nu putem construi o vizualizare în patru dimensiuni. Dar modelele pot exista și în această dimensiune, și în dimensiuni mai mari.
În criptografie, unde GCPȘ-urile trebuie să îndeplinească cele mai stricte cerințe, o astfel de situație este categoric inacceptabilă. De aceea, au fost dezvoltate algoritmi speciali pentru a evalua calitatea acestora, despre care nu ne vom ocupa acum. Subiectul este vast și necesită un articol separat.
Testare
Dacă nu știm ceva cu siguranță, cum să lucrăm cu aceasta? Merită să traversăm strada dacă nu știm ce semafor permite acest lucru? Consecințele pot fi diverse.
Același lucru este valabil și pentru celebra randare în Unity. E bine dacă documentația dezvăluie detaliile necesare, dar povestea menționată la începutul articolului a avut loc exact din lipsa unei clarități dorite.
Dacă nu știi cum funcționează instrumentul, nu vei putea să-l folosești corect. În general, a sosit momentul să verificăm și să facem un experiment pentru a ne asigura măcar în privința distribuției.
Soluția a fost simplă și eficientă — să colectăm statistici, să obținem date obiective și să privim rezultatele.
Subiectul cercetării
În Unity există mai multe modalități de generare a numerelor aleatoare — am testat cinci.
- System.Random.Next(). Generează numere întregi (integer) într-un interval de valori dat.
- System.Random.NextDouble(). Generează numere cu precizie dublă (double) în intervalul de la [0; 1).
- UnityEngine.Random.Range(). Generează numere cu precizie simplă (float) într-un interval de valori dat.
- UnityEngine.Random.value. Generează numere cu precizie simplă (float) în intervalul de la [0; 1).
- Unity.Mathematics.Random.NextFloat(). Parte din noua bibliotecă Unity.Mathematics. Generează numere cu precizie simplă (float) într-un interval de valori dat.
Practically everywhere in the documentation, uniform distribution was indicated, except for UnityEngine.Random.value (where distribution is not specified, but it was also expected to be uniform by analogy with UnityEngine.Random.Range()) and Unity.Mathematics.Random.NextFloat() (where the xorshift algorithm is used, and therefore uniform distribution is expected again).
Prin default, rezultatele așteptate au fost cele specificate în documentație.
Metodologia
Am scris o mică aplicație care genera secvențe de numere aleatoare folosind fiecare dintre metodele prezentate și salvează rezultatele pentru procesare ulterioară.
Lungimea fiecărei secvențe — 100 000 de numere.
Intervalul valorilor numerelor aleatoare — [0, 100).
Datele au fost colectate de pe mai multe platforme țintă:
- Windows
— Unity v2018.3.14f1, modul Editor, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, modul Editor, Mono, .NET Standard 2.0
— Unity v5.6.4p4, modul Editor, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, construcție pe dispozitive, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, construcție pe dispozitive, il2cpp, .NET Standard 2.0
Implementarea
Avem mai multe modalități diferite de generare a numerelor aleatoare. Pentru fiecare dintre ele vom scrie o clasă wrapper separată, care trebuie să ofere:
- Posibilitatea de a stabili un interval de valori [min/max). Acesta va fi setat prin constructor.
- Metodă care returnează un număr aleator. Ca tip vom alege float, fiind mai general.
- Numele modalității de generare pentru etichetarea rezultatelor. Pentru confort, vom returna numele întreg al clasei + numele metodei folosite pentru generarea numărului aleator.
Mai întâi, vom declara o abstractizare care va fi reprezentată de interfața IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementarea System.Random.Next()
Această metodă permite definirea unei game de valori, dar returnează numere întregi (integer), iar noi avem nevoie de float. Se poate interpreta pur și simplu integer ca float sau se poate extinde gama de valori pe câteva ordini, compensându-le la fiecare generare a numărului aleator. Se va obține ceva asemănător cu fixed-point cu o precizie dată de ordin. Vom folosi această variantă, deoarece este mai apropiată de adevărata valoare float.
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;
}
}Implementarea System.Random.NextDouble()
Aici este o gamă fixă de valori [0; 1). Pentru a o proiecta pe cea definită în constructor, vom folosi o aritmetică simplă: 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;
}
}Implementarea UnityEngine.Random.Range()
Această metodă a clasei statice UnityEngine.Random permite definirea unei game de valori și returnează numere aleatoare de tip float. Nu va fi nevoie să efectuați alte conversii.
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);
}
}Implementarea UnityEngine.Random.value
Proprietatea value a clasei statice UnityEngine.Random returnează un număr aleator de tip float dintr-o gamă fixă de valori [0; 1). O vom proiecta pe gama definită într-un mod similar cu implementarea 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;
}
}Implementarea Unity.Mathematics.Random.NextFloat()
Metoda NextFloat() a clasei Unity.Mathematics.Random returnează un tip float și permite stabilirea unui interval de valori. Singurul detaliu este că fiecare instanță a Unity.Mathematics.Random trebuie inițializată cu o anumită sămânță — astfel evităm generarea de secvențe repetitive.
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);
}
}Implementarea MainController
Mai multe implementări ale IRandomGenerator sunt gata. Următorul pas este generarea secvențelor și salvarea setului de date rezultat pentru procesare. Pentru aceasta, vom crea în Unity o scenă și un mic script MainController, care va efectua toată lucrarea necesară și va răspunde de interacțiunea cu UI.
Să stabilim dimensiunea setului de date și intervalul de valori pentru float, și de asemenea să ne dotăm cu o metodă care returnează un array de generatoare configurate și gata de utilizare.
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)
};
}
...
}
}Acum generăm setul de date. În acest caz, generarea datelor va fi combinată cu înregistrarea rezultatelor într-un flux text (în format csv). Fiecare IRandomGenerator va avea alocat un coloană separată, iar prima linie va conține numele generatorului.
namespace RandomDistribution
{
public class MainController : MonoBehaviour
{
...
private void GenerateCsvDataSet(TextWriter writer, int dataSetSize, params IRandomGenerator[] generators)
{
const char separator = ',';
int lastIdx = generators.Length - 1;
// scrie antetul
for (int j = 0; j <= lastIdx; j++)
{
writer.Write(generators[j].Name);
if (j != lastIdx)
writer.Write(separator);
}
writer.WriteLine();
// scrie datele
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();
}
}
...
}
}Rămâne de apelat metoda GenerateCsvDataSet și de salvat rezultatul într-un fișier, sau de transmis datele imediat prin rețea de pe dispozitivul final către cel ce primește. serverul.
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();
}
}
...
}
}Sursele proiectului se află pe .
Rezultate
Minunea nu s-a întâmplat. Ceea ce ne-am așteptat, am și primit — în toate cazurile distribuție uniformă fără un indiciu de conspirații. Nu văd rostul să atașez grafice pentru platforme separate — toate arată rezultate aproximativ aceleași.
Realitatea este următoarea:
Vizualizarea secvențelor pe plane din toate cele cinci metode de generare:
Și vizualizarea în 3D. Voi lăsa doar rezultatul System.Random.Next(), pentru a nu crea o mulțime de conținut identic.
Povestea spusă în introducere despre distribuția normală a UnityEngine.Random nu s-a repetat: fie a fost inițial eronată, fie ceva s-a schimbat între timp în motor. Dar acum suntem siguri.
Sursa: habr.com
