C# Random – How to Generate Random Numbers Without New Random Objects

crandom

I'm using this as part of a game, but it's not really a game development question, so I'm putting it on this more general Stack Exchange.

The goal is to generate "random" outputs for a fixed integer input, but (and this is the clincher) to generate the same random output every time the same random input is put in.

The idea here is that the function will generate the world the same way every time, so we don't need to store anything; the function itself is the storage. Unfortunately access speed is a little slow, because the only way I can find to generate random numbers is to create a new Random() object with a seed based on the input, which is surprisingly slow.

Is there a better way? I'm not worried about crypto-safe generation; in fact I'm just going to pick a random seed in advance and expose it quite publicly.

The current code looks like this:

private const int seed;

public MapCell GetMapCell(int x, int y)
{
    Random ran = new Random(seed + (x ^ y));
    return new MapCell(ran.NextInt(0, 4));
}

Where the MapCell is one of four types (in fact it's more complicated than this, but not a whole lot). The point is that this could be called for any parameters, at any time, in no particular order, but it needs to return the same answer every time, if x and y are the same every time. That's why I can't fix a certain Random object and use it repeatedly.

I also don't want to store anything, because I want to keep the RAM usage quite low, but allow the player to wander freely to the edges of Int.MaxValue

Best Answer

Sign is on a good track, but his algorithm is wrong. It is not much random. It is actually pretty hard to create random like this. I was playing around with this and everything I tried created obvious patterns when printed in 2D. In the end I manged to create an algorithm that doesn't create any eye-visible patterns. I looked for inspiration in existing random algorithms.

public static uint bitRotate(uint x)
{
    const int bits = 16;
    return (x << bits) | (x >> (32 - bits));
}

public static uint getXYNoise(int x, int y)
{
    UInt32 num = seed;
    for (uint i = 0; i < 16; i++)
    {
        num = num * 541 + (uint)x;
        num = bitRotate(num);
        num = num * 809 + (uint)y;
        num = bitRotate(num);
        num = num * 673 + (uint)i;
        num = bitRotate(num);
    }
    return num % 4;
}

When this algorithm is used to render a 4-shades of gray image, it creates this: random noise

For comparison, the Random algorithm creates this pattern:enter image description here

And Sign's algorithm too has patterns: enter image description here

Related Topic