У геймдеві часто потрібно що-небудь зав'язати на рандомі: Unity для цього має свій Random, а паралельно з ним існує System.Random. Колись давно на одному з проектів склалося враження, що вони можуть працювати по-різному (хоча повинні мати рівномірний розподіл).
Тоді деталі заглиблюватися не стали — вистачило того, що перехід на System.Random виправив усі проблеми. Зараз вирішили розібратися докладніше та провести невелике дослідження: наскільки «упереджені» чи передбачувані ДСЛ, і який вибрати. Тим більше, я не раз чув суперечливі думки щодо їхньої «чесності» — спробуємо розібратися, як реальні результати співвідносяться із заявленими.
Короткий лікнеп чи ДСЛ це насправді ДПСЛ
Якщо ви вже знайомі з генераторами випадкових чисел, можете відразу переходити до розділу «Тестування».
Випадкові числа (СЧ) - це послідовність чисел, що генерується за допомогою деякого випадкового (хаотичного) процесу, джерела ентропії. Тобто це така послідовність, елементи якої не пов'язані між собою будь-яким математичним законом — у них відсутній причинно-наслідковий зв'язок.
Те, що створює СЧ, називається генератором випадкових чисел (ГСЧ). Здавалося б, все елементарно, але якщо від теорії перейти до практики, насправді реалізувати програмний алгоритм генерації такої послідовності не так просто.
Причина криється у відсутності тієї хаотичності в сучасній споживчій електроніці. Без неї випадкові числа перестають бути випадковими, які генератор перетворюється на звичайну функцію від свідомо певних аргументів. Для цілого ряду спеціальностей в IT-сфері це серйозна проблема (наприклад, для криптографії), а для інших є цілком допустиме рішення.
Потрібно написати алгоритм, який повертав би нехай і не випадкові числа, але максимально наближені до них — так звані, псевдовипадкові числа (ПСЧ). Алгоритм у разі називається генератором псевдовипадкових чисел (ГПСЧ).
Є кілька варіантів створення ГПСЧ, але для всіх буде актуальним наступне:
- Необхідність попередньої ініціалізації.
ДПСЧ позбавлений джерела ентропії, тому перед використанням необхідно вказати початковий стан. Воно задається як числа (чи вектора) і називається зерном (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, Editor mode, Mono, .NET Standard 2.0 - MacOS
- Unity v2018.3.14f1, Editor mode, Mono, .NET Standard 2.0
- Unity v5.6.4p4, Editor mode, 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, а можна розширити діапазон значень кілька порядків, компенсуючи їх за кожної генерації СЧ. Вийде щось на кшталт fixed-point із заданою точністю. Будемо використовувати цей варіант, тому що він ближчий до справжнього 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, який виконуватиме всю необхідну роботу та попутно відповідатиме за взаємодію з UI.
Задамо розмір датасету та діапазон значень СЧ, а також обзаведемося методом, який повертає масив налаштованих та готових до роботи генераторів.
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 відводиться своя окрема колонка, а перший рядок містить Name генератора.
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