У геймдэве часта трэба што-небудзь завязаць на рандоме: у 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