Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
    
"which is surprisingly slow" How slow? IMO this is only possible way, unless you want to save the whole world. –  Euphoric Aug 17 '12 at 16:45
    
Also, how do you want to handle changes in generation algorithm itself? –  Euphoric Aug 17 '12 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. –  Richard Rast Aug 17 '12 at 16:51
7  
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 '12 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. –  Clockwork-Muse Aug 17 '12 at 18:06

3 Answers 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.

share|improve this answer
    
Depending on the nature of the GetHashCode() function that might work really well. Looking at it now. –  Richard Rast Aug 17 '12 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. –  Clockwork-Muse Aug 17 '12 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. –  Richard Rast Aug 17 '12 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 at 15:54

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.

share|improve this answer
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 at 3:02

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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