Non-Repeating Pseudo Random Sequences

4.7
(29)

Pseudo-random numbers are numbers drawn which on the surface appear random. It’s not possible for a computer to actually generate “genuinely random numbers” without additional hardware, and even then their credibility of randomness is not guaranteed. For most purposes in game development, it’s rare to actually require genuine random numbers and so we rely upon the the numbers provided by libraries.

If you’re old-school enough, or just want something quick and dirty, the classic rand() function may suffice:

#include <stdlib.h>

int main()
{
    int i = rand();
    return 0;
}

it will return a random number between 0 and RAND_MAX, a constant declared in stdlib.h. If you want control over your random numbers, for example specifying the upper limit, rand is used with the modulo operator, in this case to choose a number out of the set 0,1,2,3,4,5,6,7,8,9:

#include <stdlib.h>

int main()
{
    int i = rand() % 10;
    return 0;
}

If you required a floating point random value between two values, you may use something like this:

#include <stdlib.h>

int main()
{
    float lower = 5.0f;
    float upper = 10.0f;
    float i = ((float)rand()/(float)RAND_MAX)
                   * (upper - lower) + lower;
    return 0;
}

Where the rand() section generates a number between 0 and 1, and its scaled and offset to suit the range you require. The “Modern C++” approach is considered to generate higher quality random numbers using the <random> library, but can be slower and more fiddly to use than rand():

#include <random>

int main() 
{
    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_real_distribution<float> dist(5.0, 10.0);
    float i = dist(mt);
    return 0;
}

Certainly I’d advise considering the more robust pseudo-random number generators if you are working with cryptography or similar. rand() is widely understood to be a highly flawed function for generating numbers of high quality, but as mentioned at the start, sometimes “good enough” is OK.

However, these approaches do not guarantee that the same number won’t be drawn twice. After all, why should they? If you roll a die, you may very well get several 4’s in a sequence of rolls. This is how a random number generator should work. But what if we want a random sequence that doesn’t repeat until all possible values have been presented? To do this we can rely on some bit-shifting trickery to help us out.

#include <iostream>

int main()
{
    auto next_number = [](unsigned char prev_number)
    {
        return (prev_number >> 1) | 
         (((n ^ (n >> 2) ^ (n >> 3) ^ (n >> 5)) &amp; 0x01) << 7);
    };

    unsigned char r = 0xDB;

    for(int i=0; i<256; i++)
    {
        r = next_number(r);
        std::cout << (int) r << std::endl;
    }

    return 0;
}
    

The above code starts with a register set to a non-zero value. Each time the lambda function “next_number” is called, the bits at locations 0, 2, 3, and 5 are XOR’d together and masked to give the result as a single bit. This bit is then inserted to the right hand side of the word, and the whole word is shifted to the left one bit.

This approach is called a “linear feedback shift register” (wikipedia) and is guaranteed to output all values within the range specified by the word length of the underlying type. In this case, it was an 8-bit char, so all the values 0 – 255 will be output once, but the order will be pseudo-random. The sequence can be changed by changing the starting value, or the bits that are selected out of the word. Naturally more bits will yield longer sequences.

Non repeating pseudo random number sequences are useful in procedural generation, particularly if you only want one “thing” out of a set of things to exist in a random location.

Rate this post!

Average rating 4.7 / 5. Vote count: 29

No votes so far! Be the first to rate this post.