c++ - rango - generar numeros aleatorios en java del 1 al 100
¿Qué es un buen generador de números aleatorios para un juego? (16)
¿Qué es un buen generador de números aleatorios para usar en un juego en C ++?
Mis consideraciones son:
- Se necesitan muchos números aleatorios, por lo que la velocidad es buena.
- Los jugadores siempre se quejarán de números aleatorios, pero me gustaría poder señalarles una referencia que explique que realmente hice mi trabajo.
- Dado que este es un proyecto comercial para el que no tengo mucho tiempo, sería bueno si el algoritmo: a) fuera relativamente fácil de implementar ob) tuviera una buena implementación no GPL disponible.
- Ya estoy usando
rand()
en muchos lugares, por lo que cualquier otro generador sería mejor para justificar todos los cambios que requeriría.
No sé mucho sobre este tema, así que la única alternativa que podría surgir es el Mersenne Twister ; satisface todos estos requisitos? ¿Hay algo más que sea mejor?
Editar: Mersenne Twister parece ser la elección de consenso. Pero, ¿qué pasa con el punto n. ° 4? ¿Es realmente mucho mejor que rand()
?
Edición 2: Déjame ser un poco más claro en el punto 2: no hay forma de que los jugadores hagan trampa al conocer los números aleatorios. Período. Lo quiero lo suficientemente al azar como para que las personas (al menos aquellos que entienden la aleatoriedad) no puedan quejarse, pero no me preocupan las predicciones. Es por eso que pongo la velocidad como la principal consideración.
Edición 3: me estoy inclinando hacia los RNGs de Marsaglia ahora, pero aún me gustaría obtener más información. Por lo tanto, estoy preparando una recompensa.
Edición 4: solo una nota: tengo la intención de aceptar una respuesta justo antes de la medianoche UTC de hoy (para evitar meterme con el gorro de representante de alguien). Entonces, si estás pensando en responder, ¡no esperes hasta el último minuto!
Además, me gusta el aspecto de los generadores XORshift de Marsaglia. ¿Alguien tiene alguna información sobre ellos?
Lo quiero lo suficientemente al azar como para que las personas (al menos aquellos que entienden la aleatoriedad) no puedan quejarse, pero no me preocupan las predicciones.
A-ha!
¡Aquí está su verdadero requerimiento!
Nadie puede culparlo por usar Mersenne Twister en esta aplicación.
¿Sabes que? Perdóneme si cree que esta respuesta es una mierda por completo ... Pero he estado (por dios solo sabe qué razón ...) usando DateTime.Now.Milliseconds
como una forma de obtener un número aleatorio. Sé que no es completamente aleatorio, pero parece ser ...
¡No podía molestarme en tipear tanto para obtener un número al azar! :PAG
Aparentemente (se me olvida dónde lo leí, al igual que olvidé donde leí que el curry es bueno para evitar altzheimas), tomar el valor absoluto de la suma de comprobación de un GUID recién generado es muy aleatorio. Es un número grande, y puedes usar un módulo para reducirlo.
Entonces en SQL (mi área), esto es ABS (CHECKSUM (NEWID ()))% 1000
Robar
Basado en el generador de números aleatorios de 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 rapido
- mayor entropía que la mayoría de las implementaciones estándar de
rand()
- fácil de comprender
Compre una cámara web barata, un detector de humo ionizante. Desarme ambos, el detector de humo contiene poco material radiactivo, una fuente de ondas gamma, lo que dará como resultado el disparo de fotones en su cámara web. Esa es tu fuente de verdadera aleatoriedad :)
Dependiendo del sistema operativo objetivo, es posible que pueda usar / dev / random. Realmente no requiere ninguna implementación, y en Linux (y tal vez algunos otros sistemas operativos) es verdaderamente aleatorio. Los bloques de lectura hasta que haya suficiente entropía están disponibles, por lo que es posible que desee leer el archivo y almacenarlo en un búfer o algo utilizando otro hilo. Si no puede usar una llamada de lectura bloqueada, puede usar / dev / urandom. Genera datos aleatorios casi tan bien como / dev / random, pero reutiliza algunos datos aleatorios para dar salida instantáneamente. No es tan seguro, pero podría funcionar bien dependiendo de lo que planeas hacer con él.
En un juego en tiempo real, no hay forma de que un jugador determine la diferencia entre un generador "bueno" y uno "malo". En un juego por turnos, tienes razón: una minoría de fanáticos se quejará. Incluso te contarán historias, con detalles insoportables, de cómo arruinaste sus vidas con un generador de números aleatorios malo.
Si necesita un grupo de números aleatorios genuinos (y usted es un juego en línea), puede obtener algunos en Random.org . Úselos para juegos por turnos, o como semillas para juegos en tiempo real.
GameRand implementa el algoritmo publicado aquí http://www.flipcode.com/archives/07-15-2002.shtml
Esto es algo que desarrollé originalmente a fines de los años 80. Fácilmente supera a rand () en términos de calidad numérica, y como el beneficio secundario es el algoritmo aleatorio más rápido posible.
Hay opciones mucho mejores que Mersenne Twister hoy en día. Aquí hay un RNG llamado WELL512, diseñado por los diseñadores de Mersenne, desarrollado 10 años después, y una mejor opción para los juegos. El Dr. Chris Lomont pone el código en el dominio público. Afirma que esta implementación es 40% más rápida que Mersenne, no sufre de mala difusión y atrapamiento cuando el estado contiene muchos 0 bits, y es claramente un código mucho más simple. Tiene un período de 2 ^ 512; una PC tarda más de 10 ^ 100 años en recorrer los estados, por lo que es lo suficientemente grande.
Aquí hay un documento que describe los PRNG donde encontré la implementación de WELL512. http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf
Entonces, más rápido, más simple, creado por los mismos diseñadores 10 años después, y produce mejores números que Mersenne. ¿Cómo puedes equivocarte? :)
ACTUALIZACIÓN (18/11/14) : error solucionado (cambiado 0xDA442D20UL a 0xDA442D24UL, como se describe en el documento vinculado anteriormente).
/* 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];
}
Mersenne Twister es muy bueno, y también rápido. Lo usé en un juego y no es difícil de implementar o usar.
El algoritmo aleatorio WELL fue diseñado como una mejora sobre el Mersenne Twister. Game Gems 7 tiene más información. en él, si puedes tomar prestado o tenerlo.
En esa página WELL a la que te conecté, el número es el período del algoritmo. Es decir, puede obtener 2 ^ N - 1 números antes de que sea necesario volver a sembrar, donde N es: 512, 1024, 19937 o 44497. Mersenne Twister tiene un período de N = 19937 o 2 ^ 19937 - 1. ver que este es un número muy grande :)
La única otra cosa que puedo señalar es que boost tiene una biblioteca aleatoria , que debería ser útil.
En respuesta a su edición, sí Twister o WELL es mucho mejor que rand (). Además, el viejo truco de módulo daña la distribución de los números. Aún más razón para usar boost :)
Mersenne Twister es típico en la industria, especialmente porque se presta bien a SIMD y se puede hacer muy rápido. Knuth es popular (gracias, David).
En la mayoría de las aplicaciones de juegos, la velocidad es realmente el factor crítico, ya que los jugadores se quejarán de un framerate bajo mucho más de lo que se quejarán por el hecho de que hay un ligero sesgo hacia la generación de un 3 siempre que esté precedido por un 7, 2, y 9 en ese orden.
La excepción, por supuesto, es el juego por dinero, pero allí su autoridad relevante de licencias especificará específicamente los algoritmos que puede usar.
Soy fanático de Isaac , a diferencia del torbellino mersense, es crígráficamente seguro (no puedes descifrar el período observando los rollos)
IBAA (rc4?) También es utilizado por Blizzard para evitar que la gente prediga el número aleatorio utilizado para los rollos de botín. Imagino que se hace algo similar con Diablo II cuando juegas fuera de un servidor battle.net.
* no puede dentro de un marco de tiempo razonable (¿siglos?)
Un criterio adicional que debe considerar es la seguridad de subprocesos. (Y deberías usar subprocesos en los entornos multinúcleos de hoy en día). Solo llamar a rand de más de un hilo puede interferir con su comportamiento determinista (si tu juego depende de eso). Por lo menos, recomendaría que cambies a rand_r.
Yo votaría por el Mersenne Twister también. Las implementaciones están ampliamente disponibles, tiene un período muy largo de 2 ^ 19937 -1, es razonablemente rápido y pasa la mayoría de las pruebas de aleatoriedad, incluidas las pruebas Diehard desarrolladas por Marsaglia. Rand () y Co., que son LCG, producen desviaciones de menor calidad y sus valores sucesivos se pueden inferir fácilmente.
Un punto a destacar, sin embargo, es sembrar apropiadamente MT en un estado que pase las pruebas de aleatoriedad. Por lo general, un LCG como drand48 () se utiliza para ese fin.
Yo diría que el MT cumple con todos los requisitos que has establecido (de manera demostrable), y sería una exageración buscar algo como MWCG imo.
Sometimes desarrolladores de juegos no quieren una aleatoriedad real y una baraja es más apropiada.
Si desea aleatoriedad, el tornado Mersenne satisface sus requisitos. Es rápido, estadísticamente aleatorio, tiene un largo período y hay muchas implementaciones.
Edición: rand()
se implementa típicamente como un generador congruente lineal . Probablemente sea mejor si toma una decisión informada de si es o no lo suficientemente bueno para sus propósitos.
George Marsaglia ha desarrollado algunos de los mejores y más rápidos RNG actualmente disponibles. Multiply-with-carry es notable para una distribución uniforme.