Mänguarenduses tuleb sageli midagi juhuslikkusega siduda: Unityl on selleks oma Random ja sellega paralleelselt System.Random. Kunagi ammu ühe projekti puhul jäi mulje, et mõlemad võiksid toimida erinevalt (kuigi nende jaotus peaks olema ühtlane).
Siis nad detailidesse ei laskunud - piisas sellest, et üleminek süsteemile System.Random parandas kõik probleemid. Nüüd otsustasime seda üksikasjalikumalt uurida ja teha väikese uuringu: kui "kallutatud" või prognoositavad on RNG-d ja millist neist valida. Veelgi enam, olen korduvalt kuulnud vastakaid arvamusi nende "aususe" kohta - proovime välja mõelda, kuidas tegelikud tulemused võrreldavad deklareeritud tulemustega.
Краткий ликбез или ГСЧ это на самом деле ГПСЧ
Kui olete juhuslike numbrite generaatoritega juba tuttav, võite kohe minna jaotisse "Testimine".
Juhuslikud arvud (RN) on arvude jada, mis on genereeritud mõne juhusliku (kaootilise) protsessi abil, mis on entroopia allikas. See tähendab, et see on jada, mille elemendid ei ole omavahel seotud ühegi matemaatilise seadusega – neil pole põhjuse-tagajärje seost.
Juhusliku arvu loomist nimetatakse juhuslike arvude generaatoriks (RNG). Näib, et kõik on elementaarne, kuid kui liigume teooriast praktikasse, siis tegelikult pole sellise jada genereerimiseks tarkvaraalgoritmi rakendamine nii lihtne.
Põhjus peitub selles, et kaasaegses tarbeelektroonikas puudub sama kaos. Ilma selleta lakkavad juhuslikud arvud olemast juhuslikud ja nende generaator muutub ilmselgelt määratletud argumentide tavaliseks funktsiooniks. Mitmete IT-valdkonna erialade jaoks on see tõsine probleem (näiteks krüptograafia), kuid teiste jaoks on täiesti vastuvõetav lahendus.
On vaja kirjutada algoritm, mis tagastaks, ehkki mitte päris juhuslikud arvud, vaid neile võimalikult lähedased - nn pseudojuhuslikud numbrid (PRN). Sel juhul nimetatakse algoritmi pseudojuhuslike arvude generaatoriks (PRNG).
PRNG loomiseks on mitu võimalust, kuid järgmine on asjakohane kõigile:
- Eelinitsialiseerimise vajadus.
PRNG-l pole entroopia allikat, seega tuleb enne kasutamist anda sellele algseisund. See on määratud arvuna (või vektorina) ja seda nimetatakse seemneks (juhuslik seeme). Sageli kasutatakse seemnena protsessori kella loendurit või süsteemiaja numbrilist ekvivalenti.
- Воспроизводимость последовательности.
PRNG on täielikult deterministlik, seega määrab lähtestamise käigus määratud seeme üheselt kogu tulevase numbrijada. See tähendab, et sama seemnega (eri aegadel, erinevates programmides, erinevates seadmetes) lähtestatud eraldi PRNG genereerib sama jada.
Samuti peate teadma PRNG-d iseloomustavat tõenäosusjaotust – milliseid numbreid see genereerib ja millise tõenäosusega. Enamasti on see kas normaaljaotus või ühtlane jaotus.
Normaaljaotus (vasakul) ja ühtlane jaotus (paremal)
Oletame, et meil on 24 küljega aus. Kui viskate selle ümber, on ühe saamise tõenäosus 1/24 (sama mis tõenäosusega saada mõni muu arv). Kui teete palju viskeid ja fikseerite tulemused, märkate, et kõik servad kukuvad välja ligikaudu sama sagedusega. Põhimõtteliselt võib seda stantsi pidada ühtlase jaotusega RNG-ks.
Mis siis, kui viskad 10 täringut korraga ja loeksid kokku punktid? Kas selle puhul säilib ühtsus? Ei. Kõige sagedamini on see summa 125 punkti lähedal, st mõnele keskmisele väärtusele. Ja tänu sellele saab juba enne viske sooritamist umbkaudu hinnata tulevast tulemust.
Причина в том, что для получения средней суммы очков существует наибольшее количество комбинаций. Чем дальше от нее, тем меньше комбинаций — и соответственно, меньше вероятность выпадения. Если эти данные визуализировать, то они будут отдаленно напоминать форму колокола. Поэтому с некоторой натяжкой систему из 10 костей можно назвать ГСЧ с нормальным распределением.
Veel üks näide, ainult seekord lennukis – sihtmärki laskmine. Tulistaja on RNG, mis genereerib arvude paari (x, y), mis kuvatakse graafikul.
Согласитесь, что вариант слева более приближен к реальной жизни — это ГСЧ с нормальным распределением. Но если нужно разбросать звезды на темном небе, то лучше подойдет правый вариант, полученный с помощью ГСЧ с равномерным распределением. В общем, выбирайте генератор в зависимости от поставленной задачи.
Nüüd räägime PNG-jada entroopiast. Näiteks on jada, mis algab järgmiselt:
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, ...
Kui juhuslikud need numbrid esmapilgul on? Alustuseks kontrollime jaotust.
See näeb välja peaaegu ühtlane, kuid kui loete kahe numbri jada ja tõlgendate neid tasapinna koordinaatidena, saate järgmise:
Mustrid muutuvad selgelt nähtavaks. Ja kuna jadas olevad andmed on teatud viisil järjestatud (st neil on madal entroopia), võib see põhjustada just selle "kaldsuse". Vähemalt selline PRNG ei sobi tasapinnal koordinaatide genereerimiseks.
Teine järjestus:
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, ...
Вроде бы тут все хорошо даже на плоскости:
Vaatame mahu järgi (loe kolme numbrit korraga):
Ja jälle mustrid. Neljamõõtmelist visualiseerimist pole enam võimalik konstrueerida. Kuid mustrid võivad eksisteerida nii sellel kui ka suurematel dimensioonidel.
Krüptograafias, kus PRNG-dele esitatakse kõige rangemad nõuded, on selline olukord kategooriliselt vastuvõetamatu. Seetõttu on nende kvaliteedi hindamiseks välja töötatud spetsiaalsed algoritmid, mida me nüüd ei puuduta. Teema on ulatuslik ja väärib eraldi artiklit.
Katsetamine
Kui me midagi kindlalt ei tea, siis kuidas sellega töötada? Kas tasub teed ületada, kui ei tea, milline foor seda lubab? Tagajärjed võivad olla erinevad.
Sama kehtib Unity kurikuulsa juhuslikkuse kohta. Hea, kui dokumentatsioonist selgub vajalikud detailid, kuid artikli alguses mainitud lugu juhtus just soovitud spetsiifika puudumise tõttu.
А не зная, как работает инструмент, не сможешь его корректно применить. В общем, настало время проверить и провести эксперимент, чтобы окончательно убедиться хотя бы на счет распределения.
Lahendus oli lihtne ja tõhus – koguge statistikat, hankige objektiivseid andmeid ja vaadake tulemusi.
Õppeaine
В Unity существует несколько способов генерации случайных чисел — мы протестировали пять.
- System.Random.Next(). Генерирует целые числа (integer) в заданном диапазоне значений.
- System.Random.NextDouble(). Генерирует числа двойной точности (double) в диапазоне от [0; 1).
- UnityEngine.Random.Range(). Генерирует числа одинарной точности (float) в заданном диапазоне значений.
- UnityEngine.Random.value. Genereerib üksikud täppisarvud (ujuvad) vahemikus [0; 1).
- Ühtsus.Matemaatika.Juhuslik.NextFloat(). Osa uuest Unity.Mathematics raamatukogust. Genereerib üksikud täppisarvud (ujuvad) antud väärtusvahemikus.
Практически везде в документации было указано равномерное распределение, за исключением UnityEngine.Random.value (где распределение не указано, но по аналогии с UnityEngine.Random.Range() также ожидалось равномерное) и Unity.Mathematics.Random.NextFloat() (где в основе лежит алгоритм xorshift, а значит, снова нужно ждать равномерное распределение).
Vaikimisi võeti oodatavaid tulemusi dokumentatsioonis määratletutena.
Metoodika
Мы написали небольшое приложение, которое генерировало последовательности случайных чисел каждым из представленных способов и сохраняло результаты для дальнейшей обработки.
Iga jada pikkus on 100 000 numbrit.
Juhuslike arvude vahemik on [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, järg seadme kohta, il2cpp, .NET standard 2.0
Реализация
У нас есть несколько разных способов генерации случайных чисел. Для каждого из них напишем отдельный класс-обертку, который должен предоставить:
- Võimalus määrata väärtuste vahemik [min/max). Seadistab konstruktori kaudu.
- Метод, возвращающий СЧ. В качестве типа выберем float, как более общий.
- Tulemuste märgistamise genereerimismeetodi nimetus. Mugavuse huvides tagastame väärtusena klassi täisnime + MF genereerimiseks kasutatud meetodi nime.
Esiteks deklareerime abstraktsiooni, mida esindab IRandomGeneratori liides:
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}System.Random.Next() juurutamine
See meetod võimaldab teil määrata väärtuste vahemiku, kuid see tagastab täisarvud, kuid ujukid on vajalikud. Täisarvu saate lihtsalt tõlgendada ujuvana või väärtuste vahemikku mitme suurusjärgu võrra laiendada, kompenseerides neid keskvahemiku iga põlvkonnaga. Tulemuseks on midagi kindla täpsusega fikseeritud punkti sarnast. Kasutame seda valikut, kuna see on tegelikule ujuvväärtusele lähemal.
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;
}
}Süsteemi System.Random.NextDouble() rakendamine
Siin on fikseeritud väärtuste vahemik [0; 1). Selle projekteerimiseks konstruktoris määratletule kasutame lihtsat aritmeetikat: 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 rakendamine
Свойство 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() rakendamine
Метод 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();
}
}
...
}
}Projekti allikad on aadressil .
Järeldused
Ime ei juhtunud. Nad ootasid seda, mida nad said – kõigil juhtudel ühtlase jaotuse ilma vandenõu vihjeta. Ma ei näe mõtet platvormide jaoks eraldi graafikuid panna – need kõik näitavad ligikaudu samu tulemusi.
Tegelikkus on järgmine:
Jadade visualiseerimine tasapinnal kõigi viie genereerimismeetodi järgi:
Ja visualiseerimine 3D-s. Jätan ainult System.Random.Next() tulemuse, et mitte tekitada hunnikut identset sisu.
Рассказанная во вступлении история про нормальное распределение UnityEngine.Random не повторилась: либо она изначально была ошибочной, либо что-то с тех пор изменилось в движке. Зато теперь мы уверены.
Allikas: www.habr.com