Lo que es un buen generador de números aleatorios para el uso para un juego en C++?

Mis consideraciones son:

  1. Un montón de números aleatorios son necesarios, por lo que la velocidad es buena.
  2. Los jugadores siempre se quejan de números aleatorios, pero me gustaría ser capaz de apuntar a una referencia que explica lo que realmente me hizo mi trabajo.
  3. Ya que este es un proyecto comercial que no tengo mucho tiempo para el, sería agradable si el algoritmo que a) era relativamente fácil de implementar o b) tuvo una buena no-GPL aplicación disponible.
  4. Ya estoy utilizando rand() en mucho de los lugares, por lo que cualquier otro generador había mejor ser bueno para justificar todos los cambios que requeriría.

No sé mucho acerca de este tema, así que la única alternativa que se me ocurrió es la Mersenne Twister; que se cumplen con todos estos requisitos? ¿Hay algo más que es mejor?

Edición: Mersenne Twister parece ser el consenso de elección. Pero lo que sobre el punto #4? Es verdad que mucho mejor que la rand()?

Edit 2: permítanme ser un poco más claro sobre el punto 2: no Hay ninguna manera para que los jugadores de truco por el conocimiento de los números aleatorios. Período. Yo quiero lo suficientemente aleatorios que la gente (al menos los que entienden la aleatoriedad) no puede quejarse de ello, pero no estoy preocupado acerca de las predicciones.
Por eso he puesto la velocidad como la consideración principal.

Edit 3: me estoy inclinando hacia el Marsaglia RNGs ahora, pero me sigue gustando más la entrada. Por lo tanto, estoy configurando una recompensa.

Editar 4: Sólo una nota: tengo la intención de aceptar una respuesta justo antes de la medianoche UTC de hoy (no a meterse con alguien de la rep pac). Así que si estás pensando en responder, no espere hasta el último minuto!

También, me gusta el aspecto de Marsaglia del XORshift generadores. ¿Alguien tiene alguna entrada sobre ellos?

  • No dependen en cierta medida de lo que el perfil que desea que sus números al azar para tener; qué quiere estar distribuidos de manera uniforme? Gauss? Discreta o continua?
  • Stobor, puede generar otras distribuciones de los números aleatorios uniformes bastante bien.
  • Sí, sé que usted puede transformar cualquier tipo en cualquier otro tipo, pero si usted sabe que usted está usando principalmente la variable aleatoria en diferentes decisiones binarias (verdadero/falso, izquierda/derecha, etc), entonces usted puede aumentar la velocidad mediante el uso de un generador de binarios en lugar de utilizar un número entero una y calcular (x > RAND_MAX/2) todo el tiempo.
  • Yo estoy esperando una gota en el reemplazo para rand() (especialmente a todos los que «rand() % 10 líneas), así que prefiero distribuidos de manera uniforme y discretos.
  • He utilizado esta clase antes y es súper fácil de usar. Una de Mersenne Twister Clase es una clase creada a partir de la original del código C de el inventor de Mersenne Twister algoritmo.
  • No he hecho una comparación en un largo tiempo, pero aquí es un azar colecciones de enlaces, a otras personas comparaciones: * Universität Salzburg del pLab proyecto <aleatorio.mat.sbg.ac.en> * Dieharder: un algoritmo aleatorio de la suite de prueba <phy.duke.edu/~rgb/General/dieharder.php> * Wikipedia lista de PRNGS <en.wikipedia.org/wiki/List_of_random_number_generators> (voy a pop con algunos más adelante…)
  • SI usted sospecha de hacer trampa, ir con un crypographically generador de números aleatorios… blizzard lo hace (véase mi respuesta a continuación para el enlace)
  • Sobre el punto 4: rand (), que es débil en un número de maneras, pero sólo se puede decir si es «suficientemente bueno» para lo que estamos haciendo con él.
  • Esto no se contradice con las respuestas anteriores, pero no proporciona un poco de idea de por qué Mersenne Twister es muy valorada en C++: Una Propuesta para Agregar un Extensible Número Aleatorio de las Instalaciones de la Biblioteca Estándar Sección H da una visión general de los pros y los contras de más de algoritmos que alguna vez se pueden venir a través de, y todo el trabajo se aborda desde la perspectiva de un programador de C++.
  • >Mersenne Twister parece ser el consenso de elección. Pero lo que sobre el punto #4? Es verdad que mucho mejor que rand()? Verificar ianbullard.squarespace.com/journal/2009/4/28/…
  • He usado el impulso al azar de las bibliotecas, con juegos en el pasado. Se ha mercenne Twister boost.org/doc/libs/1_39_0/libs/random/index.html
  • Si está utilizando el editor vim, sólo podría utilizar el comando :%s/rand/newrand/g, y que sustituiría a cada instancia de «rand» con el nombre de su nueva función. Por no hablar de más decente de los editores tienen un método para buscar/reemplazar incorporado. La última vez que revisé, incluso el bloc de notas de Windows tenía esta característica. Si la función toma los parámetros de forma diferente, siempre se puede hacer un contenedor para minimizar la cantidad de edición repetitivas que tiene que hacer.
  • Además, es posible redefinir la constante RAND_MAX, si eso ayuda a todos. #undef RAND_MAX seguido por #define RAND_MAX [new max]

