Podczas tworzenia gier często trzeba powiązać coś z losowością: Unity ma do tego swój własny Random i równolegle z nim istnieje System.Random. Któregoś razu przy jednym z projektów odniosłem wrażenie, że oba mogłyby działać inaczej (choć powinny mieć równy rozkład).
Potem nie wdawali się w szczegóły – wystarczyło, że przejście na System.Random rozwiązało wszystkie problemy. Teraz postanowiliśmy przyjrzeć się temu bardziej szczegółowo i przeprowadzić małe badanie: jak „stronnicze” lub przewidywalne są RNG i który wybrać. Co więcej, niejednokrotnie słyszałem sprzeczne opinie na temat ich „uczciwości” - spróbujmy dowiedzieć się, jak rzeczywiste wyniki mają się do deklarowanych.
Krótki program edukacyjny lub RNG to tak naprawdę RNG
Jeśli znasz już generatory liczb losowych, możesz od razu przejść do sekcji „Testowanie”.
Liczby losowe (RN) to ciąg liczb generowany przy użyciu jakiegoś losowego (chaotycznego) procesu, będącego źródłem entropii. Oznacza to, że jest to ciąg, którego elementy nie są ze sobą powiązane żadnym prawem matematycznym - nie mają związku przyczynowo-skutkowego.
To, co tworzy liczbę losową, nazywa się generatorem liczb losowych (RNG). Wydawać by się mogło, że wszystko jest elementarne, jednak jeśli przejdziemy od teorii do praktyki, to w rzeczywistości zaimplementowanie algorytmu programowego generującego taką sekwencję nie jest takie proste.
Powodem jest brak tego samego chaosu we współczesnej elektronice użytkowej. Bez tego liczby losowe przestają być losowe, a ich generator zamienia się w zwykłą funkcję o jasno określonych argumentach. Dla wielu specjalności z branży IT jest to poważny problem (na przykład kryptografia), ale dla innych jest to całkowicie akceptowalne rozwiązanie.
Należy napisać algorytm, który zwracałby, choć nie liczby prawdziwie losowe, ale jak najbardziej do nich zbliżone – tzw. liczby pseudolosowe (PRN). Algorytm w tym przypadku nazywany jest generatorem liczb pseudolosowych (PRNG).
Istnieje kilka opcji tworzenia PRNG, ale poniższe będą istotne dla każdego:
- Konieczność wstępnej inicjalizacji.
PRNG nie ma źródła entropii, dlatego przed użyciem należy mu nadać stan początkowy. Jest on określony jako liczba (lub wektor) i nazywany jest ziarnem (nasionem losowym). Często licznik zegara procesora lub liczbowy odpowiednik czasu systemowego jest używany jako materiał siewny.
- Powtarzalność sekwencji.
PRNG jest całkowicie deterministyczny, więc ziarno określone podczas inicjalizacji jednoznacznie określa całą przyszłą sekwencję liczb. Oznacza to, że oddzielny PRNG zainicjowany tym samym ziarnem (w różnym czasie, w różnych programach, na różnych urządzeniach) wygeneruje tę samą sekwencję.
Trzeba także znać rozkład prawdopodobieństwa charakteryzujący PRNG – jakie liczby wygeneruje i z jakim prawdopodobieństwem. Najczęściej jest to rozkład normalny lub rozkład równomierny.
Rozkład normalny (po lewej) i rozkład równomierny (po prawej)
Załóżmy, że mamy uczciwą kość z 24 stronami. Jeśli rzucisz, prawdopodobieństwo wylosowania jedynki będzie równe 1/24 (tak samo jak prawdopodobieństwo wylosowania dowolnej innej liczby). Jeśli wykonasz wiele rzutów i zapiszesz wyniki, zauważysz, że wszystkie krawędzie wypadają z mniej więcej taką samą częstotliwością. Zasadniczo tę kość można uznać za RNG o równomiernym rozkładzie.
A co jeśli rzucisz 10 takich kostek na raz i policzysz wszystkie punkty? Czy zostanie w tym zakresie zachowana jednolitość? NIE. Najczęściej będzie to kwota zbliżona do 125 punktów, czyli do jakiejś średniej wartości. W rezultacie jeszcze przed wykonaniem rzutu możesz z grubsza oszacować przyszły wynik.
Powodem jest to, że istnieje największa liczba kombinacji, aby uzyskać średni wynik. Im dalej od tego, tym mniej kombinacji - i odpowiednio, tym mniejsze prawdopodobieństwo straty. Jeśli te dane zostaną zwizualizowane, będą one niejasno przypominać kształt dzwonu. Dlatego przy pewnym rozciągnięciu układ 10 kości można nazwać RNG o rozkładzie normalnym.
Inny przykład, tylko tym razem w samolocie - strzelanie do celu. Strzelcem będzie RNG, który generuje parę liczb (x, y), które są wyświetlane na wykresie.
Zgadzam się, że opcja po lewej stronie jest bliższa prawdziwemu życiu - jest to RNG z rozkładem normalnym. Ale jeśli chcesz rozproszyć gwiazdy na ciemnym niebie, lepiej nadaje się odpowiednia opcja, uzyskana za pomocą RNG o równomiernym rozkładzie. Ogólnie rzecz biorąc, wybierz generator w zależności od wykonywanego zadania.
Porozmawiajmy teraz o entropii sekwencji PNG. Na przykład istnieje sekwencja rozpoczynająca się w ten sposób:
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, ...
Jak losowe są te liczby na pierwszy rzut oka? Zacznijmy od sprawdzenia dystrybucji.
Wygląda prawie identycznie, ale jeśli odczytasz sekwencję dwóch liczb i zinterpretujesz je jako współrzędne na płaszczyźnie, otrzymasz to:
Wzory stają się wyraźnie widoczne. A ponieważ dane w sekwencji są uporządkowane w określony sposób (to znaczy mają niską entropię), może to powodować właśnie tę „stronniczość”. Przynajmniej taki PRNG nie jest zbyt odpowiedni do generowania współrzędnych na płaszczyźnie.
Inna sekwencja:
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, ...
Tutaj wszystko wydaje się być w porządku, nawet w samolocie:
Spójrzmy na objętość (czytaj trzy liczby na raz):
I znowu wzory. Nie da się już skonstruować wizualizacji w czterech wymiarach. Ale wzorce mogą istnieć w tym wymiarze i w większych.
W kryptografii, gdzie na PRNG stawiane są najbardziej rygorystyczne wymagania, taka sytuacja jest kategorycznie niedopuszczalna. Dlatego opracowano specjalne algorytmy oceniające ich jakość, o czym nie będziemy się teraz poruszać. Temat jest obszerny i zasługuje na osobny artykuł.
Testowanie
Jeśli nie wiemy czegoś na pewno, to jak z tym pracować? Czy warto przechodzić przez jezdnię, jeśli nie wiemy, które światła na to pozwalają? Konsekwencje mogą być różne.
To samo dotyczy notorycznej losowości w Unity. Dobrze, jeśli dokumentacja ujawnia niezbędne szczegóły, jednak historia wspomniana na początku artykułu wydarzyła się właśnie z powodu braku pożądanych konkretów.
A jeśli nie wiesz, jak działa to narzędzie, nie będziesz w stanie go poprawnie używać. Generalnie przyszedł czas na sprawdzenie i przeprowadzenie eksperymentu, aby w końcu upewnić się przynajmniej co do rozkładu.
Rozwiązanie było proste i skuteczne – zbieraj statystyki, zdobywaj obiektywne dane i przyglądaj się wynikom.
Przedmiot badań
Istnieje kilka sposobów generowania liczb losowych w Unity — przetestowaliśmy pięć.
- System.Losowy.Następny(). Generuje liczby całkowite z danego zakresu wartości.
- System.Losowy.NextDouble(). Generuje liczby o podwójnej precyzji w zakresie od [0; 1).
- UnityEngine.Random.Range(). Generuje liczby o pojedynczej precyzji (zmiennoprzecinkowe) w danym zakresie wartości.
- UnityEngine.Losowa.wartość. Generuje liczby o pojedynczej precyzji (zmiennoprzecinkowe) w zakresie od [0; 1).
- Unity.Mathematics.Random.NextFloat(). Część nowej biblioteki Unity.Mathematics. Generuje liczby o pojedynczej precyzji (zmiennoprzecinkowe) w danym zakresie wartości.
Niemal wszędzie w dokumentacji podano rozkład jednolity, z wyjątkiem UnityEngine.Random.value (gdzie rozkładu nie podano, ale przez analogię z UnityEngine.Random.Range() oczekiwano również uniformu) i Unity.Mathematics.Random .NextFloat() (gdzie w podstawie znajduje się algorytm xorshift, co oznacza, że znowu trzeba poczekać na rozkład równomierny).
Domyślnie za oczekiwane wyniki przyjęto takie, jakie podano w dokumentacji.
Metodologia
Napisaliśmy małą aplikację, która generowała ciągi liczb losowych każdą z przedstawionych metod i zapisywała wyniki do dalszej obróbki.
Długość każdej sekwencji wynosi 100 000 liczb.
Zakres liczb losowych to [0, 100).
Dane zebrano z kilku platform docelowych:
- Windows
— Unity v2018.3.14f1, tryb edytora, mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, tryb edytora, mono, .NET Standard 2.0
— Unity v5.6.4p4, tryb edytora, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, kompilacja na urządzenie, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, kompilacja na urządzenie, il2cpp, .NET Standard 2.0
realizacja
Mamy kilka różnych sposobów generowania liczb losowych. Dla każdego z nich napiszemy osobną klasę wrapperową, która powinna udostępniać:
- Możliwość ustawienia zakresu wartości [min/max]. Zostanie ustawiony przez konstruktora.
- Metoda zwracająca MF. Jako typ wybierzmy float, ponieważ jest on bardziej ogólny.
- Nazwa metody generowania oznaczania wyników. Dla wygody zwrócimy jako wartość pełną nazwę klasy + nazwę metody użytej do wygenerowania MF.
Najpierw zadeklarujmy abstrakcję, która będzie reprezentowana przez interfejs IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implementacja System.Random.Next()
Ta metoda pozwala ustawić zakres wartości, ale zwraca liczby całkowite, ale potrzebne są liczby zmiennoprzecinkowe. Można po prostu zinterpretować liczbę całkowitą jako liczbę zmiennoprzecinkową lub można rozszerzyć zakres wartości o kilka rzędów wielkości, kompensując je z każdą generacją średnicy. Rezultatem będzie coś w rodzaju punktu stałego o określonym rzędzie dokładności. Użyjemy tej opcji, ponieważ jest ona bliższa rzeczywistej wartości 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;
}
}Implementacja System.Random.NextDouble()
Tutaj ustalony zakres wartości [0; 1). Aby rzutować to na podane w konstruktorze, używamy prostej arytmetyki: 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;
}
}Implementacja UnityEngine.Random.Range()
Ta metoda klasy statycznej UnityEngine.Random pozwala ustawić zakres wartości i zwraca typ zmiennoprzecinkowy. Nie musisz wykonywać żadnych dodatkowych przekształceń.
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);
}
}Implementacja UnityEngine.Random.value
Właściwość value klasy statycznej UnityEngine.Random zwraca typ zmiennoprzecinkowy ze stałego zakresu wartości [0; 1). Rzutujmy to na zadany zakres w taki sam sposób, jak przy implementacji 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;
}
}Implementacja Unity.Mathematics.Random.NextFloat()
Metoda NextFloat() klasy Unity.Mathematics.Random zwraca liczbę zmiennoprzecinkową typu float i umożliwia określenie zakresu wartości. Jedynym niuansem jest to, że każda instancja Unity.Mathematics.Random będzie musiała zostać zainicjowana jakimś ziarnem – w ten sposób unikniemy generowania powtarzających się sekwencji.
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);
}
}Implementacja MainControllera
Gotowych jest kilka implementacji IRandomGenerator. Następnie musisz wygenerować sekwencje i zapisać powstały zbiór danych do przetworzenia. W tym celu utworzymy w Unity scenę i mały skrypt MainController, który wykona całą niezbędną pracę i jednocześnie będzie odpowiedzialny za interakcję z interfejsem użytkownika.
Ustalmy rozmiar zbioru danych i zakres wartości MF, a także uzyskajmy metodę, która zwróci tablicę generatorów skonfigurowanych i gotowych do pracy.
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)
};
}
...
}
}Stwórzmy teraz zbiór danych. W tym przypadku generowanie danych będzie połączone z zapisem wyników w strumieniu tekstowym (w formacie csv). Aby przechowywać wartości każdego IRandomGenerator, przydzielana jest osobna kolumna, a pierwsza linia zawiera nazwę generatora.
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();
}
}
...
}
}Pozostaje tylko wywołać metodę GenerateCsvDataSet i zapisać wynik do pliku lub od razu przesłać dane przez sieć z urządzenia końcowego na serwer odbierający.
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();
}
}
...
}
}Źródła projektu znajdują się pod adresem .
wyniki
Żaden cud się nie wydarzył. Oczekiwali tego, co otrzymali – we wszystkich przypadkach równą dystrybucję bez cienia spisku. Nie widzę sensu umieszczania oddzielnych wykresów dla platform – wszystkie pokazują w przybliżeniu te same wyniki.
Rzeczywistość jest taka:
Wizualizacja sekwencji na płaszczyźnie ze wszystkich pięciu metod generacji:
Oraz wizualizacja w 3D. Zostawię tylko wynik System.Random.Next(), aby nie tworzyć wielu identycznych treści.
Opowiedziana we wstępie historia o normalnej dystrybucji UnityEngine. Random się nie powtórzyła: albo początkowo była błędna, albo coś od tego czasu zmieniło się w silniku. Ale teraz jesteśmy tego pewni.
Źródło: www.habr.com