How to generate random numbers without making new Random objects?

Question

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

Answer 1

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:

For comparison, the Random algorithm creates this pattern:

And Sign's algorithm too has patterns:

Answer 2

Why not just combine the two numbers and hash them? something like

private const int seed;

public MapCell GetMapCell(int x, int y)
{
    int combined = seed + (x ^ y);
    return new MapCell(combined.GetHashCode() %5);
}

You want to simply map each X,Y coordinate to a MapCell.

Answer 3

In The Art of Computer programming, volume 2 there is a section dedicated to random numbers. You might be able to find what you are looking for in there.

---

Project Euler uses the following psuedo random number generator in a few of its problems (252 and 375 are the ones I spotted first):

  S(0)   = 290797 
  S(n+1) = (S(n))^2 mod 50515093

Obviously, this doesn't give you a walk up to maxint, but it gives an approach to your own that only requires you save the last result. If you are working with longs instead of ints, it would let work (for what its worth, 2^32-5 = 0xFFFFFFFB = 4,294,967,291 is the largest 32 bit prime).

---

In the talk rand() Considered Harmful the presenter goes over a number of different options for doing random numbers. While that talks of C++, it does give information that can be used to find a the right method in other languages.

In particular, for well known uniform random number distributions the thing you want to find is mt19937 which stands for the Mersenne twister with very particular parameters - its based on 2¹⁹⁹³⁷ - 1. (~11m into the talk).

The key with the Mersenne twister is that it is very high quality pseudo-random numbers. If you poke around a bit, you can find implementations of it in a number of languages. The original C source

Specfically, for C# you can use Jon Skeet's StaticRandom to get random numbers in a thread safe way - no instantiation of new objects needed (code). A modification of the code should allow you to pass in a seed.

Answer 4

As commented by Kyralessa, the Random class should be created and the sequence requested from the one instance. This saves the time of creating a new class instance.

//fixed seed of 123
private Random ran = new Random(123);
public MapCell GetMapCell(int x, int y)
{
    //x and y should not be zero
    int r = ran.Next(0,x*y*4)%4;
    return new MapCell(r);
}