Sign in to follow this  
KristofferDorph

Seemingly random number based on coordinates

Recommended Posts

Hi gamedevs!

I'm making a little game, where I need an almost infinite world. The game is 2d, and to make it less memory consuming I want the entire map to be generated based on a seed.
The same way minecraft is randomly generated based on a seed.

So in short, what I need is a number based on each x and y coordinate that seems random, but is the same everytime the map is loaded.

For instance, x = 3, y = 5 gives 42 and (63,15) gives 23

Right now i use this equation: Math.round(((y) * (x+1) + (y/20) + (x/32)) % 20) (javascript)
But it repeats every 32 block or something like that.

Anybody who can come up with a fix ? :-)

Regards
Kristoffer

Share this post


Link to post
Share on other sites
zacaj    667
[url="http://stackoverflow.com/questions/6469969/pseudo-random-number-generator-from-two-inputs"]http://stackoverflow.com/questions/6469969/pseudo-random-number-generator-from-two-inputs[/url] maybe?
Youre looking for a pseudo random number generator with two inputs and one output. The problem with the repetition every 32 blocks can be solved my using large prime numbers, and then limiting the outputted number, either with %RANGE or &RANGE (only if range is all 1's in binary)

Share this post


Link to post
Share on other sites
alvaro    21246
What you want to do is compute a hash of x and y. A simple one:

[code]long hash(long x, long y) {
long result = x;
result *= MAGIC_CONSTANT_1|1;
result += MAGIC_CONSTANT_2;
result = (result>>32) + (result<<32);
result ^= MAGIC_CONSTANT_3;
result += y;
result *= MAGIC_CONSTANT_4|1;
result += MAGIC_CONSTANT_5;
result = (result>>32) + (result<<32);
result ^= MAGIC_CONSTANT_6;
result *= MAGIC_CONSTANT_7|1;

return result;
}[/code]

Plug in values for all the magic constant that are basically random 64-bit integers and you'll get some really random-looking output.

Share this post


Link to post
Share on other sites
NormanCao    100
Just use [url="http://en.wikipedia.org/wiki/Perlin_noise"]Perlin Noise[/url], or any number of different noise generators which take an initial seed, then an x and y value to generate the value of the noise at that point.

Share this post


Link to post
Share on other sites
alvaro    21246
Can you post exactly what you did? I see how Perlin noise and your situation both can benefit from a hash function, but I don't know how you would apply Perlin noise directly to your situation.

Share this post


Link to post
Share on other sites
NormanCao    100
You initialize Perlin Noise with a certain seed. Perlin Noise is a function that will return the same value given the same input values for x and y (it can also be extended to z and t). There's no need to hash anything.

Share this post


Link to post
Share on other sites
JTippetts    12950
Most Perlin noise implementations [i]do[/i] hash the coordinates first, then perform a gradient table lookup with the hash (for gradient noise, at least) and calculate a dot-product, then interpolate those to obtain a final value. For instance, see the reference implementation: [url="http://mrl.nyu.edu/~perlin/noise/"]http://mrl.nyu.edu/~perlin/noise/[/url]
The implementation folds (hashes) the coordinates using a permutation table. The thing is, though, that for 2D Perlin noise, the function is going to hash 4 sets of coordinates, then perform an interpolation between them to generate the tween values. Even if your inputs fall on integer boundaries, the interpolation is still performed, even if the interpolators are 0. So you're doing 4 hashes, possibly 4 gradient lookups + dot products, and 3 interpolations. That's of course, for the 2D case. 3D of course increases exponentially. (8 hashes, 8 gradient lookups, 8 dotproducts, and 7 interpolations)

I don't really see this as being superior to just doing the hashes yourself, especially if performance is key (as is so often the case in this kind of thing). In fact, it seems like you are adding completely unnecessary processing for absolutely no benefit. If nothing else, just strip the hashing out of the reference implementation and perform it yourself, and skip all the rest of it.

Share this post


Link to post
Share on other sites
[quote name='alvaro' timestamp='1311126623' post='4837743']
Can you post exactly what you did? I see how Perlin noise and your situation both can benefit from a hash function, but I don't know how you would apply Perlin noise directly to your situation.
[/quote]

I used a 2d Simplex Perlin noise, that is a modified version of the original:

What I use is a javascript port of: [color="#999988"][url="http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf"]http://staffwww.itn....implexnoise.pdf[/url][/color]

Wich works somewhat faster than the classic method, and for now, in a grid of (150,150) I can't really see any change in performance in comparison to just making a normal random number between -1 and 1 :-)

/Kristoffer

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this