W rozwoju gier często trzeba powiązać coś z losowością: Unity ma do tego własne Random, a System.Random istnieje równolegle z nim. Kiedyś, w jednym z projektów, odniosłem wrażenie, że oba mogą działać inaczej (chociaż powinny mieć jednolity rozkład).
Wtedy nie wchodziliśmy w szczegóły – wystarczyło, że przejście na System.Random rozwiązało wszystkie problemy. Teraz postanowiliśmy przyjrzeć się temu dokładniej i przeprowadzić małe badanie: jak „stronnicze” lub przewidywalne są RNG i który wybrać. Co więcej, słyszałem już nie raz sprzeczne opinie na temat ich „uczciwości” – spróbujmy ustalić, jak prawdziwe wyniki mają się do deklarowanych.
Krótki program edukacyjny lub czy RNG to w rzeczywistości RNG
Jeśli znasz już generatory liczb losowych, możesz pominąć tę część i przejść do sekcji „Testowanie”.
Liczby losowe (RN) to ciąg liczb generowany przez jakiś losowy (chaotyczny) proces, źródło entropii. Oznacza to, że jest to ciąg, którego elementy nie są ze sobą połączone żadnym prawem matematycznym - nie mają związku przyczynowo-skutkowego.
To, co tworzy SN, nazywa się generatorem liczb losowych (RNG). Wydawałoby się, że wszystko jest elementarne, ale jeśli przejdziemy od teorii do praktyki, to w rzeczywistości wdrożenie algorytmu programowego do generowania takiej sekwencji nie jest takie proste.
Powodem jest brak tego właśnie chaosu w nowoczesnej elektronice użytkowej. Bez niego liczby losowe przestają być losowe, a ich generator zamienia się w zwykłą funkcję z góry ustalonych argumentów. Dla szeregu specjalności w sferze IT jest to poważny problem (np. dla kryptografii), ale dla pozostałych istnieje całkowicie akceptowalne rozwiązanie.
Należy napisać algorytm, który zwracałby, jeśli nie prawdziwie losowe liczby, to możliwie najbardziej do nich zbliżone - tzw. liczby pseudolosowe (PRNG). Algorytm w tym przypadku nazywa się generatorem liczb pseudolosowych (PRNG).
Istnieje kilka możliwości utworzenia PRNG, ale poniższe będą istotne dla każdego:
- Wymagana wstępna inicjalizacja.
PRNG nie ma źródła entropii, więc przed jego użyciem należy określić stan początkowy. Jest on określony jako liczba (lub wektor) i nazywany jest seed (ziarno losowe). Często licznik cykli procesora lub numeryczny odpowiednik czasu systemowego jest używany jako seed.
- Powtarzalność sekwencji.
PRNG jest całkowicie deterministyczny, więc ziarno określone podczas inicjalizacji jednoznacznie determinuje całą przyszłą sekwencję liczb. Oznacza to, że pojedynczy PRNG zainicjowany tym samym ziarnem (w różnych momentach, w różnych programach, na różnych urządzeniach) wygeneruje tę samą sekwencję.
Musisz również znać rozkład prawdopodobieństwa, który charakteryzuje PRNG – jakie liczby wygeneruje i z jakim prawdopodobieństwem. Najczęściej jest to rozkład normalny lub rozkład jednostajny.
Rozkład normalny (po lewej) i rozkład jednostajny (po prawej)
Załóżmy, że mamy uczciwą 24-ścienną kostkę. Jeśli rzucimy nią, prawdopodobieństwo uzyskania 1 wynosi 24/XNUMX (podobnie jak prawdopodobieństwo uzyskania dowolnej innej liczby). Jeśli wykonamy wiele rzutów i zapiszemy wyniki, zauważymy, że wszystkie ściany wypadają mniej więcej z taką samą częstotliwością. W istocie tę kostkę można uznać za równomierny RNG.
A jeśli rzucisz 10 takimi kośćmi na raz i obliczysz wynik? Czy pozostanie on jednolity? Nie. Najczęściej wynik będzie bliski 125 punktom, czyli pewnej średniej wartości. I w efekcie, jeszcze przed rzutem, możesz w przybliżeniu oszacować przyszły wynik.
Powodem jest to, że istnieje największa liczba kombinacji, aby uzyskać średni wynik. Im dalej od niego, tym mniej kombinacji - i, co za tym idzie, tym mniejsze prawdopodobieństwo wypadnięcia. Jeśli te dane zostaną zwizualizowane, będą one niejasno przypominać kształt dzwonu. Dlatego, z pewnym naciągnięciem, system 10 kości można nazwać RNG o rozkładzie normalnym.
Inny przykład, ale już w samolocie - strzelanie do celu. Strzelcem będzie RNG, generujący parę liczb (x, y), która jest wyświetlana na wykresie.
Zgadzam się, że wariant z lewej strony jest bliższy rzeczywistości - to RNG z rozkładem normalnym. Ale jeśli musisz rozproszyć gwiazdy na ciemnym niebie, to wariant z prawej strony, uzyskany za pomocą RNG z rozkładem równomiernym, jest bardziej odpowiedni. Generalnie wybieraj generator w zależności od zadania, które masz do wykonania.
Teraz porozmawiajmy o entropii ciągu liczb losowych. Na przykład, jest ciąg, który zaczyna się tak:
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 rozkładu.
Wygląda na to, że jest to ciąg jednorodny, ale jeśli odczytasz sekwencję po dwie liczby na raz 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 (tj. mają niską entropię), może to generować właśnie to „przesunięcie”. Przynajmniej taki PRNG nie nadaje się 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, …
Wydaje się, że wszystko jest tutaj w porządku, nawet na płaskiej powierzchni:
Przyjrzyjmy się objętości (odczytaj trzy liczby):
I znowu wzory. Nie da się już zbudować wizualizacji w czterech wymiarach. Ale wzory mogą istnieć w tym wymiarze i w większych.
W tej samej kryptografii, w której na PRNG nałożone są najsurowsze wymagania, taka sytuacja jest kategorycznie niedopuszczalna. Dlatego opracowano specjalne algorytmy do oceny ich jakości, których teraz nie będziemy poruszać. Temat jest obszerny i zasługuje na osobny artykuł.
Testowanie
Jeśli czegoś nie wiemy na pewno, jak mamy z tym pracować? Czy powinniśmy przechodzić przez ulicę, jeśli nie wiemy, który sygnał świetlny na to pozwala? Konsekwencje mogą być różne.
To samo dotyczy notorycznej losowości w Unity. Dobrze, jeśli dokumentacja ujawnia niezbędne szczegóły, ale historia wspomniana na początku artykułu wydarzyła się właśnie z powodu braku pożądanych szczegółów.
A bez wiedzy, jak działa narzędzie, nie będziesz w stanie używać go poprawnie. Generalnie, czas sprawdzić i przeprowadzić eksperyment, aby w końcu mieć pewność co do dystrybucji.
Rozwiązanie było proste i skuteczne — zebrać statystyki, uzyskać obiektywne dane i przeanalizować wyniki.
Przedmiot badań
Istnieje kilka sposobów generowania liczb losowych w Unity - przetestowaliśmy pięć.
- System.Random.Next() Generuje liczby całkowite w podanym zakresie wartości.
- System.Random.NextDouble(). Generuje liczby podwójnej precyzji w zakresie [0; 1).
- UnityEngine.Random.Range() Generuje liczby pojedynczej precyzji (float) w podanym zakresie wartości.
- UnityEngine.Random.value Generuje liczby pojedynczej precyzji (float) z zakresu [0; 1).
- Unity.Mathematics.Random.NextFloat(). Część nowej biblioteki Unity.Mathematics. Generuje zmiennoprzecinkowe pojedynczej precyzji w podanym zakresie wartości.
Prawie wszędzie w dokumentacji określono rozkład jednostajny, z wyjątkiem UnityEngine.Random.value (gdzie rozkład nie jest określony, ale przez analogię z UnityEngine.Random.Range(), oczekiwano również rozkładu jednostajnego) i Unity.Mathematics.Random.NextFloat() (która opiera się na algorytmie xorshift, co oznacza, że również należy oczekiwać rozkładu jednostajnego).
Domyślnie oczekiwane wyniki były takie, jakie określono w dokumentacji.
Metodologia
Napisaliśmy małą aplikację, która generuje losowe sekwencje liczb, wykorzystując każdą z zaprezentowanych metod, i przechowuje wyniki w celu dalszego przetwarzania.
Długość każdego ciągu wynosi 100 000 liczb.
Zakres wartości liczb losowych wynosi [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 urządzenia, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, kompilacja na urządzeniu, il2cpp, .NET Standard 2.0
realizacja
Mamy kilka różnych sposobów generowania liczb losowych. Dla każdego z nich napiszemy osobną klasę opakowującą, która powinna zapewnić:
- Możliwość ustawienia zakresu wartości [min/max]. Zostanie ustawiony za pomocą konstruktora.
- Metoda zwracająca SC. Wybierzemy float jako typ, ponieważ jest bardziej ogólny.
- Nazwa metody generowania do oznaczania wyników. Dla wygody zwrócimy pełną nazwę klasy + nazwę metody użytej do wygenerowania SC jako wartość.
Najpierw deklarujemy 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, a potrzebne są liczby zmiennoprzecinkowe. Możesz po prostu interpretować liczby całkowite jako float lub możesz rozszerzyć zakres wartości o kilka rzędów wielkości, kompensując je przy każdym generowaniu SC. Otrzymasz 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()
Oto stały zakres wartości [0; 1). Aby rzutować go na określony w konstruktorze zakres, 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 statycznej klasy UnityEngine.Random pozwala określić zakres wartości i zwraca liczbę losową typu float. Nie są wymagane żadne dodatkowe konwersje.
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 liczbę losową typu float z ustalonego zakresu wartości [0; 1). Rzutujmy ją na podany 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ę losową typu float i pozwala określić zakres wartości. Jedynym zastrzeżeniem 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 MainController
Kilka implementacji IRandomGenerator jest gotowych. Następnie musimy wygenerować sekwencje i zapisać wynikowy zestaw danych do przetworzenia. Aby to zrobić, utworzymy scenę w Unity i mały skrypt MainController, który wykona całą niezbędną pracę i jednocześnie będzie odpowiedzialny za interakcję z UI.
Ustawimy rozmiar zbioru danych i zakres wartości SC, a także uzyskamy metodę zwracającą tablicę skonfigurowanych i gotowych do użycia generatorów.
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)
};
}
...
}
}Teraz tworzymy zbiór danych. W tym przypadku generowanie danych zostanie połączone z rejestrowaniem wyników w strumieniu tekstowym (w formacie csv). Każdy IRandomGenerator ma własną, oddzielną kolumnę do przechowywania wartości, a pierwszy wiersz 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 jedynie wywołać metodę GenerateCsvDataSet i zapisać wynik do pliku lub od razu przesłać dane przez sieć z urządzenia końcowego do odbierającego. Serwer.
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
Nie było żadnego cudu. To, czego się spodziewaliśmy, to to, co dostaliśmy - we wszystkich przypadkach równomierny rozkład bez cienia spisków. Nie widzę sensu dołączania oddzielnych wykresów dla platform - wszystkie pokazują mniej więcej te same wyniki.
Rzeczywistość jest taka:
Wizualizacja sekwencji na płaszczyźnie ze wszystkich pięciu metod generowania:
I wizualizacja w 3D. Zostawię tylko wynik System.Random.Next(), aby nie generować zbioru identycznej zawartości.
Historia opowiedziana we wstępie o rozkładzie normalnym UnityEngine.Random nie powtórzyła się: albo była początkowo błędna, albo coś zmieniło się w silniku od tego czasu. Ale teraz jesteśmy pewni.
Źródło: www.habr.com
