C# roguelike, devlog 9: Pseudorandom number generation (LFSR)

1. Introduction
2. Implementation
3. Conclusion

Introduction

So far I’ve used the built-in Random class for generation of random numbers and booleans. However, at this stage in the project, before moving on to procedural landscape generation, it might be a good time to write a random number generator. This will allow for finer control of the procedural process, from start to finish, and the use of custom seeds will ensure deterministic results in the generation of terrain. Additionally the creation of a simple number generator could prove an interesting and fun excercise.

A fairly simple and easy way to generate pseudorandom numbers is by using linear-feedback shift registers (LFSR). An LFSR takes a seed value and checks some of the bits, these are called “taps”, often with a logical exclusive OR operation, and generates a new bit from the result. The seed value is then bitshifted one step left or right and the newly generated bit is inserted on the opposite end. The resulting bit is the pseudorandom value used for boolean or number generation. This procedure can be repeated a certain number of times before the seed returns to the initial value and the sequence of generated bits starts repeating.

With this method a seemingly random boolean value can be generated by shifting a seed value once and checking the resulting bit. And numbers can be generated by shifting multiple times, once for each bit in the resulting number (generation of a 16-bit number requires 16 shifts, a 32-bit number requires 32 shifts and a 64-bit number requires 64 shifts), and combining the generated bits from each shift into a new, seemingly random number.

Using a seed value with more bits increase the length of the LFSR. The length meaning the length of the sequence of bits generated before the cycle repeats. Additionally careful selection of the most optimal taps is also crucial in order to achive the maximal LFSR length. Thankfully there are tables available to assist in the selection of taps, and for this implementation I’ve referenced the table of taps from the LFSR article by Peter Alfke (linked below). An LFSR with optimal taps will generate a sequence of bits with a length that corresponds to the number of possible combinations for the bit-size of the seed value used. Meaning an LFSR with a 16-bit ushort seed can generate a pattern of 65,535 “random” bits before the pattern repeats. A 32-bit uint seed can generate a pattern of 4,294,967,295 values before the pattern repeats. And a 64-bit ulong seeded LFSR with optimal taps has a maximal length of 18,446,744,073,709,551,615.

One very important thing to note is that a seed value should never be set to zero, since any shift and XOR operation of the taps will result in zero, resulting in a never-ending sequence of zero values. I haven’t done it in my simple LFSR implementation here, but forcing a 0 value seed to 1 could optionally be added to the Shift16(), Shift32() and Shift64() methods of the Lfsr class.

For a more detailed explaination please see the following links:

• Maxfield, M. Linear Feedback Shift Registers
• Alfke, P. Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators.
• Computerphile. Random Numbers with LFSR

Implementation

The Lfsr class contains the following methods:

• Shift16() Receive a 16-bit unsigned integer seed value. Check the result of a XOR bitwise operation on the taps at bit 3, 12, 14 and 15. Bitshift the seed one step to the left. Insert the result of the XOR operation as the rightmost bit.
• Shift32() Receive a 32-bit unsigned integer seed value. Check the result of a XOR bitwise operation on the taps at bit 0, 1, 21 and 31. Bitshift the seed one step to the left. Insert the result of the XOR operation as the rightmost bit.
• Shift64() Receive a 64-bit unsigned integer seed value. Check the result of a XOR bitwise operation on the taps at bit 59, 60, 62 and 63. Bitshift the seed one step to the left. Insert the result of the XOR operation as the rightmost bit.
• Check16() Receive a 16-bit unsigned integer seed value. Run the Shift16() method and return the rightmost bit as a boolean value.
• Check32() Receive a 32-bit unsigned integer seed value. Run the Shift16() method and return the rightmost bit as a boolean value.
• Check64() Receive a 64-bit unsigned integer seed value. Run the Shift16() method and return the rightmost bit as a boolean value.
• Make16() Receive a 16-bit unsigned integer seed value. Run the Shift16() method 16 times in a loop and return a 16-bit unsigned integer value made by combining the rightmost bit from each iteration into a new value.
• Make32() Receive a 32-bit unsigned integer seed value. Run the Shift32() method 32 times in a loop and return a 32-bit unsigned integer value made by combining the rightmost bit from each iteration into a new value.
• Make64() Receive a 64-bit unsigned integer seed value. Run the Shift64() method 64 times in a loop and return a 64-bit unsigned integer value made by combining the rightmost bit from each iteration into a new value.
• MakeShort() Receive a 16-bit unsigned integer seed value. Run the Make16() method and return the resulting 16-bit unsigned integer cast as a 16-bit signed integer. Optionally force the result to be a positive value by setting the sign bit to zero if the negative parameter is set to false.
• MakeInt() Receive a 32-bit unsigned integer seed value. Run the Make32() method and return the resulting 32-bit unsigned integer cast as a 32-bit signed integer. Optionally force the result to be a positive value by setting the sign bit to zero if the negative parameter is set to false.
• MakeLong() Receive a 64-bit unsigned integer seed value. Run the Make64() method and return the resulting 64-bit unsigned integer cast as a 64-bit signed integer. Optionally force the result to be a positive value by setting the sign bit to zero if the negative parameter is set to false.

