rand () donne à nouveau les mêmes nombres pour une petite plage

J'essaie de faire une sorte de jeu où j'ai une grille de 20x20 et j'affiche un joueur (P), une cible (T) et trois ennemis (X). Tous ceux-ci ont une coordonnée X et Y qui sont attribués à l'aide rand(). Le problème est que si j'essaie d'obtenir plus de points dans le jeu (recharges d'énergie, etc.), ils se chevauchent avec un ou plusieurs des autres points car la plage est petite (1 à 20 inclus).

Ce sont mes variables et comment je leur attribue des valeurs: (le COORDest un structavec juste un X et un Y)

const int gridSize = 20;
COORD player;
COORD target;
COORD enemy1;
COORD enemy2;
COORD enemy3;

//generate player
srand ( time ( NULL ) );
spawn(&player);
//generate target
spawn(&target);
//generate enemies
spawn(&enemy1);
spawn(&enemy2);
spawn(&enemy3);

void spawn(COORD *point)
{
    //allot X and Y coordinate to a point
    point->X = randNum();
    point->Y = randNum();
}

int randNum()
{
    //generate a random number between 1 and gridSize
    return (rand() % gridSize) + 1;
}

Je veux ajouter plus de choses au jeu, mais la probabilité de chevauchement augmente lorsque je le fais. Est-ce qu'il y a un moyen de réparer ceci?

Alors que les utilisateurs qui se plaignent rand()et recommandent de meilleurs RNG ont raison sur la qualité des nombres aléatoires, ils manquent également de vue d'ensemble. Les doublons dans les flux de nombres aléatoires ne peuvent être évités, ils sont une réalité de la vie. Telle est la leçon du problème des anniversaires .

Sur une grille de 20 * 20 = 400 positions de réapparition possibles, un point de réapparition en double est à prévoir (probabilité de 50%) même lors de la réapparition de seulement 24 entités. Avec 50 entités (toujours seulement 12,5% de l'ensemble du réseau), la probabilité d'un doublon est supérieure à 95%. Vous devez faire face aux collisions.

Parfois, vous pouvez dessiner tous les échantillons en même temps, puis vous pouvez utiliser un algorithme de lecture aléatoire pour dessiner ndes éléments garantis distincts. Il vous suffit de générer la liste de toutes les possibilités. Si la liste complète des possibilités est trop grande pour être stockée, vous pouvez générer des positions d'apparition une à la fois comme vous le faites maintenant (juste avec un meilleur RNG) et simplement recréer lorsqu'une collision se produit. Même si certaines collisions sont probables, de nombreuses collisions consécutives sont exponentiellement improbables même si la majeure partie de la grille est peuplée.

Si vous voulez toujours éviter de jouer une nouvelle entité dans un emplacement qui a déjà été alloué à autre chose, vous pouvez légèrement changer votre processus. Cela garantirait des emplacements uniques, mais cela nécessite un peu plus de frais généraux. Voici les étapes:

1. Configurer une collection de références à tous les emplacements possibles sur la carte (pour la carte 20x20, ce serait 400 emplacements)
2. Choisissez un emplacement au hasard dans cette collection de 400 (rand () fonctionnerait bien pour cela)
3. Supprimez cette possibilité de la collection d'emplacements possibles (elle a donc désormais 399 possibilités)
4. Répétez jusqu'à ce que toutes les entités aient un emplacement spécifié

Tant que vous supprimez l'emplacement de l'ensemble que vous choisissez, il ne devrait y avoir aucune chance qu'une deuxième entité reçoive le même emplacement (à moins que vous ne choisissiez les emplacements de plusieurs threads à la fois).

Un véritable analogue à cela serait de tirer une carte d'un jeu de cartes. Actuellement, vous mélangez le jeu, piochez une carte et la marquez, remettez la carte tirée dans le jeu, remélangez et dessinez à nouveau. L'approche ci-dessus saute de remettre la carte dans le jeu.

Relatif au fait d' rand() % nêtre loin d' être idéal

Faire rand() % na une distribution non uniforme. Vous obtiendrez un nombre disproportionné de certaines valeurs car le nombre de valeurs n'est pas un multiple de 20

Ensuite, il rand()s'agit généralement d'un générateur congruentiel linéaire (il y en a beaucoup d'autres , juste celui qui est le plus probable implémenté - et avec des paramètres moins qu'idéaux (il existe de nombreuses façons de sélectionner les paramètres)). Le plus gros problème avec cela est que souvent les bits bas (ceux que vous obtenez avec une % 20expression de type) ne sont pas si aléatoires. Je me souviens d'un rand()il y a des années où le bit le plus bas alternait de 1à 0à chaque appel à rand()- ce n'était pas très aléatoire.

Depuis la page de manuel de rand (3):

Les versions de rand () et srand () dans la bibliothèque Linux C utilisent les mêmes
générateur de nombres aléatoires comme random () et srandom (), donc l'ordre inférieur
les bits doivent être aussi aléatoires que les bits d'ordre supérieur. Cependant, sur les anciens
rand () implémentations, et sur les implémentations actuelles sur différents
systèmes, les bits d’ordre inférieur sont beaucoup moins aléatoires que les bits
commander des bits. N'utilisez pas cette fonction dans des applications destinées à
portable lorsqu'un bon caractère aléatoire est nécessaire.

Cela peut maintenant être relégué dans l'histoire, mais il est fort possible que vous ayez toujours une mauvaise implémentation de rand () cachée quelque part dans la pile. Dans ce cas, c'est encore tout à fait applicable.

La chose à faire est d'utiliser une bonne bibliothèque de nombres aléatoires (qui donne de bons nombres aléatoires), puis de demander des nombres aléatoires dans la plage souhaitée.

Un exemple d'un bon bit de code aléatoire (à partir de 13h00 dans la vidéo liée)

#include <iostream>
#include <random>
int main() {
    std::mt19937 mt(1729); // yes, this is a fixed seed
    std::uniform_int_distribution<int> dist(0, 99);
    for (int i = 0; i < 10000; i++) {
        std::cout << dist(mt) << " ";
    }
    std::cout << std::endl;
}

Comparez cela à:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
    srand(time(NULL));
    for (int i = 0; i < 10000; i++) {
        printf("%d ", rand() % 100);
    }
    printf("\n");
}

Exécutez ces deux programmes et comparez la fréquence à laquelle certains nombres apparaissent (ou ne s'affichent pas) dans cette sortie.

Vidéo connexe: rand () considéré comme nuisible

Quelques aspects historiques de rand () causant des bogues dans Nethack que l'on devrait regarder et considérer dans ses propres implémentations:

• Problème Nethack RNG

  Rand () est une fonction très fondamentale pour la génération de nombres aléatoires de Nethack. La façon dont Nethack l'utilise est boguée ou on peut soutenir que lrand48 () produit des nombres pseudo-aléatoires merdiques. (Cependant, lrand48 () est une fonction de bibliothèque utilisant une méthode PRNG définie et tout programme qui l'utilise devrait prendre en compte les faiblesses de cette méthode.)

  Le bogue est que Nethack s'appuie (parfois exclusivement comme c'est le cas dans rn (2)) sur les bits inférieurs des résultats de lrand48 (). Pour cette raison, RNG dans tout le jeu fonctionne mal. Ceci est particulièrement visible avant que les actions de l'utilisateur n'introduisent davantage d'aléatoire, c'est-à-dire dans la génération de caractères et la création de premier niveau.

