Qu'est-ce qu'un bon générateur de nombres aléatoires pour un jeu?

Question

Ce qui est un bon générateur de nombres aléatoires à utiliser pour un jeu en C++?

Mes critères sont les suivants:

1. Beaucoup de nombres aléatoires sont nécessaires, de sorte que la vitesse est bonne.
2. Les joueurs vont se plaignent toujours des nombres aléatoires, mais je voudrais être en mesure de les faire pointer vers un document de référence qui explique que j'ai vraiment fait de mon travail.
3. Puisque c'est un projet commercial qui je n'ai pas beaucoup de temps, ce serait bien si l'algorithme a) a été relativement facile à mettre en œuvre ou b) a un bon non-GPL mise en œuvre disponibles.
4. Je suis déjà en utilisant rand() dans beaucoup d'endroits, de sorte que toute autre générateur a intérêt à être bon à justifier toutes les modifications qu'il en aurait besoin.

Je ne sais pas beaucoup sur ce sujet, de sorte que la seule alternative qui me vient en tête est le Mersenne Twister; t-il de répondre à ces exigences? Est-il rien d'autre qui est mieux?

Edit: Mersenne Twister semble être le consensus choix. Mais qu'en est point #4? Est-il vraiment beaucoup mieux que rand()?

Edit 2: Permettez-moi d'être un peu plus clair sur le point 2: Il n'existe aucun moyen pour les joueurs de tricher en connaissant les nombres aléatoires. Période. Je veux qu'il aléatoires que les gens (au moins ceux qui comprennent l'aléatoire) ne peut pas s'en plaindre, mais je ne suis pas inquiet au sujet des prédictions. C'est pourquoi j'ai mis la vitesse comme la préoccupation principale.

Edit 3: je suis penchée vers l'Marsaglia Rng maintenant, mais je voudrais encore plus de commentaires. Donc, je suis la mise en place d'une prime.

Edit 4: Juste une remarque: j'ai l'intention d'accepter une réponse juste avant minuit UTC aujourd'hui (pour éviter de jouer avec quelqu'un rep cap). Donc, si vous envisagez de répondre, n'attendez pas la dernière minute!
Aussi, j'aime le look de Marsaglia de XORshift générateurs. Quelqu'un a une entrée à leur sujet?

Answer 1

Parfois, les développeurs de jeux ne veulent pas de l'aléatoire véritable et un shuffle sac est plus approprié.

Si vous ne voulez pas de hasard, le Mersenne twister répond à vos exigences. Il est rapide, statistiquement aléatoire, a une longue période et il y a beaucoup de mises en œuvre là-bas.

Edit: rand() est généralement mis en œuvre comme un générateur linéaire à congruence. Il est probablement mieux si vous faites un choix éclairé de si oui ou non il est assez bon pour vos fins.

Answer 2

Il y a beaucoup de meilleurs choix que Mersenne Twister de nos jours. Voici un RNG appelé WELL512, conçu par les designers de Mersenne, développé 10 ans plus tard, et un tout autour de meilleur choix pour les jeux. Le code est placé dans le domaine public par le Dr Chris Lomont. Il prétend que cette mise en œuvre est 40% plus rapide que le nombre de Mersenne, ne souffre pas de la mauvaise diffusion et de piégeage lorsque l'état contient de nombreuses 0 bits, et est clairement beaucoup plus simple de code. Il dispose d'un délai de 2^512; un PC de plus de 10^100 ans pour faire défiler les états, de sorte qu'il est assez grand.

Voici un papier avec vue sur la PRNGs où j'ai trouvé la WELL512 mise en œuvre. http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf

Donc, plus rapide, plus simple, créé par les mêmes concepteurs 10 ans plus tard, et produit de meilleurs nombres de Mersenne. Comment pouvez-vous vous tromper? :)

/* initialize state to random bits */
static unsigned long state[16];
/* init should also reset this to 0 */
static unsigned int index = 0;
/* return 32 bit random number */
unsigned long WELLRNG512(void)
   {
   unsigned long a, b, c, d;
   a = state[index];
   c = state[(index+13)&15];
   b = a^c^(a<<16)^(c<<15);
   c = state[(index+9)&15];
   c ^= (c>>11);
   a = state[index] = b^c;
   d = a^((a<<5)&0xDA442D20UL);
   index = (index + 15)&15;
   a = state[index];
   state[index] = a^b^d^(a<<2)^(b<<18)^(c<<28);
   return state[index];
   }

Answer 3

George Marsaglia a mis au point certains des meilleurs et des plus rapides RNG actuellement disponibles. Multiply-with-carry est un modèle remarquable pour une distribution uniforme.

Answer 4

Mersenne Twister est typique dans l'industrie, surtout depuis qu'il se prête bien à SIMD, et peut être fait super vite. Knuth est aussi très populaire (merci David).

Dans la plupart des applications de jeu de vitesse est vraiment le facteur déterminant, puisque les joueurs vont se plaindre de framerate beaucoup plus que ils se plaignent du fait qu'il y a un léger biais en faveur de la génération d'un 3 quand il est précédé par un 7, 2, et 9, dans cet ordre.

L'exception est bien sûr les jeux de hasard pour de l'argent, mais il y a de votre autorité de délivrance des autorisations spécifiquement poser les algorithmes que vous pouvez utiliser.

Answer 5

Achetez une webcamera pas cher, un détecteur de fumée ionisant. Démontez les deux, le détecteur de fumée contient peu de matières radioactives - une source d’ondes gamma - ce qui entraînera la décharge de photons sur votre webcam. C'est ta source de vrai hasard :)