6

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

17
  • "which is surprisingly slow" How slow? IMO this is only possible way, unless you want to save the whole world.
    – Euphoric
    Aug 17, 2012 at 16:45
  • Also, how do you want to handle changes in generation algorithm itself?
    – Euphoric
    Aug 17, 2012 at 16:50
  • Just generating a lot of objects that way (say, when you're scrolling quite quickly around the map) seems to cause trouble. I'm not sure what you mean by changes in generation algorithm. I think what's to be done is to find a numerical "random number generator" (repeatable, deterministic, mathematical process) which turns two numbers into an apparently unrelated third number and runs quickly. Aug 17, 2012 at 16:51
  • 8
    I feel like you're not understanding how Random works. It's intended to give you a sequence of random numbers. You don't need to create a bunch of different Random instances. You just need one with a given seed, which will return you the same sequence of random numbers every time. Random is not like the RND() back in BASIC days that would give you one random number. Your application only needs one instance of the Random class from which to generate all of its random numbers.
    – Kyralessa
    Aug 17, 2012 at 17:37
  • 2
    I have a feeling what you're looking for is some sort of noisy function, where the seed is the 'setup', and x and y are the inputs. Aug 17, 2012 at 18:06

4 Answers 4

4

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

3

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.

4
  • Depending on the nature of the GetHashCode() function that might work really well. Looking at it now. Aug 17, 2012 at 18:56
  • One would assume that the simplest implementation of a hashcode on an integer object would be to return the integer itself? I'm not sure how 'noisy' this would be (the distribution), but I think this is the direction the OP is looking. Aug 17, 2012 at 19:49
  • Turns out that is the hashcode (or something quite a bit like it). Not very noisy, but this is spiritually the right approach. Aug 17, 2012 at 19:53
  • It is as noisy as you want. His example just relies on C#'s int hash code, which isn't very randomized (its built for speed). There are very simple hash algorithms based on integers which will provide the noise you are looking for. The only reason to use Random() is because it will generate more statistically random behavior over long periods. From your question, the quality of the randomness is not a high priority, so a hash is an easy solution.
    – Cort Ammon
    Dec 6, 2014 at 15:54
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 219937 - 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.

1
  • 1
    +1 for what looks like Blum Blum Shub up top from TAOCP and the Mersenne Twister reference for more accurate stuff. I just implemented Blum Blum Shub in JS for this exact sort of scenario where I needed reproducible pseudo-randomness and it works pretty good.
    – J Trana
    Feb 13, 2014 at 3:02
-1

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);
}
2
  • This is a very old question to be answering, but no, this won't work; the most important requirement is to be deterministic. If I call getMapCell(3, 2) several times, it needs to return the same thing each time. This code won't achieve that. It also has lots of other issues (e.g. if x=0 then it always returns 0, making lots of horizontal lines, and so on) Nov 1, 2016 at 19:55
  • I had presumed that this was wrapped in a class that basically reset Random each time to the same seed and you were iterating through a range of x and y once. If you want to call getMapCell() several times with the same (x, y), I would suggest you accept Euphoric's answer.
    – Valid
    Nov 11, 2016 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.