У развоју игара, често морате нешто да повежете са случајношћу: Унити има свој Рандом за ово, а паралелно са њим постоји Систем.Рандом. Једном давно, на једном од пројеката, стекао сам утисак да оба могу другачије да раде (иако треба да имају равномерну дистрибуцију).
Онда нису улазили у детаље - било је довољно да је прелазак на Систем.Рандом исправио све проблеме. Сада смо одлучили да то детаљније размотримо и спроведемо мало истраживање: колико су РНГ-ови „пристрасни“ или предвидљиви и који да одаберете. Штавише, више пута сам чуо опречна мишљења о њиховој „поштености“ - хајде да покушамо да схватимо како се стварни резултати упоређују са декларисаним.
Кратак образовни програм или РНГ је заправо РНГ
Ако сте већ упознати са генераторима случајних бројева, можете одмах прескочити на одељак „Тестирање“.
Случајни бројеви (РН) су низ бројева генерисаних коришћењем неког случајног (хаотичног) процеса, извора ентропије. То јест, ово је низ чији елементи нису међусобно повезани никаквим математичким законом - немају узрочно-последичну везу.
Оно што ствара случајни број назива се генератор случајних бројева (РНГ). Чини се да је све елементарно, али ако пређемо са теорије на праксу, онда у ствари није тако једноставно имплементирати софтверски алгоритам за генерисање таквог низа.
Разлог лежи у одсуству тог истог хаоса у модерној потрошачкој електроници. Без тога, случајни бројеви престају да буду случајни, а њихов генератор се претвара у обичну функцију очигледно дефинисаних аргумената. За један број специјалности у ИТ области ово је озбиљан проблем (на пример, криптографија), али за друге постоји потпуно прихватљиво решење.
Неопходно је написати алгоритам који би враћао, додуше не истински случајне бројеве, али им што ближе – такозване псеудослучајне бројеве (ПРН). Алгоритам у овом случају се назива генератор псеудослучајних бројева (ПРНГ).
Постоји неколико опција за креирање ПРНГ-а, али следеће ће бити релевантне за све:
- Потреба за прелиминарном иницијализацијом.
ПРНГ нема извор ентропије, тако да му се мора дати почетно стање пре употребе. Наведен је као број (или вектор) и назива се семе (случајно семе). Често се као семе користи бројач такта процесора или нумерички еквивалент системског времена.
- Репродуцибилност секвенце.
ПРНГ је потпуно детерминистички, тако да семе специфицирано током иницијализације јединствено одређује цео будући низ бројева. То значи да ће посебан ПРНГ иницијализован истим семеном (у различито време, у различитим програмима, на различитим уређајима) генерисати исту секвенцу.
Такође морате знати расподелу вероватноће која карактерише ПРНГ – које бројеве ће генерисати и са којом вероватноћом. Најчешће је то или нормална или униформна расподела.
Нормална дистрибуција (лево) и униформна дистрибуција (десно)
Рецимо да имамо поштену коцку са 24 стране. Ако га баците, вероватноћа да добијете један биће једнака 1/24 (исто као вероватноћа да ћете добити било који други број). Ако направите много бацања и забележите резултате, приметићете да све ивице испадају са приближно истом фреквенцијом. У суштини, ова матрица се може сматрати РНГ са униформном дистрибуцијом.
Шта ако баците 10 ових коцкица одједном и пребројите укупан број поена? Хоће ли се за њега одржати униформност? Не. Најчешће ће износ бити близу 125 поена, односно неке просечне вредности. И као резултат тога, чак и пре бацања, можете грубо проценити будући резултат.
Разлог је што постоји највећи број комбинација за добијање просечне оцене. Што је даље од тога, то је мање комбинација - и, сходно томе, мања је вероватноћа губитка. Ако се ови подаци визуелизују, они ће нејасно подсећати на облик звона. Према томе, уз извесно натезање, систем од 10 коцкица се може назвати РНГ са нормалном дистрибуцијом.
Још један пример, само овога пута у авиону – гађање мете. Стрелац ће бити РНГ који генерише пар бројева (к, и) који се приказује на графикону.
Слажете се да је опција са леве стране ближа стварном животу - ово је РНГ са нормалном дистрибуцијом. Али ако треба да распршите звезде на тамном небу, онда је права опција, добијена коришћењем РНГ-а са униформном дистрибуцијом, боља. Генерално, изаберите генератор у зависности од задатка.
Хајде сада да причамо о ентропији ПНГ секвенце. На пример, постоји низ који почиње овако:
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, ...
Чини се да је све у реду овде чак иу авиону:
Хајде да погледамо у обиму (читај три броја одједном):
И опет обрасци. Више није могуће конструисати визуелизацију у четири димензије. Али обрасци могу постојати на овој димензији и на већим.
У криптографији, где се на ПРНГ постављају најстрожи захтеви, таква ситуација је категорички неприхватљива. Због тога су развијени посебни алгоритми за процену њиховог квалитета, на које се сада нећемо дотицати. Тема је обимна и заслужује посебан чланак.
Тестирање
Ако нешто не знамо сигурно, како онда радити с тим? Да ли је вредно прећи пут ако не знате који семафор то дозвољава? Последице могу бити различите.
Исто важи и за озлоглашену случајност у Јединству. Добро је ако документација открива потребне детаље, али прича поменута на почетку чланка догодила се управо због недостатка жељених специфичности.
А ако не знате како алат функционише, нећете моћи да га правилно користите. Генерално, дошло је време да се провери и спроведе експеримент да се коначно увери бар у дистрибуцију.
Решење је било једноставно и ефикасно – прикупити статистику, добити објективне податке и погледати резултате.
Предмет проучавања
Постоји неколико начина за генерисање случајних бројева у Унити-у - тестирали смо пет.
- Систем.Рандом.Нект(). Генерише целе бројеве у датом опсегу вредности.
- Систем.Рандом.НектДоубле(). Генерише бројеве двоструке прецизности у опсегу од [0; 1).
- УнитиЕнгине.Рандом.Ранге(). Генерише појединачне прецизне бројеве (флоатс) у датом опсегу вредности.
- УнитиЕнгине.Рандом.валуе. Генерише појединачне прецизне бројеве (флоатс) у опсегу од [0; 1).
- Унити.Матхематицс.Рандом.НектФлоат(). Део нове библиотеке Унити.Матхематицс. Генерише појединачне прецизне бројеве (флоатс) у датом опсегу вредности.
Скоро свуда у документацији је специфицирана униформна дистрибуција, са изузетком УнитиЕнгине.Рандом.валуе (где дистрибуција није наведена, али се по аналогији са УнитиЕнгине.Рандом.Ранге() униформа такође очекивала) и Унити.Матхематицс.Рандом .НектФлоат() (где је у Основа алгоритам корсхифт, што значи да опет треба да сачекате униформну дистрибуцију).
Подразумевано, очекивани резултати су узети као они наведени у документацији.
Методологија
Написали смо малу апликацију која је генерисала низове случајних бројева користећи сваку од представљених метода и сачувала резултате за даљу обраду.
Дужина сваког низа је 100 бројева.
Опсег случајних бројева је [0, 100).
Подаци су прикупљени са неколико циљних платформи:
- виндовс
— Унити в2018.3.14ф1, режим уређивача, моно, .НЕТ Стандард 2.0 - Мац ОС
— Унити в2018.3.14ф1, режим уређивача, моно, .НЕТ Стандард 2.0
— Унити в5.6.4п4, Едитор моде, Моно, .НЕТ Стандард 2.0 - Android
— Унити в2018.3.14ф1, буилд по уређају, Моно, .НЕТ Стандард 2.0 - иОС
— Унити в2018.3.14ф1, буилд по уређају, ил2цпп, .НЕТ Стандард 2.0
Имплементација
Имамо неколико различитих начина да генеришемо случајне бројеве. За сваку од њих написаћемо посебну класу омотача, која треба да обезбеди:
- Могућност подешавања опсега вредности [мин/макс). Биће подешен преко конструктора.
- Метод враћања МФ. Хајде да изаберемо флоат као тип, јер је општији.
- Назив методе генерисања за обележавање резултата. Ради погодности, вратићемо као вредност пуно име класе + име методе која се користи за генерисање МФ.
Прво, хајде да декларишемо апстракцију која ће бити представљена интерфејсом ИРандомГенератор:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Имплементација Систем.Рандом.Нект()
Овај метод вам омогућава да поставите опсег вредности, али враћа целе бројеве, али су потребни плутајући. Можете једноставно протумачити цео број као флоат, или можете проширити опсег вредности за неколико редова величине, компензујући их са сваком генерацијом средњег опсега. Резултат ће бити нешто попут фиксне тачке са датим редоследом тачности. Користићемо ову опцију пошто је ближа стварној вредности са плутајућом вредности.
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;
}
}Имплементација Систем.Рандом.НектДоубле()
Овде је фиксни опсег вредности [0; 1). Да бисмо га пројектовали на онај који је наведен у конструктору, користимо једноставну аритметику: Кс * (мак − мин) + мин.
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;
}
}Имплементација УнитиЕнгине.Рандом.Ранге()
Овај метод статичке класе УнитиЕнгине.Рандом вам омогућава да поставите опсег вредности и враћа тип флоат. Не морате да радите никакве додатне трансформације.
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);
}
}Имплементација УнитиЕнгине.Рандом.валуе
Својство вредности статичке класе УнитиЕнгине.Рандом враћа тип флоат из фиксног опсега вредности [0; 1). Пројектујмо га на дати опсег на исти начин као када имплементирамо Систем.Рандом.НектДоубле().
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;
}
}Имплементација Унити.Матхематицс.Рандом.НектФлоат()
Метод НектФлоат() класе Унити.Матхематицс.Рандом враћа плутајући зарез типа флоат и омогућава вам да наведете опсег вредности. Једина нијанса је да ће свака инстанца Унити.Матхематицс.Рандом морати да се иницијализује са неким семеном - на овај начин ћемо избећи генерисање понављајућих секвенци.
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);
}
}Имплементација МаинЦонтроллер-а
Неколико имплементација ИРандомГенератора је спремно. Затим морате да генеришете секвенце и сачувате резултујући скуп података за обраду. Да бисмо то урадили, креираћемо сцену и малу МаинЦонтроллер скрипту у Унити-у, која ће обавити сав потребан посао и истовремено бити одговорна за интеракцију са корисничким интерфејсом.
Хајде да подесимо величину скупа података и опсег МФ вредности, а такође добијемо метод који враћа низ генератора конфигурисаних и спремних за рад.
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)
};
}
...
}
}Сада направимо скуп података. У овом случају, генерисање података ће бити комбиновано са снимањем резултата у текстуални ток (у цсв формату). За чување вредности сваког ИРандомГенератора, додељује се посебна колона, а први ред садржи Име генератора.
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();
}
}
...
}
}Остаје само да позовете методу ГенератеЦсвДатаСет и сачувате резултат у датотеку, или одмах пренесете податке преко мреже са крајњег уређаја на сервер који прима.
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();
}
}
...
}
}Извори пројекта су на .
Налази
Никакво чудо се није догодило. Оно што су очекивали је оно што су добили - у свим случајевима, равномерну расподелу без наговештаја завере. Не видим смисао у постављању одвојених графикона за платформе - сви показују приближно исте резултате.
Реалност је следећа:
Визуелизација секвенци на равни из свих пет генерацијских метода:
И визуелизација у 3Д. Оставићу само резултат Систем.Рандом.Нект() да не би произвео гомилу идентичног садржаја.
Прича испричана у уводу о нормалној дистрибуцији УнитиЕнгине.Рандом се није поновила: или је у почетку била погрешна, или се нешто променило у мотору. Али сада смо сигурни.
Извор: ввв.хабр.цом