В геймдеве често трябва нещо да се свърже с произволност: в Unity за това има собствен Random, а паралелно с него съществува System.Random. Някога, на един от проектите, се създаде впечатление, че и двата могат да работят по различен начин (въпреки че трябва да имат равномерно разпределение).
Не се задълбочихме в детайли — достатъчно бе, че преминаването на System.Random реши всички проблеми. Сега решихме да се задълбочим и да проведем малко изследване: колко "пристрастени" или предсказуеми са генераторите на случайни числа и кой да изберем. Тем повече, че не веднъж съм чувал противоречиви мнения за тяхната "честност" — ще опитаме да разберем как реалните резултати се отнасят към заявените.
Кратък ликбез или Какво всъщност е генератор на случайни числа
Ако вече сте запознати с генераторите на случайни числа, можете веднага да преминете към раздела "Тестиране".
Случайните числа (СЧ) са последователност от числа, генерирани с помощта на някакъв произволен (хаотичен) процес, източник на ентропия. Тоест, това е такава последователност, елементите на която не са свързани помежду си с никакъв математически закон — те нямат причинно-следствена връзка.
Това, което създава СЧ, се нарича генератор на случайни числа (ГСЧ). Изглежда, всичко е елементарно, но ако преминем от теория към практика, наистина реализирането на програмния алгоритъм за генериране на такава последователност не е толкова просто.
Причината се крие в отсъствието на онзи хаос в съвременната потребителска електроника. Без него случайните числа спират да бъдат случайни, а техният генератор се преобразува в обикновена функция от определени аргументи. За цяла група специалности в ИТ сферата това е сериозен проблем (например за криптографията); за останалите обаче има напълно приемливо решение.
Необходимо е да се напише алгоритъм, който да връща макар и неистински случайни числа, но максимално близки до тях — така наречените псевдослучайни числа (ПСЧ). Алгоритъмът в този случай се нарича генератор на псевдослучайни числа (ГПСЧ).
Има няколко варианта за създаване на ГПСЧ, но за всички ще бъде актуално следното:
- Необходимост от предварителна инициализация.
Генераторът на случайни числа (ГПСЧ) няма източник на ентропия, затова преди да се използва, е необходимо да се зададе начално състояние. То се определя под формата на число (или вектор) и се нарича семе (seed, random seed). Често за семе се използва брояч на тактовете на процесора или числовият еквивалент на системното време.
- Възпроизвеждаемост на последователността.
ГПСЧ е напълно детерминиран, затова зададеното при инициализацията семе еднозначно определя цялата бъдеща последователност от числа. Това означава, че даден ГПСЧ, инициализиран с едно и също семе (в различно време, в различни програми, на различни устройства), ще генерира същата последователност.
Също така е необходимо да се знае характерното за ГПСЧ разпределение на вероятностите – какви числа ще генерира и с каква вероятност. Най-често това е или нормално разпределение (normal distribution), или равномерно разпределение (uniform distribution).
Нормално разпределение (вляво) и равномерно разпределение (вдясно)
Да предположим, че имаме честен зар с 24 грани. Ако го хвърлим, вероятността да се падне единица е 1/24 (както и вероятността да се падне всяко друго число). Ако извършим множество хвърляния и запишем резултатите, можем да забележим, че всички грани се падат приблизително с еднаква честота. Всъщност, този зар може да се счита за ГПСЧ с равномерно разпределение.
А какво ако хвърлим веднага 10 от тези зарове и изчислим общата сума на точките? Ще запази ли тя равномерността? Не. Най-често сумата ще бъде близка до 125 точки, т.е. към някаква средна стойност. И следователно, още преди хвърлянето можем да оценим приблизителния бъдещ резултат.
Причината е, че за получаване на средната сума на точките съществува най-голям брой комбинации. Колкото по-далеч от нея, толкова по-малко комбинации – и съответно, по-малка вероятност да се падне. Ако тези данни се визуализират, те ще наподобяват форма на звънец. Затова с известна нагласа, системата от 10 зара може да се нарече ГПСЧ с нормално разпределение.
Още един пример, но вече в две измерения – стрелба по мишена. Стрелецът ще бъде ГПСЧ, генериращ двойка числа (x, y), които се отразяват на графиката.
Съгласете се, че вариантът отляво е по-близо до реалността — това е ГСЧ с нормално разпределение. Но ако трябва да разпръснете звездите в тъмното небе, тогава десният вариант, получен посредством ГСЧ с равномерно разпределение, е по-подходящ. Изобщо, изберете генератор в зависимост от поставената задача.
Сега да поговорим за ентропията на последователността на ПСЧ. Например, има последователност, която започва така:
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, …
Насколько случайни изглеждат тези числа на пръв поглед? Нека започнем с проверка на разпределението.
Изглежда близко до равномерно, но ако считаме последователността по две числа и ги интерпретираме като координати на равнината, то получаваме това:
Визуализират се ясно модели. А тъй като данните в последователността са подредени по определен начин (т.е. имат ниска ентропия), това може да предизвика въпросната "пристрастност". Поне такъв ГПСЧ не е много подходящ за генериране на координати на равнината.
Друга последователност:
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, …
Вижда се, че тук всичко е наред, дори на равнината:
Нека да погледнем в обем (читаем по три числа):
И отново модели. Създаването на визуализация в четири измерения вече не е възможно. Но модели могат да съществуват и в това измерение, и в по-високи.
В същата криптография, където се поставят най-строги изисквания към ГПСЧ, подобна ситуация е категорично недопустима. Затова са разработени специални алгоритми за оценка на тяхното качество, по които сега няма да говорим. Темата е обширна и заслужава отделна статия.
Тестване
Ако не знаем нещо със сигурност, как да работим с него? Стои ли си да пресечеш улицата, ако не знаеш какъв сигнал на светофара разрешава това? Последствията могат да бъдат различни.
Същото важи и за пресловутия рандом в Unity. Добре е, ако документацията разкрива необходимите подробности, но споменатата в началото на статията история е станала точно поради липсата на желаната конкретика.
Ако не знаеш как работи инструментът, няма да можеш да го приложиш коректно. Време е да проверим и проведем експеримент, за да се уверим поне що се отнася до разпределението.
Решението беше просто и ефективно — да съберем статистика, да получим обективни данни и да разгледаме резултатите.
Предмет на изследването
В Unity съществуват няколко начина за генериране на случайни числа — тествали сме пет.
- System.Random.Next(). Генерира цели числа в зададения диапазон.
- System.Random.NextDouble(). Генерира числа с двойна точност в диапазона от [0; 1).
- UnityEngine.Random.Range(). Генерира числа с единична точност в зададения диапазон.
- UnityEngine.Random.value. Генерира числа с единична точност в диапазона от [0; 1).
- Unity.Mathematics.Random.NextFloat(). Част от новата библиотека Unity.Mathematics. Генерира числа с единична точност в зададения диапазон.
Практически навсякъде в документацията беше посочено равномерно разпределение, с изключение на UnityEngine.Random.value (където разпределението не е посочено, но по аналогия с UnityEngine.Random.Range() също се очакваше равно) и Unity.Mathematics.Random.NextFloat() (където в основата му стои алгоритъм xorshift, следователно отново е необходимо да се очаква равномерно разпределение).
По подразбиране се взимат за очаквани резултатите, посочени в документацията.
Методика
Създадохме малко приложение, което генерираше последователности от случайни числа по всеки от представените начини и запазваше резултатите за по-нататъшна обработка.
Дължината на всяка последователност е 100 000 числа.
Диапазонът на стойностите на случайните числа е [0, 100).
Данните бяха събирани от няколко целеви платформи:
- Windows
— Unity v2018.3.14f1, Режим на редактора, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, Режим на редактора, Mono, .NET Standard 2.0
— Unity v5.6.4p4, Режим на редактора, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, компилация на устройство, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, компилация на устройство, il2cpp, .NET Standard 2.0
Реализация
Имаме няколко различни начина за генериране на случайни числа. За всеки от тях ще напишем отделен клас-обертка, който трябва да предостави:
- Възможност за задаване на диапазона на стойностите [min/max). Ще бъде зададено чрез конструктора.
- Метод, който връща случайно число. Като тип ще изберем float, като по-обобщен.
- Наименование на начина на генериране за маркиране на резултатите. За удобство като стойност ще връщаме пълното име на класа + името на метода, използван за генериране на случайното число.
Първо, да обявим абстракция, която ще бъде представена чрез интерфейса IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Имплементация на System.Random.Next()
Този метод позволява задаване на диапазон от стойности, но връща цели числа (integer), а имаме нужда от float. Може просто да интерпретираме integer като float, или можем да разширим диапазона на стойностите с няколко реда, компенсирайки ги при всяко генериране на произволно число. Ще получим нещо като фиксирована запетая с зададена точност. Ще използваме този вариант, тъй като е по-близък до истинската стойност 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;
}
}Имплементация на System.Random.NextDouble()
Тук има фиксиран диапазон от стойности [0; 1). За да го проектираме на зададения в конструктора, използваме проста аритметика: 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()
Този метод на статичния клас UnityEngine.Random позволява задаване на диапазон от стойности и връща произволно число от тип float. Никакви допълнителни преобразувания няма да са необходими.
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
Свойството value на статичния клас UnityEngine.Random връща произволно число от тип float в фиксирован диапазон от стойности [0; 1). Нека го проектираме на зададения диапазон по същия начин, както при имплементацията на System.Random.NextDouble().
използвайки 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()
Методът NextFloat() на класа Unity.Mathematics.Random връща число от тип float и позволява да зададете диапазон на стойности. Единственият нюанс е, че всеки екземпляр на Unity.Mathematics.Random трябва да бъде инициализиран с някой seed — така избягваме генерирането на повтарящи се последователности.
използвайки 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);
}
}Имплементация на MainController
Няколко имплементации на IRandomGenerator са готови. Сега е необходимо да се генерират последователности и да се запази полученият датасет за обработка. За целта ще създадем сцена в Unity и малък скрипт MainController, който ще изпълнява цялата необходима работа и ще отговаря за взаимодействието с потребителския интерфейс.
Ще зададем размер на датасета и диапазон на стойностите на числовите генерации, както и ще създадем метод, който връща масив от настроени и готови за работа генератори.
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)
};
}
...
}
}А сега формируем датасета. В този случай генерирането на данни ще бъде комбинирано със записването на резултатите в текстов стрийм (в формат csv). За съхранение на стойностите на всяко IRandomGenerator се отделя своя собствена колона, а първият ред съдържа името на генератора.
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();
}
}
...
}
}Остава да се извика методът GenerateCsvDataSet и да се запази резултатът в файл, или директно да се предадат данните по мрежата от крайната устройство на получаващото. сървър.
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();
}
}
...
}
}Изходните файлове на проекта се намират на .
Резултати
Чудо не се е случило. Каквото очаквахме, такова и получихме — във всички случаи равномерно разпределение без намек за заплождане. Не виждам смисъл в прикачването на отделни графики по платформи — те всички показват приблизително еднакви резултати.
Реалността е такава:
Визуализация на последователностите на равнината от всичките пет метода на генериране:
И визуализация в 3D. Оставям само резултата от System.Random.Next(), за да не създавам куп идентично съдържание.
Разказаната във въведението история за нормалното разпределение на UnityEngine.Random не се повтори: или е била първоначално погрешна, или нещо е променено в двигателя оттогава. Но сега сме сигурни.
Източник: habr.com