Bien que ce qui précède date de 2003, il convient de garder à l'esprit car il se peut que tous les systèmes exécutant votre jeu ne soient pas un système Linux à jour avec une bonne fonction rand ().

Si vous faites cela par vous-même, vous pouvez tester la qualité de votre générateur de nombres aléatoires en écrivant du code et en testant la sortie avec ent .

Sur les propriétés des nombres aléatoires

Il existe d'autres interprétations de «aléatoire» qui ne sont pas exactement aléatoires. Dans un flux aléatoire de données, il est tout à fait possible d'obtenir deux fois le même nombre. Si vous lancez une pièce (au hasard), il est tout à fait possible d'obtenir deux têtes d'affilée. Ou lancez deux dés et obtenez le même numéro deux fois de suite. Ou faites tourner une roulette et obtenez deux fois le même numéro.

La répartition des nombres

Lors de la lecture d'une liste de chansons, les gens s'attendent à ce que «aléatoire» signifie que la même chanson ou le même artiste ne sera pas joué une deuxième fois de suite. Avoir une playlist jouer les Beatles deux fois de suite est considéré comme «non aléatoire» (bien qu'il soit aléatoire). La perception que pour une liste de lecture de quatre chansons a joué un total de huit fois:

1 3 2 4 1 2 4 3

est plus «aléatoire» que:

1 3 3 2 1 4 4 2

Plus d'informations à ce sujet pour le "mélange" des chansons: Comment mélanger les chansons?

Sur les valeurs répétées

Si vous ne voulez pas répéter des valeurs, il existe une approche différente qui doit être envisagée. Générez toutes les valeurs possibles et mélangez-les.

Si vous appelez rand()(ou tout autre générateur de nombres aléatoires), vous l'appelez avec remplacement. Vous pouvez toujours obtenir le même numéro deux fois. Une option consiste à lancer les valeurs encore et encore jusqu'à ce que vous en sélectionniez une qui réponde à vos besoins. Je soulignerai que cela a un runtime non déterministe et il est possible que vous vous retrouviez dans une situation où il y a une boucle infinie à moins que vous ne commenciez à faire un traçage arrière plus complexe.

Liste et sélection

Une autre option consiste à générer une liste de tous les états valides possibles, puis à sélectionner un élément aléatoire dans cette liste. Trouvez tous les espaces vides (qui répondent à certaines règles) dans la salle, puis choisissez-en un au hasard dans cette liste. Et puis faites-le encore et encore jusqu'à ce que vous ayez terminé.

Shuffle

L'autre approche consiste à mélanger comme s'il s'agissait d'un jeu de cartes. Commencez par tous les espaces vides dans la salle, puis commencez à les attribuer en distribuant les espaces vides, un par un, à chaque règle / processus en demandant un espace vide. Vous avez terminé lorsque vous n'avez plus de cartes ou que les choses cessent de les demander.

La solution la plus simple à ce problème a été citée dans les réponses précédentes: il s'agit de faire une liste de valeurs aléatoires à côté de chacune de vos 400 cellules, puis de trier cette liste aléatoire. Votre liste de cellules sera triée en tant que liste aléatoire, et de cette façon, sera mélangée.

Cette méthode a l'avantage d'éviter totalement le chevauchement de cellules sélectionnées au hasard.

L'inconvénient est que vous devez calculer une valeur aléatoire sur une liste distincte pour chacune de vos cellules. Donc, vous préférez ne pas le faire pendant le début du jeu.

Voici un exemple de la façon dont vous pouvez le faire:

#include <algorithm>
#include <iostream>
#include <vector>

#define NUMBER_OF_SPAWNS 20
#define WIDTH 20
#define HEIGHT 20

typedef struct _COORD
{
  int x;
  int y;
  _COORD() : x(0), y(0) {}
  _COORD(int xp, int yp) : x(xp), y(yp) {}
} COORD;

typedef struct _spawnCOORD
{
  float rndValue;
  COORD*coord;
  _spawnCOORD() : rndValue(0.) {}
} spawnCOORD;

struct byRndValue {
  bool operator()(spawnCOORD const &a, spawnCOORD const &b) {
    return a.rndValue < b.rndValue;
  }
};

int main(int argc, char** argv)
{
  COORD map[WIDTH][HEIGHT];
  std::vector<spawnCOORD>       rndSpawns(WIDTH * HEIGHT);

  for (int x = 0; x < WIDTH; ++x)
    for (int y = 0; y < HEIGHT; ++y)
      {
        map[x][y].x = x;
        map[x][y].y = y;
        rndSpawns[x + y * WIDTH].coord = &(map[x][y]);
        rndSpawns[x + y * WIDTH].rndValue = rand();
      }

  std::sort(rndSpawns.begin(), rndSpawns.end(), byRndValue());

  for (int i = 0; i < NUMBER_OF_SPAWNS; ++i)
    std::cout << "Case selected for spawn : " << rndSpawns[i].coord->x << "x"
              << rndSpawns[i].coord->y << " (rnd=" << rndSpawns[i].rndValue << ")\n";
  return 0;
}

Résultat:

root@debian6:/home/eh/testa# ./exe 
Case selected for spawn : 11x15 (rnd=6.93951e+06)
Case selected for spawn : 14x1 (rnd=7.68493e+06)
Case selected for spawn : 8x12 (rnd=8.93699e+06)
Case selected for spawn : 18x13 (rnd=1.16148e+07)
Case selected for spawn : 1x0 (rnd=3.50052e+07)
Case selected for spawn : 2x17 (rnd=4.29992e+07)
Case selected for spawn : 9x14 (rnd=7.60658e+07)
Case selected for spawn : 3x11 (rnd=8.43539e+07)
Case selected for spawn : 12x7 (rnd=8.77554e+07)
Case selected for spawn : 19x0 (rnd=1.05576e+08)
Case selected for spawn : 19x14 (rnd=1.10613e+08)
Case selected for spawn : 8x2 (rnd=1.11538e+08)
Case selected for spawn : 7x2 (rnd=1.12806e+08)
Case selected for spawn : 19x15 (rnd=1.14724e+08)
Case selected for spawn : 8x9 (rnd=1.16088e+08)
Case selected for spawn : 2x19 (rnd=1.35497e+08)
Case selected for spawn : 2x16 (rnd=1.37807e+08)
Case selected for spawn : 2x8 (rnd=1.49798e+08)
Case selected for spawn : 7x16 (rnd=1.50123e+08)
Case selected for spawn : 8x11 (rnd=1.55325e+08)

Modifiez simplement NUMBER_OF_SPAWNS pour obtenir des cellules plus ou moins aléatoires, cela ne changera pas le temps de calcul requis pour la tâche.