Dans le développement de jeux, vous devez souvent lier quelque chose au hasard : Unity a son propre Random pour cela, et en parallèle il y a System.Random. Il était une fois, sur l'un des projets, j'ai eu l'impression que les deux pouvaient fonctionner différemment (même s'ils devraient avoir une répartition égale).
Ensuite, ils ne sont pas entrés dans les détails - il suffisait que la transition vers System.Random corrige tous les problèmes. Nous avons maintenant décidé d’examiner la question plus en détail et de mener une petite recherche : dans quelle mesure les RNG sont-ils « biaisés » ou prévisibles, et lequel choisir. De plus, j'ai entendu plus d'une fois des opinions contradictoires sur leur « honnêteté » - essayons de comprendre comment les résultats réels se comparent à ceux déclarés.
Un bref programme éducatif ou RNG est en fait RNG
Si vous êtes déjà familier avec les générateurs de nombres aléatoires, vous pouvez immédiatement passer à la section « Tests ».
Les nombres aléatoires (RN) sont une séquence de nombres générés à l'aide d'un processus aléatoire (chaotique), source d'entropie. C'est-à-dire qu'il s'agit d'une séquence dont les éléments ne sont interconnectés par aucune loi mathématique - ils n'ont aucune relation de cause à effet.
Ce qui crée le nombre aléatoire s’appelle un générateur de nombres aléatoires (RNG). Il semblerait que tout soit élémentaire, mais si l'on passe de la théorie à la pratique, alors en réalité il n'est pas si simple de mettre en œuvre un algorithme logiciel pour générer une telle séquence.
La raison réside dans l’absence de ce même chaos dans l’électronique grand public moderne. Sans cela, les nombres aléatoires cessent d'être aléatoires et leur générateur se transforme en une fonction ordinaire d'arguments clairement définis. Pour un certain nombre de spécialités du domaine informatique, il s'agit d'un problème sérieux (par exemple, la cryptographie), mais pour d'autres, il existe une solution tout à fait acceptable.
Il est nécessaire d'écrire un algorithme qui renverrait, bien que pas des nombres vraiment aléatoires, mais aussi proches que possible d'eux - les nombres dits pseudo-aléatoires (PRN). L'algorithme dans ce cas est appelé générateur de nombres pseudo-aléatoires (PRNG).
Il existe plusieurs options pour créer un PRNG, mais les suivantes seront pertinentes pour tout le monde :
- La nécessité d'une initialisation préalable.
Le PRNG n’a pas de source d’entropie, il faut donc lui donner un état initial avant utilisation. Il est spécifié sous forme de nombre (ou de vecteur) et est appelé graine (graine aléatoire). Souvent, le compteur d’horloge du processeur ou l’équivalent numérique de l’heure du système est utilisé comme graine.
- Reproductibilité des séquences.
Le PRNG est complètement déterministe, de sorte que la graine spécifiée lors de l'initialisation détermine de manière unique toute la séquence future de nombres. Cela signifie qu'un PRNG distinct initialisé avec la même graine (à des moments différents, dans des programmes différents, sur des appareils différents) générera la même séquence.
Vous devez également connaître la distribution de probabilité caractérisant le PRNG - quels nombres il générera et avec quelle probabilité. Le plus souvent, il s'agit soit d'une distribution normale, soit d'une distribution uniforme.
Distribution normale (à gauche) et distribution uniforme (à droite)
Disons que nous avons un dé équitable avec 24 faces. Si vous le lancez, la probabilité d’en obtenir un sera égale à 1/24 (la même que la probabilité d’obtenir n’importe quel autre nombre). Si vous effectuez de nombreux lancers et enregistrez les résultats, vous remarquerez que tous les bords tombent à peu près à la même fréquence. Essentiellement, ce dé peut être considéré comme un RNG avec une distribution uniforme.
Et si vous jetiez 10 de ces dés à la fois et comptiez le total des points ? L'uniformité sera-t-elle maintenue pour cela ? Non. Le plus souvent, le montant sera proche de 125 points, c'est-à-dire d'une valeur moyenne. Et du coup, avant même de lancer, vous pouvez estimer approximativement le résultat futur.
La raison est qu’il existe le plus grand nombre de combinaisons pour obtenir le score moyen. Plus on s'en éloigne, moins il y a de combinaisons - et, par conséquent, plus la probabilité de perte est faible. Si ces données sont visualisées, elles ressembleront vaguement à la forme d’une cloche. Par conséquent, avec un peu d’étirement, un système de 10 dés peut être appelé un RNG avec une distribution normale.
Autre exemple, mais cette fois dans un avion : tirer sur une cible. Le jeu de tir sera un RNG qui génère une paire de nombres (x, y) affichés sur le graphique.
Convenez que l'option de gauche est plus proche de la vraie vie - il s'agit d'un RNG avec une distribution normale. Mais si vous avez besoin de disperser des étoiles dans un ciel sombre, alors la bonne option, obtenue à l'aide de RNG avec une distribution uniforme, est mieux adaptée. En général, choisissez un générateur en fonction de la tâche à accomplir.
Parlons maintenant de l'entropie de la séquence PNG. Par exemple, il y a une séquence qui commence comme ceci :
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, ...
Dans quelle mesure ces chiffres sont-ils aléatoires à première vue ? Commençons par vérifier la distribution.
Cela semble presque uniforme, mais si vous lisez une séquence de deux nombres et les interprétez comme des coordonnées sur un plan, vous obtenez ceci :
Les motifs deviennent clairement visibles. Et comme les données de la séquence sont ordonnées d’une certaine manière (c’est-à-dire qu’elles ont une faible entropie), cela peut donner lieu à ce même « biais ». A minima, un tel PRNG n'est pas très adapté pour générer des coordonnées sur un avion.
Autre séquence :
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, ...
Tout semble bien ici, même dans l'avion :
Regardons en volume (lisez trois chiffres à la fois) :
Et encore les modèles. Il n'est plus possible de construire une visualisation en quatre dimensions. Mais des modèles peuvent exister dans cette dimension et dans des dimensions plus vastes.
En cryptographie, où les exigences les plus strictes sont imposées aux PRNG, une telle situation est catégoriquement inacceptable. Par conséquent, des algorithmes spéciaux ont été développés pour évaluer leur qualité, que nous n'aborderons pas maintenant. Le sujet est vaste et mérite un article séparé.
Test
Si nous ne savons pas quelque chose avec certitude, comment y parvenir ? Est-ce que cela vaut la peine de traverser la route si on ne sait pas quel feu tricolore le permet ? Les conséquences peuvent être différentes.
Il en va de même pour le caractère aléatoire notoire de Unity. C'est bien si la documentation révèle les détails nécessaires, mais l'histoire mentionnée au début de l'article s'est produite précisément à cause du manque de détails souhaités.
Et si vous ne savez pas comment fonctionne l’outil, vous ne pourrez pas l’utiliser correctement. De manière générale, le moment est venu de vérifier et de mener une expérimentation pour enfin s'assurer au moins de la répartition.
La solution était simple et efficace : collecter des statistiques, obtenir des données objectives et examiner les résultats.
Sujet d'étude
Il existe plusieurs façons de générer des nombres aléatoires dans Unity – nous en avons testé cinq.
- Système.Random.Next(). Génère des entiers dans une plage de valeurs donnée.
- System.Random.NextDouble(). Génère des nombres en double précision compris entre [0 ; 1).
- UnityEngine.Random.Range(). Génère des nombres simple précision (flotteurs) dans une plage de valeurs donnée.
- UnityEngine.Random.value. Génère des nombres en simple précision (flotteurs) compris entre [0 ; 1).
- Unity.Mathematics.Random.NextFloat(). Fait partie de la nouvelle bibliothèque Unity.Mathematics. Génère des nombres simple précision (flotteurs) dans une plage de valeurs donnée.
Presque partout dans la documentation, une distribution uniforme a été spécifiée, à l'exception de UnityEngine.Random.value (où la distribution n'a pas été spécifiée, mais par analogie avec UnityEngine.Random.Range(), une distribution uniforme était également attendue) et Unity.Mathematics.Random .NextFloat() (où dans La base est l'algorithme xorshift, ce qui signifie que vous devez encore une fois attendre une distribution uniforme).
Par défaut, les résultats attendus ont été pris comme ceux spécifiés dans la documentation.
Méthodologie
Nous avons écrit une petite application qui générait des séquences de nombres aléatoires en utilisant chacune des méthodes présentées et enregistrait les résultats pour un traitement ultérieur.
La longueur de chaque séquence est de 100 000 nombres.
La plage de nombres aléatoires est [0, 100).
Les données ont été collectées à partir de plusieurs plateformes cibles :
- Windows
— Unity v2018.3.14f1, mode éditeur, Mono, .NET Standard 2.0 - macOS
— Unity v2018.3.14f1, mode éditeur, Mono, .NET Standard 2.0
— Unity v5.6.4p4, mode éditeur, Mono, .NET Standard 2.0 - Android
— Unity v2018.3.14f1, build par appareil, Mono, .NET Standard 2.0 - iOS
— Unity v2018.3.14f1, build par appareil, il2cpp, .NET Standard 2.0
exécution
Nous disposons de plusieurs manières différentes pour générer des nombres aléatoires. Pour chacun d’eux, nous écrirons une classe wrapper distincte, qui devrait fournir :
- Possibilité de paramétrer la plage de valeurs [min/max). Sera défini via le constructeur.
- Méthode renvoyant MF. Choisissons float comme type, car il est plus général.
- Le nom de la méthode de génération pour marquer les résultats. Pour plus de commodité, nous renverrons comme valeur le nom complet de la classe + le nom de la méthode utilisée pour générer le MF.
Tout d'abord, déclarons une abstraction qui sera représentée par l'interface IRandomGenerator :
namespace RandomDistribution
{
public interface IRandomGenerator
{
string Name { get; }
float Generate();
}
}Implémentation de System.Random.Next()
Cette méthode vous permet de définir une plage de valeurs, mais elle renvoie des entiers, mais des flottants sont nécessaires. Vous pouvez simplement interpréter un entier comme un flottant, ou vous pouvez élargir la plage de valeurs de plusieurs ordres de grandeur, en les compensant à chaque génération du milieu de gamme. Le résultat sera quelque chose comme un point fixe avec un ordre de précision donné. Nous utiliserons cette option car elle est plus proche de la valeur réelle du 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;
}
}Implémentation de System.Random.NextDouble()
Ici la plage de valeurs fixe [0; 1). Pour le projeter sur celui spécifié dans le constructeur, nous utilisons une arithmétique simple : 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;
}
}Implémentation de UnityEngine.Random.Range()
Cette méthode de la classe statique UnityEngine.Random permet de définir une plage de valeurs et renvoie un type float. Vous n'avez pas besoin d'effectuer de transformations supplémentaires.
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);
}
}Implémentation de UnityEngine.Random.value
La propriété value de la classe statique UnityEngine.Random renvoie un type float à partir d'une plage fixe de valeurs [0; 1). Projetons-le sur une plage donnée de la même manière que lors de l'implémentation de 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;
}
}Implémentation de Unity.Mathematics.Random.NextFloat()
La méthode NextFloat() de la classe Unity.Mathematics.Random renvoie une virgule flottante de type float et permet de spécifier une plage de valeurs. La seule nuance est que chaque instance de Unity.Mathematics.Random devra être initialisée avec une graine - de cette façon, nous éviterons de générer des séquences répétitives.
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);
}
}Implémentation de MainController
Plusieurs implémentations d'IRandomGenerator sont prêtes. Ensuite, vous devez générer des séquences et enregistrer l'ensemble de données résultant pour le traitement. Pour ce faire, nous allons créer une scène et un petit script MainController dans Unity, qui fera tout le travail nécessaire et sera en même temps responsable de l'interaction avec l'interface utilisateur.
Définissons la taille de l'ensemble de données et la plage des valeurs MF, et obtenons également une méthode qui renvoie un tableau de générateurs configurés et prêts à fonctionner.
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)
};
}
...
}
}Créons maintenant un ensemble de données. Dans ce cas, la génération des données sera combinée à l'enregistrement des résultats dans un flux texte (au format csv). Pour stocker les valeurs de chaque IRandomGenerator, sa propre colonne distincte est allouée et la première ligne contient le nom du générateur.
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();
}
}
...
}
}Il ne reste plus qu'à appeler la méthode GenerateCsvDataSet et à enregistrer le résultat dans un fichier, ou à transférer immédiatement les données sur le réseau du périphérique final vers le serveur de réception.
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();
}
}
...
}
}Les sources du projet sont à .
résultats
Aucun miracle ne s'est produit. Ce à quoi ils s’attendaient, c’est ce qu’ils ont obtenu : dans tous les cas, une répartition égale, sans la moindre trace de complot. Je ne vois pas l'intérêt de mettre des graphiques séparés pour les plates-formes - elles montrent toutes à peu près les mêmes résultats.
La réalité est :
Visualisation de séquences sur un plan issues des cinq méthodes de génération :
Et visualisation en 3D. Je ne laisserai que le résultat de System.Random.Next() afin de ne pas produire un tas de contenu identique.
L'histoire racontée dans l'introduction sur la distribution normale d'UnityEngine.Random ne s'est pas répétée : soit elle était initialement erronée, soit quelque chose a changé depuis dans le moteur. Mais maintenant nous en sommes sûrs.
Source: habr.com