В геймдевелопмента често е необходимо да се завърже нещо на произвола: Unity има свой Random за това, а паралелно му съществува System.Random. Отдавна, на един от проектите, се създаде впечатление, че и двата могат да работят различно (въпреки че трябва да имат равномерно разпределение).
Тогава не се задълбочихме в детайлите — достатъчно беше, че преминаването на System.Random коригира всички проблеми. Сега решихме да се опитаме да се разберем по-добре и да проведем малко изследване: колко „предвзети“ или предсказуеми са генераторите на случайни числа и кой да изберем. Освен това, не веднъж съм чувал противоречиви мнения за тяхната „честност“ — ще се опитаме да разберем как реалните резултати съответстват на заявените.
Кратко ликбез или ГСЧ всъщност е ГПСЧ.
Ако вече сте запознати с генераторите на случайни числа, можете веднага да преминете към раздела „Тестване“.
Случайните числа (СЧ) — това е последователност от числа, генерирана с помощта на някакъв случайно (хаотично) процес, източник на ентропия. Тоест това е последователност, елементите на която не са свързани помежду си чрез математически закон — те нямат причинно-следствена връзка.
Това, което генерира СЧ, се нарича генератор на случайни числа (ГСЧ). Изглежда елементарно, но всъщност да се реализира софтуерен алгоритъм за генериране на такава последователност не е толкова просто.
Причината е в отсъствието на споменатата хаотичност в съвременната потребителска електроника. Без нея, случайните числа спират да бъдат случайни, а техният генератор се превръща в обикновена функция от предварително определени аргументи. За редица специалности в ИТ сферата това е сериозен проблем (например, за криптографията), а за останалите има напълно приемливо решение.
Необходимо е да се напише алгоритъм, който да връща, макар и не напълно случайни числа, но максимално близки до тях — така наречените псевдослучайни числа (ПСЧ). Алгоритъмът в този случай се нарича генератор на псевдослучайни числа (ГПСЧ).
Има няколко варианта за създаване на ГПСЧ, но за всички ще бъде важно следното:
- Необходимост от предварителна инициализация.
ГПСЧ е лишен от източник на ентропия, затова преди да се използва, е необходимо да се зададе начално състояние. То се определя под формата на число (или вектор) и се нарича семе (seed, random seed). Често за seed се използва брояч на тактовете на процесора или числовият еквивалент на системното време.
- Възпроизводимост на последователността.
ГПСЧ е напълно детерминиран, затова зададеният при инициализацията seed точно определя цялата бъдеща последователност от числа. Това означава, че индивидуален ГПСЧ, инициализиран с еднакъв 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(). Генерира цели числа (integer) в зададен диапазон от стойности.
- System.Random.NextDouble(). Генерира числа с двойна точност (double) в диапазон от [0; 1).
- UnityEngine.Random.Range(). Генерира числа с единична точност (float) в зададен диапазон от стойности.
- UnityEngine.Random.value. Генерира числа с единична точност (float) в диапазон от [0; 1).
- Unity.Mathematics.Random.NextFloat(). Част от новата библиотека Unity.Mathematics. Генерира числа с единична точност (float) в зададен диапазон от стойности.
Почти навсякъде в документацията беше посочено равномерно разпределение, с изключение на 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().
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()
Методът NextFloat() на класа Unity.Mathematics.Random връща стойност от тип float и позволява да зададем диапазон от стойности. Единственият нюанс е, че всеки екземпляр на Unity.Mathematics.Random трябва да бъде инициализиран с определен seed, за да избегнем генерирането на повтарящи се последователности.
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);
}
}Имплементация на 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;
// пишем заголовок
for (int j = 0; j <= lastIdx; j++)
{
writer.Write(generators[j].Name);
if (j != lastIdx)
writer.Write(separator);
}
writer.WriteLine();
// записываем данные
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
