Random number generator

From RogueBasin
(Difference between revisions)
Jump to: navigation, search
(Someday I will go after the NetHack variants' RNG bugs, but for now I expand this document about RNGs.)
Line 1: Line 1:
A '''Random number generator''', or '''RNG''' for short, is a special algorithm that returns a pseudo-aleatory number in certain range each time it is activated, based on a "seed" or initial number from which an infinite sequence is deduced. Some RNG algorithms use techniques derived from the fractal and chaos theories.
+
A '''random number generator''', or '''RNG''' for short, is a special algorithm that returns a pseudo-aleatory number, the next number of an infinite sequence deduced from a "seed" or initial number. Roguelike games use the RNG to compute [[dice]] rolls and in other cases that require [[random generation]]. Some RNG algorithms evaluate simple polynomials, while others use techniques derived from the fractal and chaos theories.
  
The RNG is also sometimes refered to as the '''Random Number God''', the entity inside a game that provides random functionality.
+
Many players refer to the RNG as the '''Random Number God''', the entity inside the game that provides random functionality. This diety seems to leave great [[item]]s and easy [[monster]]s for some players, while granting seemingly-unfair deaths to others. Some players superstitiously avoid offending the Random Number God.
 +
 
 +
== Algorithms ==
 +
All RNG algorithms start with an initial ''seed''. The algorithm uses the seed to compute its initial ''state''. To compute the next random number, the algorithm applies some formula to calculate the next state from the current state, then it uses the state to produce a number from a certain range.
 +
 
 +
Some RNGs produce integers, while others produce floating-point. Most roguelikes want integers; conversion from floating-point is often easy as multiply and floor.
 +
 
 +
After very many uses, any RNG algorithm will ''cycle'' as it reaches a state equal to its initial state. After this, the RNG will begin to compute the exact sequence of random numbers again! A good RNG would have a very long ''period'' so that it practically never cycles.
 +
 
 +
If an eavesdropper (who does not know the seed) can use a sequence of outputs from the RNG to predict the next random number, then the RNG is not cryptographically secure. Conveniently, cryptographic security is not important for roguelikes.
 +
 
 +
=== Seeding ===
 +
Some RNGs seed themselves differently each time, but other RNGs use the same default seed every time unless you remember to seed them. If every game uses the same seed, then it will roll the same character and (if the opening map is random) start at the same map every time! You can observe this if you intentionally set a particular seed during testing, or if the game has a bug that prevents it from setting the seed. For example, [http://sourceforge.net/tracker/index.php?func=detail&aid=1380333&group_id=9746&atid=109746 SLASH'EM bug 1380333] was the result of a game, in some configurations, seeding one random number generator but using another.
 +
 
 +
A simple way to grow a different seed every game is to use the current time as a seed. This traditional method is barely enough to give the player a different experience every time.
  
 
== RNG in programming languages ==
 
== RNG in programming languages ==
 +
Most programming environments provide an RNG. Typically, a game will:
 +
# seed the RNG, if necessary
 +
# provide its own functions to access the RNG, so that
 +
#* one can change to a different RNG later
 +
#* one can convert the RNG's output to the correct range
 +
 +
=== C and C++ ===
 +
In [[C]] and [[Cpp|C++]], the random number generator is the <tt>rand()</tt> function. One sets the seed with <tt>srand()</tt>. Some call these the "ANSI C" (or equivalently "ISO C") functions because they are part of the C standard and to distinguish them from other RNGs that some systems provide.
 +
 +
The rand() function returns an int in the range from 0 to RAND_MAX, a platform-dependent value. Here is a simple program to show one random value:
 +
 +
<pre>
 +
#include <stdlib.h> /* rand, srand */
 +
#include <stdio.h>  /* printf (for this example) */
 +
#include <time.h>  /* time */
 +
 +
int main() {
 +
  srand( (unsigned int)time(NULL) );
 +
  printf("%d\n", rand());
 +
  return 0;
 +
}
 +
</pre>
 +
 +
Many programmers like to seed srand() with the return value of <tt>time()</tt>, as we do above. In fact, if we run this program multiple times within one second, it may print the same number again. (Some will write "srand( time(0) )", which is bad because the time function takes a pointer. Using NULL reminds you that it is a pointer, and prevents bugs on machines where a pointer has 64 bits but a 0 has only 32 bits. The cast to unsigned int is optional, but we added it to satisfy [http://www.freebsd.org/cgi/man.cgi?query=lint <tt>lint</tt>].)
 +
 +
Now we come to an important note: '''Many platforms have poor-quality versions of the rand() function.''' Above [[GNU]] platforms, rand() and srand() work relatively well, and [http://www.gnu.org/software/libc/manual/html_node/Pseudo_002dRandom-Numbers.html ''The GNU C Library Reference Manual''] recommends their use. If your favorite platform is GNU or Linux, then you could program with rand() and srand() and have your game at least working above other C platforms. But the most popular roguelike games support many platforms well, and their developers avoid rand() when they can.
 +
 +
[[BSD]] platforms implement rand() and srand() in terms of [http://www.freebsd.org/cgi/man.cgi?query=rand_r <tt>rand_r()</tt>], which limits the state of the RNG to 32 bits (implying a period of 2**31-1 or less). BSD calls this a "bad random number generator", while GNU states that 32 bits is "far too few to provide a good RNG."
 +
 +
Meanwhile, though RAND_MAX is platform dependent, BSD and GNU use 2,147,483,647, the largest possible signed int. One should be warned that on MSVC, RAND_MAX is 32,767, which may be a lot smaller than you expect.
  
In [[C]] and [[Cpp|C++]], the random number generator is the rand() function. One sets the seed with srand(). The maximum range for the random numbers is RAND_MAX, which is platform dependent. One should be warned that on MSVC, this is 32,767, which may be a lot smaller than you expect. If in doubt, you should implement a new RNG.
+
If in doubt, you should implement a new RNG.
  
 +
=== Java ===
 
On the other hand, in [[Java]] the commonly used RNG resides in the Random class, which uppon initialized with a seed or the system time, returns pseudo-aleatory values of different primitive types. For example, you may invoke the method nextDouble() to get a value from 0.0D to 1.0D, which you may then scale to any range you need.
 
On the other hand, in [[Java]] the commonly used RNG resides in the Random class, which uppon initialized with a seed or the system time, returns pseudo-aleatory values of different primitive types. For example, you may invoke the method nextDouble() to get a value from 0.0D to 1.0D, which you may then scale to any range you need.
  

Revision as of 05:47, 25 December 2006

A random number generator, or RNG for short, is a special algorithm that returns a pseudo-aleatory number, the next number of an infinite sequence deduced from a "seed" or initial number. Roguelike games use the RNG to compute dice rolls and in other cases that require random generation. Some RNG algorithms evaluate simple polynomials, while others use techniques derived from the fractal and chaos theories.

Many players refer to the RNG as the Random Number God, the entity inside the game that provides random functionality. This diety seems to leave great items and easy monsters for some players, while granting seemingly-unfair deaths to others. Some players superstitiously avoid offending the Random Number God.

Contents

Algorithms

All RNG algorithms start with an initial seed. The algorithm uses the seed to compute its initial state. To compute the next random number, the algorithm applies some formula to calculate the next state from the current state, then it uses the state to produce a number from a certain range.

Some RNGs produce integers, while others produce floating-point. Most roguelikes want integers; conversion from floating-point is often easy as multiply and floor.

After very many uses, any RNG algorithm will cycle as it reaches a state equal to its initial state. After this, the RNG will begin to compute the exact sequence of random numbers again! A good RNG would have a very long period so that it practically never cycles.

If an eavesdropper (who does not know the seed) can use a sequence of outputs from the RNG to predict the next random number, then the RNG is not cryptographically secure. Conveniently, cryptographic security is not important for roguelikes.

Seeding

Some RNGs seed themselves differently each time, but other RNGs use the same default seed every time unless you remember to seed them. If every game uses the same seed, then it will roll the same character and (if the opening map is random) start at the same map every time! You can observe this if you intentionally set a particular seed during testing, or if the game has a bug that prevents it from setting the seed. For example, SLASH'EM bug 1380333 was the result of a game, in some configurations, seeding one random number generator but using another.

A simple way to grow a different seed every game is to use the current time as a seed. This traditional method is barely enough to give the player a different experience every time.

RNG in programming languages

Most programming environments provide an RNG. Typically, a game will:

  1. seed the RNG, if necessary
  2. provide its own functions to access the RNG, so that
    • one can change to a different RNG later
    • one can convert the RNG's output to the correct range

C and C++

In C and C++, the random number generator is the rand() function. One sets the seed with srand(). Some call these the "ANSI C" (or equivalently "ISO C") functions because they are part of the C standard and to distinguish them from other RNGs that some systems provide.

The rand() function returns an int in the range from 0 to RAND_MAX, a platform-dependent value. Here is a simple program to show one random value:

#include <stdlib.h> /* rand, srand */
#include <stdio.h>  /* printf (for this example) */
#include <time.h>   /* time */

int main() {
  srand( (unsigned int)time(NULL) );
  printf("%d\n", rand());
  return 0;
}

Many programmers like to seed srand() with the return value of time(), as we do above. In fact, if we run this program multiple times within one second, it may print the same number again. (Some will write "srand( time(0) )", which is bad because the time function takes a pointer. Using NULL reminds you that it is a pointer, and prevents bugs on machines where a pointer has 64 bits but a 0 has only 32 bits. The cast to unsigned int is optional, but we added it to satisfy lint.)

Now we come to an important note: Many platforms have poor-quality versions of the rand() function. Above GNU platforms, rand() and srand() work relatively well, and The GNU C Library Reference Manual recommends their use. If your favorite platform is GNU or Linux, then you could program with rand() and srand() and have your game at least working above other C platforms. But the most popular roguelike games support many platforms well, and their developers avoid rand() when they can.

BSD platforms implement rand() and srand() in terms of rand_r(), which limits the state of the RNG to 32 bits (implying a period of 2**31-1 or less). BSD calls this a "bad random number generator", while GNU states that 32 bits is "far too few to provide a good RNG."

Meanwhile, though RAND_MAX is platform dependent, BSD and GNU use 2,147,483,647, the largest possible signed int. One should be warned that on MSVC, RAND_MAX is 32,767, which may be a lot smaller than you expect.

If in doubt, you should implement a new RNG.

Java

On the other hand, in Java the commonly used RNG resides in the Random class, which uppon initialized with a seed or the system time, returns pseudo-aleatory values of different primitive types. For example, you may invoke the method nextDouble() to get a value from 0.0D to 1.0D, which you may then scale to any range you need.

You may also use the rand() method of the "Math" utility class; however it is recommended to have your seedable RNG as a method in your own utility class so that the implementation of it may be changed without pain.

Most RL projects encapsulate or wrap the RNG functionality to allow exchangability of algorithms

RNG algorithms

Several RNG algorithms have been devised ; a common one is the Mersenne twister, a recent, fast and algorithm of high quality. See [1] for more info about it.

Personal tools