16 Comentarios

  1. 26

    George Marsaglia ha desarrollado algunos de los mejores y más rápidos generadores de números aleatorios disponibles en la actualidad
    Multiplicar-con-llevar ser una notable para una distribución uniforme.

    === Actualización 2018-09-12 ===

    Para mi propio trabajo, ahora estoy usando Xoshiro256**, que es una especie de evolución/actualización en Marsaglia del XorShift.

    • Se estaba viendo Marsaglia de la crítica en el artículo de Wikipedia sobre el Mersenne Twister que en realidad me hizo esta pregunta. ¿Alguien realidad el uso de estos, aunque?
    • No estoy seguro de cómo el uso generalizado de estas es pero he usado Marsaglia del xor-shift RNG en mi proyecto favorito y publicado el RNG como: codeproject.com/KB/cs/fastrandom.aspx Posteriormente, este código fue ued en un generador de números aleatorios de biblioteca de código: codeproject.com/KB/recipes/Random.aspx Y también me pidieron modificar la concesión de licencias para ser utilizado en algún proyecto en Novell, que se ejecuta en Mono.
    • He aceptado esto, porque en mis pruebas sencillas, el XOR de cambio de generador propuesto por Marsaglia fue por un justo margen, el más rápido de la competencia. Yo también considerar la posibilidad de cambiar a WELL512 en algún momento; he abstraído todas las llamadas a rand en un encapsulado de clase, de modo que es muy fácil cambiar la aplicación.
    • Gracias, lo elegimos por la velocidad también, mientras que también pasa Marsaglia la suite de RNG pruebas. Otro beneficio es que la semilla se puede restablecer rápidamente, mientras que otros generadores de números aleatorios requieren una rutina de inicialización para ejecutarse en settign la semilla. Esta es una característica útil si usted necesita para volver a generar exactamente la misma secuencia de números (comience con la misma semilla) y la necesidad de cambiar la semilla con frecuencia.
  2. 42

    A veces juego que los desarrolladores no quieren verdadera aleatoriedad y un shuffle bolsa es más apropiado.

    Si quieres que la aleatoriedad, el Mersenne twister satisface sus requisitos. Es rápido, estadísticamente aleatoria, tiene un largo período de tiempo y hay un montón de implementaciones de allí.

    Edición: rand() es que normalmente se implementa como un lineal congruential generador. Probablemente es mejor si usted hace una decisión informada de si es o no es lo suficientemente bueno para sus propósitos.

    • En el clavo. Sin esto, los jugadores se quejan de constantemente sobre las cosas demasiado al azar.
    • He leído que la pregunta ya (de hecho, se desató la discusión que llevó a esta pregunta), pero creo que no es la solución. Los «hits» de aquí se extraen de distancia del jugador, por lo que los jugadores probablemente no se de cuenta.
    • «Cuerpo vacío para bucles son de Satanás descendencia, pero vamos a ignorar esto por ahora.» +1 para una risa y una buena respuesta. (irónicamente, he usado un montón de ellos en Perl…)
  3. 38

    Hay mucho mejores opciones que la de Mersenne Twister hoy en día. Aquí es un generador de números aleatorios llamado WELL512, diseñado por los diseñadores de Mersenne, desarrollado 10 años más tarde, y todo alrededor una mejor opción para juegos. El código se coloca en el dominio público por el Dr. Chris Lomont. Él afirma que esta aplicación es 40% más rápido que el de Mersenne, no sufre de la poca difusión y la captura cuando el estado contiene muchos de los bits 0, y es claramente mucho más simple. Tiene un período de 2^512; un PC tarda más de 10^100 años para el ciclo a través de los estados, así que es bastante grande.

    Aquí es un papel resaltar PRNGs donde he encontrado la WELL512 aplicación.
    http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf

    Así – más rápido, más sencillo, creado por los mismos diseñadores 10 años más tarde, y produce mejores números de Mersenne. Cómo se puede ir mal? 🙂

    ACTUALIZACIÓN (11-18-14): Corregido error (cambiado 0xDA442D20UL a 0xDA442D24UL, como se describe en el documento enlazado más arriba).

    /* 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)&0xDA442D24UL);
       index = (index + 15)&15;
       a = state[index];
       state[index] = a^b^d^(a<<2)^(b<<18)^(c<<28);
       return state[index];
       }
    • Que es una buena.
    • Yo los residuos de una noche a entender por qué mi código no funciona en 64 bits máquinas de este código procude de 64 bits número! Uso sizeof(unsigned long) * 8
    • uso sizeof(unsigned long) * 8 en lugar de que parte?
    • La constante debe ser (según el original en papel): 0xDA442D24UL
    • comentario es correcto: 0xDA442D20UL debe ser 0xDA442D24UL. (He probado a editar esto hace más de un año, pero por alguna razón él fue rechazado.) Este problema de la versión fue dada en el Lomont_PRNG_2008.pdf documento enlazado más arriba, luego corregido (véase la sección de Historia en la final de este documento). Pero el código aquí todavía muestra la versión incorrecta. La implementación original por el BIEN de los creadores, para la comparación, está aquí: iro.umontreal.ca/~panneton/bien/WELL512a.c (tenga en cuenta que este cambio es muy pequeño, pero estas cosas pueden tener un enorme impacto en el generador de números aleatorios algoritmos).
    • otras personas que puedan leer esto): creo que quiere decir que los usuarios de este código debe comprobar el resultado de sizeof(unsigned long)*8 en su máquina/compilador… Si el resultado es de 64 (es decir, enteros largos sin signo de 64 bits de ancho), este código va a producir resultados inesperados porque se supone enteros largos sin signo de 32 bits de ancho. Comparar la implementación original aquí, que utiliza unsigned int en lugar de enteros largos sin signo: iro.umontreal.ca/~panneton/bien/WELL512a.c
    • Yo no estoy diciendo nada en contra de tu comentario, pero no es necesario sizeof(unsigned long)*8 para comprobar de 64 bits, usted puede comprobar sizeof(unsigned long) (por supuesto, suponiendo que char es de 8 bits). Así que, o hay otra razón para @RuggeroTurra comentario, o que no estaba prestando mucha atención.
    • Seguro que, por supuesto, el *8 es innecesario. Supongo que el propósito de su comentario fue simplemente el estado no firmados anhela tener diferentes tamaños (por ejemplo, 4 vs 8 bytes) en diferentes plataformas, y que el código que aparece aquí es problemático porque se supone unsigned anhela son de 4 bytes. (Para que los usuarios de este código, probablemente debería cambiar el unsigned anhela por ejemplo, a uint32_t.)
    • a PC takes over 10^100 years to cycle through the states es de 2008 de la demanda (de los de papel), y muy ambiguo. Por favor, puedes especificar mejor la velocidad de estimación?

  4. 10

    Mersenne Twister es típico en la industria, especialmente ya que se presta para SIMD y puede ser súper rápido. Knuth también es muy conocido (gracias, David).

    En la mayoría de las aplicaciones de juegos de velocidad es realmente el factor crítico, ya que los jugadores se van a quejarse de framerate baja mucho más de lo que se quejan del hecho de que hay un ligero sesgo hacia la generación de un 3 siempre es precedido por un 7, 2 y 9, en ese orden.

    La excepción, por supuesto, es el juego para el dinero, pero no su correspondiente licencia de la autoridad específica de diseñar los algoritmos que se pueden utilizar.

    • Ellos pueden quejarse mucho (y bastante fuerte) que el 3 nunca parece llegar a todo por ellos. Depende del uso. Realmente aleatorio es bueno para cosas como el daño, pero para cosas como elemento de gotas tiene sentido utilizar un algoritmo de barajado como @David Johnstone publicado.
    • Lo cierto es que; usted querrá un algoritmo diferente dependiendo de si la «justicia» o la verdadera aleatoriedad es más importante.
    • No llegar a ver realmente los números aleatorios, pero ellos se dan cuenta de que a veces se pierde cuando no se espera. (Estoy seguro de que ocurre a la inversa también, pero ellos casi nunca parece darse cuenta de ello.) Tal vez una distribución normal sería lo mejor para el combate de la parte.
    • También, la mayoría de los idiomas tienen un buen off-the-shelf implementación de MT disponible, y, probablemente, uno bajo una licencia que no le excluye de la incorporación de software comercial.
  5. 9

    Comprar una barata de la cámara web, un detector de humo de ionización. Desmontar los dos, detector de humo, contienen poco material radiactivo – una fuente de ondas gamma – que se traducirá en el despido de los fotones en su cámara web. Esa es su fuente de la verdadera aleatoriedad 🙂

    • De nuevo, yo realmente no se preocupan acerca de la verdadera aleatoriedad. Yo solo quiero que bastante cerca y bastante rápido.
    • Lo que es más rápido que un fotón?
    • Esta idea genera eventos en momentos aleatorios, pero no de bits aleatorios en la demanda. Además el humo detector de webcam de hardware va a ser visto como una copia de llave de protección hardware por la base de clientes.
    • Me gustaría comprar el juego sólo porque tiene una «protección de copia» dongle con un radiactivos etiqueta de advertencia en él!
  6. 6

    Mersenne Twister es muy buena, y es rápido. Yo lo he utilizado en un juego y no es difícil de poner en práctica o uso.

    La BIEN algoritmo aleatorio fue diseñado como una mejora sobre el Mersenne Twister. Juego De Gemas 7 tiene más información. en ella, si usted puede pedir prestado o que la tienen.

    En que página me enlazan, el número es el período en el algoritmo. Que es, usted puede conseguir 2^N – 1 números antes de que se necesita la resiembra, donde N es: 512, 1024, 19937, o 44497. Mersenne Twister tiene un periodo de N = 19937, o 2^19937 – 1. Vas a ver que este es un número muy grande 🙂

    Lo único que puedo señalar es que boost tiene un al azar de la biblioteca, que debe serle de utilidad.

    En respuesta a su edición, sí, el Twister o BIEN es que mucho mejor que rand(). También, el antiguo módulo de truco perjudica a la distribución de los números. Aún más razones para usar el boost 🙂

    • Es impulsar la pena sólo por números aleatorios? No estamos usando ahora mismo.
    • Boost es muy digno de él. Limpie C++ uso (sólo echa un vistazo a la página), junto con todas las otras cosas boost ofrece, como punteros inteligentes, de boost: funciones:lambda, hilos, etc… yo, básicamente, tratar de impulsar como la STL. Una vez que está establecido, que no es demasiado difícil, usted será capaz de olvidar que es aún allí, y se alegra cuando usted lo necesite.
    • Recuerde que el impulso no es o. Usted acaba de incluir el archivo de encabezado único que usted necesita, y eso es todo lo que tienes. La mayoría de las bibliotecas de boost es incluso solamente de cabecera de las bibliotecas, así que no hay necesidad de conectar nada, todo está en el archivo de encabezado.
  7. 4

    En un juego en tiempo real, no hay manera de que un jugador para determinar la diferencia entre un «buen» generador y un «malo». En un juego basado en turnos, tienes razón, algunos minoría de fanáticos que se quejan. Incluso vamos a contar historias, con doloroso detalle de cómo se arruinó sus vidas con un mal generador de números aleatorios.

    Si usted necesita un montón de auténticos números aleatorios (y es un juego en línea), usted puede conseguir algunos en Random.org. Los uso para juegos basados en turnos, o como semillas en tiempo real de los juegos.

    • Es semi-en tiempo real. Por ejemplo, en combate, el «cubo» se rodó cada 5 días de juego. Combates durarán un juego de mes o más, sin embargo.
    • Ah, y no basado en la web, por lo que random.org no es una opción.
    • Es totalmente posible experimentar la verdadera aleatoria frustración en un juego en tiempo real. Si, cada vez que se pulsa el «ataque» de botón, su espada echa de menos la rata gigante, usted va a ser tan molesto como si tuviera que pasar una «vuelta» en cada miss.
    • Eso es cierto, usted puede experimentar. A lo que me refería es que un usuario no puede identificar los números aleatorios que venían hacia él. Pero está en lo correcto de que el jugador a menudo no quiere verdaderos números aleatorios. Él quiere diversión números, que pueden tener una forma totalmente diferente de distribución. Pero el programador puede resolver el problema por el post-procesamiento «real» números aleatorios en diferentes secuencias o distribuciones.
    • random.org todavía puede ser una opción, incluso si el juego no está basado en la web. Si necesita cualquier tipo de conexión a internet, puede conectarse a la random.org en la demanda o usted puede solicitar una larga lista de números aleatorios en un spesified gama, almacenar y utilizar según sea necesario. Si te quedas sin precargadas randoms, puede volver a la buena vieja rand(). Una última nota: random.org utiliza el ruido estático de la entrada de sonido de modo que usted puede tratar de usar que también como semilla aleatoria.
  8. 4

    Soy un fan de Isaac, a diferencia de mersense twister, es crypographically seguro (que *no se puede romper el período de observación de los rollos)

    IBAA (rc4?) es también uno que es utilizados por blizzard para evitar que la gente de predecir el número aleatorio utilizado por el botín rollos.. me imagino que algo similar se realiza w/diablo II cuando usted está jugando fuera de un battle.net servidor.

    *no se puede dentro de cualquier periodo de tiempo razonable (siglos?)

  9. 3

    Basado en el generador de números aleatorios por Ian C. Bullard:

    //utils.hpp
    namespace utils {
        void srand(unsigned int seed);
        void srand();
        unsigned int rand();
    }
    
    //utils.cpp
    #include "utils.hpp"
    #include <time.h>
    
    namespace {
        static unsigned int s_rand_high = 1;
        static unsigned int s_rand_low = 1 ^ 0x49616E42;
    }
    
    void utils::srand(unsigned int seed)
    {
        s_rand_high = seed;
        s_rand_low = seed ^ 0x49616E42;
    }
    
    void utils::srand()
    {
        utils::srand(static_cast<unsigned int>(time(0)));
    }
    
    unsigned int utils::rand()
    {
        static const int shift = sizeof(int) / 2;
        s_rand_high = (s_rand_high >> shift) + (s_rand_high << shift);
        s_rand_high += s_rand_low;
        s_rand_low += s_rand_high;
        return s_rand_high;
    }

    ¿Por qué?

    • muy, muy rápido
    • una entropía más alta que la mayoría de los rand() implementaciones
    • fácil de entender
    • Ian tiene un interesante artículo en el que compara varios generadores. ianbullard.squarespace.com/journal/2009/4/28/…
    • Se supone que al dar una semilla de la que difiere sólo ligeramente usted sólo obtiene resultados ligeramente diferentes?
  10. 2

    Un criterio adicional que usted debe considerar es la seguridad de los subprocesos. (Y usted debe ser el uso de hilos en el hoy de los multi-core ambientes.) Con sólo llamar a rand de más de un subproceso puede meterse con él determinista del comportamiento (si su juego depende de que). Al menos yo te recomiendo cambiar a rand_r.

  11. 1

    Yo iba a votar por el Mersenne Twister así. Implementaciones están ampliamente disponibles, tiene un gran período de 2^19937 -1, es razonablemente rápido y pasa a la mayoría de la aleatoriedad de las pruebas, incluyendo la Diehard pruebas desarrolladas por Marsaglia. rand() y Co., se LCGs, producen menor calidad se desvía y sus valores sucesivos se pueden deducir fácilmente.

    Un punto de la nota, sin embargo, es propiamente la semilla de MT en un estado que pasa a la aleatoriedad de las pruebas. Generalmente un LCG como drand48() es utilizada para ese propósito.

    Yo diría que la MT cumple con todos los requisitos que hemos establecido (seguramente), y sería una exageración para ir por algo como MWCG de la omi.

  12. 0

    Quiero es lo suficientemente aleatorios que la gente (al menos los que entienden la aleatoriedad)
    no puede quejarse, pero no estoy preocupado acerca de las predicciones.

    A-ha!

    Ahí está su verdadero requisito!

    Nadie podría culpa de usted para el uso de Mersenne Twister en esta aplicación.

  13. 0

    Dependiendo del sistema operativo de destino, usted podría ser capaz de utilizar /dev/random. Realmente no requieren de su aplicación, y en Linux (y tal vez algunos otros sistemas operativos) es verdaderamente aleatorio. El leer los bloques hasta que no haya suficiente entropía está disponible, así que es posible que desee leer el archivo y guárdelo en un buffer o algo utilizando otro hilo. Si usted no puede utilizar un bloqueo de lectura de la llamada, puede utilizar /dev/urandom. Esto genera datos aleatorios casi tan bien como /dev/random, pero reutiliza algunos datos aleatorios para dar salida al instante. No es tan seguro, pero podría funcionar bien dependiendo de lo que usted planea hacer con ella.

    • El objetivo es el SO de Windows, con un Mac puerto en algún momento posterior.
  14. 0

    Al parecer (no recuerdo donde lo leí, igual me olvide de dónde he leído que el curry es buena para prevenir la altzheimas), tomando el valor absoluto de la suma de comprobación de un recién generado GUID es bien random. Es un gran número, y se puede utilizar un módulo de ella para encogerla.

    Así que en SQL (mi zona), este es el ABS(suma de comprobación(NEWID())) % 1000

    Rob

    • En serio? SQL? Él está hablando acerca de un JUEGO.
    • Seguro, pero si puede generar rápidamente un guid, entonces, el principio se aplica.
    • Es el GUID de la generación rápida de todos modos?
    • No estoy seguro acerca de la velocidad, la he mencionado porque, al parecer, la aleatoriedad es muy buena. Haciendo la suma de comprobación es probable que sea más lenta. Todo se reduce a cómo la predicción de los resultados debe ser.
    • Cualquier buen aleatoriedad que esto podría tener pruebas (¿alguien?) es frustrado por la falta de uniformidad introducido a través del modulo de operación.
    • Por qué? Si el objetivo del espacio dirigido por la suma de comprobación() es suficientemente mayor que el número a la derecha de %, entonces debe ser lo suficientemente aleatorio todavía. Si la suma de comprobación() sólo produce valores de menos de 1500, a continuación, % de 1000 es sesgada. Pero si es un número de alrededor de 9 billones de dólares, el skew es minúsculo.

  15. 0

    ¿Sabes qué? Perdóname si crees que esta respuesta completamente una mierda… Pero he sido (para sólo dios sabe por qué razón…) el uso de DateTime.Now.Milliseconds como una forma de obtener un número aleatorio. Sé que no es completamente aleatoria, pero parece ser…

    Yo simplemente no podía ser molestado a escribir mucho, SOLO para obtener un número aleatorio! 😛

    • La velocidad importa mucho el OP, por lo que probablemente será llamado muy frecuentemente, así que fácilmente podría conseguir el mismo milisegundos valores muchas veces. De todos modos el tiempo de muestreo en repetidas ocasiones, especialmente en el fijo de la velocidad de bucles tan típico en un juego, iba a comportarse de manera no aleatoria.

Dejar respuesta

Please enter your comment!
Please enter your name here