При разработването на игри често трябва да обвържете нещо със случайността: Unity има свой собствен Random за това и успоредно с него има System.Random. Веднъж в един от проектите ми направи впечатление, че и двата могат да работят по различен начин (въпреки че трябва да имат равномерно разпределение).
Тогава те не навлязоха в подробности - достатъчно беше, че преходът към System.Random коригира всички проблеми. Сега решихме да го разгледаме по-подробно и да проведем малко проучване: колко „предубедени“ или предсказуеми са RNG и кой да изберем. Освен това, повече от веднъж съм чувал противоречиви мнения относно тяхната „честност“ - нека се опитаме да разберем как реалните резултати се сравняват с декларираните.
Кратка образователна програма или RNG всъщност е RNG
Ако вече сте запознати с генераторите на произволни числа, можете веднага да преминете към раздела „Тестване“.
Случайните числа (RN) са поредица от числа, генерирани чрез някакъв случаен (хаотичен) процес, източник на ентропия. Тоест, това е последователност, чиито елементи не са свързани помежду си с никакъв математически закон - нямат причинно-следствена връзка.
Това, което създава произволното число, се нарича генератор на произволни числа (RNG). Изглежда, че всичко е елементарно, но ако преминем от теория към практика, тогава всъщност не е толкова лесно да се приложи софтуерен алгоритъм за генериране на такава последователност.
Причината се крие в липсата на същия този хаос в съвременната битова електроника. Без него случайните числа престават да бъдат случайни и техният генератор се превръща в обикновена функция от очевидно дефинирани аргументи. За редица специалности в ИТ сферата това е сериозен проблем (например криптографията), но за други има напълно приемливо решение.
Необходимо е да се напише алгоритъм, който да връща, макар и не наистина случайни числа, но възможно най-близки до тях - така наречените псевдослучайни числа (PRN). Алгоритъмът в този случай се нарича генератор на псевдослучайни числа (PRNG).
Има няколко опции за създаване на PRNG, но следното ще бъде от значение за всички:
- Необходимостта от предварителна инициализация.
PRNG няма източник на ентропия, така че трябва да му се даде първоначално състояние преди употреба. Посочва се като число (или вектор) и се нарича семе (произволно семе). Често броячът на часовника на процесора или численият еквивалент на системното време се използва като семе.
- Възпроизводимост на последователността.
PRNG е напълно детерминистичен, така че семето, посочено по време на инициализацията, уникално определя цялата бъдеща последователност от числа. Това означава, че отделен PRNG, инициализиран със същото семе (по различно време, в различни програми, на различни устройства), ще генерира същата последователност.
Също така трябва да знаете разпределението на вероятностите, характеризиращо PRNG - какви числа ще генерира и с каква вероятност. Най-често това е или нормално разпределение, или равномерно разпределение.
Нормално разпределение (вляво) и равномерно разпределение (вдясно)
Да кажем, че имаме справедлив зар с 24 страни. Ако го хвърлите, вероятността да получите единица ще бъде равна на 1/24 (същата като вероятността да получите всяко друго число). Ако направите много хвърляния и запишете резултатите, ще забележите, че всички ръбове изпадат с приблизително еднаква честота. По същество тази матрица може да се счита за RNG с равномерно разпределение.
Ами ако хвърлите 10 от тези зарове наведнъж и преброите общите точки? Ще се запази ли еднообразието за него? Не. Най-често сумата ще бъде близо до 125 точки, тоест до някаква средна стойност. И в резултат на това, дори преди да направите хвърляне, можете грубо да оцените бъдещия резултат.
Причината е, че има най-много комбинации за получаване на среден резултат. Колкото по-далеч от него, толкова по-малко комбинации - и, съответно, по-малка е вероятността от загуба. Ако тези данни се визуализират, те смътно ще наподобяват формата на камбана. Следователно, с известно удължение, система от 10 зара може да се нарече RNG с нормално разпределение.
Друг пример, само че този път в самолет - стрелба по мишена. Стрелецът ще бъде RNG, който генерира двойка числа (x, y), които се показват на графиката.
Съгласете се, че опцията отляво е по-близо до реалния живот - това е RNG с нормално разпределение. Но ако трябва да разпръснете звезди в тъмно небе, тогава правилната опция, получена с помощта на RNG с равномерно разпределение, е по-подходяща. Като цяло изберете генератор в зависимост от поставената задача.
Сега нека поговорим за ентропията на PNG последователността. Например, има последователност, която започва така:
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, ...
Колко случайни са тези числа на пръв поглед? Нека започнем с проверка на разпределението.
Изглежда почти еднообразно, но ако прочетете поредица от две числа и ги интерпретирате като координати в равнина, ще получите това:
Моделите стават ясно видими. И тъй като данните в последователността са подредени по определен начин (т.е. имат ниска ентропия), това може да доведе до точно това „пристрастие“. Като минимум такъв PRNG не е много подходящ за генериране на координати в равнина.
Друга последователност:
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, ...
Тук всичко изглежда наред дори в самолета:
Нека погледнем в обем (четете три числа наведнъж):
И отново шарките. Вече не е възможно да се изгради визуализация в четири измерения. Но моделите могат да съществуват в това измерение и в по-големи.
В криптографията, където към PRNG се налагат най-строги изисквания, подобна ситуация е категорично неприемлива. Затова са разработени специални алгоритми за оценка на тяхното качество, които няма да засягаме сега. Темата е обширна и заслужава отделна статия.
Тестване
Ако не знаем нещо със сигурност, тогава как да работим с него? Струва ли си да пресичате пътя, ако не знаете кой светофар го позволява? Последствията може да са различни.
Същото важи и за прословутата случайност в 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). Ще се задава чрез конструктора.
- Метод, връщащ MF. Нека изберем float като тип, тъй като е по-общ.
- Името на метода за генериране за маркиране на резултатите. За удобство ще върнем като стойност пълното име на класа + името на метода, използван за генериране на MF.
Първо, нека декларираме абстракция, която ще бъде представена от интерфейса IRandomGenerator:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Внедряване на System.Random.Next()
Този метод ви позволява да зададете диапазон от стойности, но връща цели числа, но са необходими плаващи числа. Можете просто да интерпретирате цяло число като плаващо число или можете да разширите диапазона от стойности с няколко порядъка, като ги компенсирате с всяко поколение на средния диапазон. Резултатът ще бъде нещо като фиксирана точка с даден ред на точност. Ще използваме тази опция, тъй като е по-близо до реалната плаваща стойност.
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 ви позволява да зададете диапазон от стойности и връща плаващ тип. Не е необходимо да правите допълнителни трансформации.
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
Свойството стойност на статичния клас UnityEngine.Random връща плаващ тип от фиксиран диапазон от стойности [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 ще трябва да се инициализира с някакво семе - по този начин ще избегнем генерирането на повтарящи се последователности.
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. След това трябва да генерирате последователности и да запазите получения набор от данни за обработка. За да направим това, ще създадем сцена и малък скрипт MainController в Unity, който ще свърши цялата необходима работа и в същото време ще отговаря за взаимодействието с потребителския интерфейс.
Нека зададем размера на набора от данни и обхвата на стойностите на MF, а също така да получим метод, който връща масив от генератори, конфигурирани и готови за работа.
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, не се повтори: или първоначално беше грешна, или нещо оттогава се е променило в двигателя. Но сега сме сигурни.
Източник: www.habr.com