/// <summary>
/// Generate pseudo random numbers using Linear-Feedback Shift Register (LFSR).
/// </summary>
public static class Lfsr
{
    // Shift 16-bit seed, using taps: 15,14,12,3 (zero-indexed)
    public static void Shift16(ref ushort seed)
    {
        bool result = ((
        ((seed >> 15) & 0B_00000000_00000001) ^
        ((seed >> 14) & 0B_00000000_00000001) ^
        ((seed >> 12) & 0B_00000000_00000001) ^
        ((seed >> 3)  & 0B_00000000_00000001)
        ) == 0B_00000000_00000001);
        seed <<= 1;
        if (result) { seed |= 0B_00000000_00000001; }
    }

    // Shift 32-bit seed, using taps: 31,21,1,0 (zero-indexed)
    public static void Shift32(ref uint seed)
    {
        bool result = ((
        ((seed >> 31) & 0B_00000000_00000000_00000000_00000001) ^
        ((seed >> 21) & 0B_00000000_00000000_00000000_00000001) ^
        ((seed >> 1)  & 0B_00000000_00000000_00000000_00000001) ^
        ((seed >> 0)  & 0B_00000000_00000000_00000000_00000001)
        ) == 0B_00000000_00000000_00000000_00000001);
        seed <<= 1;
        if (result) { seed |= 0B_00000000_00000000_00000000_00000001; }
    }
    
    // Shift 64-bit seed, using taps: 63,62,60,59 (zero-indexed)
    public static void Shift64(ref ulong seed)
    {
        bool result = ((
        ((seed >> 63) & 0B_00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001) ^
        ((seed >> 62) & 0B_00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001) ^
        ((seed >> 60) & 0B_00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001) ^
        ((seed >> 59) & 0B_00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001)
        ) == 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001);
        seed <<= 1;
        if (result) { seed |= 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001; }
    }
    
    // Generate bool from 16-bit seed
    public static bool Check16(ref ushort seed)
    {
        Shift16(ref seed);
        if ((seed & 0B_00000000_00000001) == 0B_00000000_00000001) { return true; }
        return false;
    }

    // Generate bool from 32-bit seed
    public static bool Check32(ref uint seed)
    {
        Shift32(ref seed);
        if ((seed & 0B_00000000_00000000_00000000_00000001) == 0B_00000000_00000000_00000000_00000001) { return true; }
        return false;
    }
    
    // Generate bool from 64-bit seed
    public static bool Check64(ref ulong seed)
    {
        Shift64(ref seed);
        if ((seed & 0B_00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001) == 0B_00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001) { return true; }
        return false;
    }

    // Generate unsigned 16-bit integer from 16-bit seed
    public static ushort Make16(ref ushort seed)
    {
        ushort result = 0B_00000000_00000000;
        ushort mask   = 0B_00000000_00000001;
        for (int i = 0; i < 16; i++)
        {
            Shift16(ref seed);
            if ((seed & 0B_00000000_00000001) == 0B_00000000_00000001) { result |= mask; }
            mask <<= 1;
        }
        return result;
    }

    // Generate unsigned 32-bit integer from 32-bit seed
    public static uint Make32(ref uint seed)
    {
        uint result = 0B_00000000_00000000_00000000_00000000;
        uint mask   = 0B_00000000_00000000_00000000_00000001;
        for (int i = 0; i < 32; i++)
        {
            Shift32(ref seed);
            if ((seed & 0B_00000000_00000000_00000000_00000001) == 0B_00000000_00000000_00000000_00000001) { result |= mask; }
            mask <<= 1;
        }
        return result;
    }
    
    // Generate unsigned 64-bit integer from 64-bit seed
    public static ulong Make64(ref ulong seed)
    {
        ulong result = 0B_00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000000;
        ulong mask   = 0B_00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001;
        for (int i = 0; i < 64; i++)
        {
            Shift64(ref seed);
            if ((seed & 0B_00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001) == 0B_00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001) { result |= mask; }
            mask <<= 1;
        }
        return result;
    }

    // Generate signed 16-bit integer from 16-bit seed
    public static short MakeShort(ref ushort seed, bool negative = false)
    {
        if (negative) { return (short)Make16(ref seed); }
        return (short)(Make16(ref seed) & 0B_01111111_11111111);
    }
    
    // Generate signed 32-bit integer from 32-bit seed
    public static int MakeInt(ref uint seed, bool negative = false)
    {
        if (negative) { return (int)Make32(ref seed); }
        return (int)(Make32(ref seed) & 0B_01111111_11111111_11111111_11111111);
    }
    
    // Generate signed 64-bit integer from 64-bit seed
    public static long MakeLong(ref ulong seed, bool negative = false)
    {
        if (negative) { return (long)Make64(ref seed); }
        return (long)(Make64(ref seed) & 0B_01111111_11111111_11111111_11111111_11111111_11111111_11111111_11111111);
    }
}

Conclusion

Here is a simple example of running the generator (with a slightly modified Lfsr.cs to print debug messages) using a 32-bit seed to generate three random booleans and a random number:

Download the demo source code: roguelike-devlog9_demo.zip

Find the full roguelike project on GitHub: lzzrhx/roguelike