Explore our sites

Stack Exchange
tour help
Tell me more ×
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.
up vote 5 down vote favorite

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
4  
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
1  
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
show 9 more comments

2 Answers

up vote 2 down vote

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
add comment
up vote 1 down vote

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).

The Euler forums have someone asking for a similar request as yours (a range) and a resulting hash function that gives a sizeable range (working with 64 bit numbers). Note: this is not my code and is simply copied from the forum link.

typedef unsigned long long int uint;

uint ror(uint x, short i)
{
   return (x >> i) | (x << (64-i));
}

uint hash64(uint x)
{
uint x0=ror(x,51)^ror(x,20)+15884312619126177065LL;
uint x1=ror(x,48)^ror(x,3)+16030739109795541072LL;
uint x2=ror(x,48)^ror(x,1)+9095224626272754645LL;
uint x3=ror(x,46)^ror(x,37)+13258336774676992168LL;
uint x4=ror(x,37)^ror(x,18)+13870978993782402331LL;
uint x5=ror(x,15)^ror(x,14)+794800749471879372LL;
uint x6=ror(x,9)^ror(x,2)+17805125125192487503LL;
uint x7=ror(x,13)^ror(x,26)+3740983554860765654LL;

x0=ror(x7,43)^ror(x4,44)+8708192349004310897LL;
x1=ror(x4,22)^ror(x3,42)+86190737941271154LL;
x2=ror(x5,41)^ror(x3,7)+9877488641444698413LL;
x3=ror(x3,57)^ror(x6,6)+5793382607003543736LL;
x4=ror(x2,46)^ror(x1,12)+8689969686300368012LL;
x5=ror(x2,55)^ror(x1,5)+9077693918083023698LL;
x6=ror(x4,38)^ror(x7,19)+5501717187604728996LL;
x7=ror(x5,40)^ror(x0,28)+9036855273260389929LL;

x0=ror(x5,50)^ror(x1,23)+14916210545219058286LL;
x1=ror(x7,17)^ror(x4,13)+14121561607146121051LL;
x2=ror(x6,13)^ror(x0,40)+8957702351020845919LL;
x3=ror(x3,47)^ror(x1,63)+2413769986111943230LL;
x4=ror(x4,50)^ror(x1,13)+17942888648282466259LL;
x5=ror(x1,23)^ror(x2,36)+12293804346899439258LL;
x6=ror(x5,60)^ror(x4,28)+49390456654669589LL;
x7=ror(x7,14)^ror(x6,37)+811373459448382129LL;

x0 = x0^x1;
x2 = x2^x3;
x4 = x4^x5;
x6 = x6^x7;
x0 = x0^x2;
x4 = x4^x6;
return x0^x4;
}

This could then be masked off to give you 32 bits.

share|improve this answer
 
Hmm... - What would the effect be if the use of x inside the function were replaced by a static (unchanging) seed, and the two uses of i were replaced by two input parameters? –  Clockwork-Muse Aug 17 '12 at 18:39
 
@X-Zero The parameter i is used in ror for how many bits to rotate the other parameter. It has a range from 1 to 63 in this code. If one wanted two parameters, it would be done on the hash64 function. Howerver, as the original code is two 32 bit integers, and this is one 64 bit value, it would work just as well to concatenate the bits for a 64 bit value. Having x be static wouldn't have the intended effect at all (it isn't a seed) - this is a hash function, not a pseudo-random function. –  MichaelT Aug 20 '12 at 2:56
add comment

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.