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
Seemingly random number based on coordinates
http://stackoverflow.com/questions/6469969/pseudo-random-number-generator-from-two-inputs 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)
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)
What you want to do is compute a hash of x and y. A simple one:
Plug in values for all the magic constant that are basically random 64-bit integers and you'll get some really random-looking output.
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;
}Plug in values for all the magic constant that are basically random 64-bit integers and you'll get some really random-looking output.
Just use Perlin Noise, 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.
Author
Thanks a bunch for all the replies !
Got it working with the Perlin Noise, super smart method :-)
Got it working with the Perlin Noise, super smart method :-)
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.
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.
Most Perlin noise implementations do 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: http://mrl.nyu.edu/~perlin/noise/
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.
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.
Author
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.
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"]http://staffwww.itn....implexnoise.pdf
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
