Followers 0

# good random permutation?

## 15 posts in this topic

Hello,

I'm looking for a way to map a 31-bit positive integer (leaving some room for Java!) to another 31-bit positive integer, for purpose of random world generation, with the following properties:

-if you go through the inputs in sequence, the resulting output sequence should be a good pseudo-random sequence

-it should not require state. So a linear congruence generator or similar will not work afaik. Instead, it should be able to give you the output for any of the inputs at any time, no requirement to go through it in order.

-it should be fast, so cryptographic hashes are probably not it

-it should be stable: always give the same output for the same input (so no true random generator )

-each result is unique, that is, every possible integer is output by one input integer (not the most important requirement, but would be nice, each output value should have equal probability). So some arbitrary bit twiddling and multiplications won't do it either

I tried to implement something similar to the following one:

http://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/

but it's actually not that great, I want to use a seed value as well, and while this one works great for some seeds, it does not for many as well and to make it even more annoying, it gives too similar patterns for seeds that are near each other (so if you generate for coordinates x and y a random world temperature with seed 1000 and a random height with seed 1001, they will be too correlated. Or something like that, in any case the patterns are ugly with nearby seeds).

Does anyone have suggestions for such a function?

Thanks a lot!

Edited by Lode
0

##### Share on other sites
I don't think a stateless PRNG makes any sense. Is there not any way to store the state of a PRNG with the terrain generator?

Usually the go-to choice for alternative RNGs (if not already provided by the language's libraries) is usually mersenne twister.
0

##### Share on other sites

Sounds like you're looking for a perfect hash.

2

##### Share on other sites
There are a few fast operations you can do on an unsigned' value that are permutations of Z/(2^32):
- XOR with a constant
- multiply by an odd constant
- rotate bits (e.g. x = (x>>18) | (x<<14)')

By composing a few of these operations together I think you can make something that satisfies all of your requirements.

Since you want to do it with 31 bits instead of 32, you'll have to AND the result of each operation with 0x7fffffff to emulate 31-bit arithmetic. If you were to do it with 32 bits, it would be a bit faster.

Care to explain what you mean by "leaving some room for Java!"? Edited by Álvaro
2

##### Share on other sites

Thanks! Yeah I didn't really know the exact scientific name of what I was looking for which made googling hard. Perfect hash, and random access random permutation, sound indeed like it.

It needs to be stateless because the whole world will not be generated at once, it generates a part only when you reach it. E.g. if you reach a part with a coordinate x + 65536 * y = 5000, it needs to give you the value for 5000.

About Java: I'm not even using it but if I would the world should be the same. So, it doesn't have unsigned integers. I don't like that, at all, but it is what it is. 64-bit integers can of course store the 32-bit value, but truth is the upper value doesn't really matter a lot so going up to 2 billion seems fine.

Edited by Lode
0

##### Share on other sites

Yes, it would be much easier if you had asked for a 32-bit permutation. I think Java does let you access all 32 bits (signed integers just use a bit for the sign bit, after all) but bitwise operations are apparently rather tricky. I always say signed arithmetic is evil, but Java does not let you choose here, so it's harder than it needs to be.

0

##### Share on other sites
I don't think you should have any trouble using 32-bit arithmetic in Java. For arithmetic operations (addition and multiplication), it makes no difference whether you are interpreting your bit patterns as unsigned or signed with two's complement representation. XOR only has one possible interpretation. When shifting, just make sure to use >>> instead of >> so the sign bit isn't propagated.

Disclaimer: I am not a Java programmer.
1

##### Share on other sites

I'll throw in my minimalistic GLSL PRNG. I'm using this in my particle code, which requires very basic random inital values. I stole it from here and modified it to make use of the VAO's vertex ID to generate unique seeds for each particle. It uses two variables (fTime and iSeed) as components to calculate the initial seed when the shader is run. iSeed has to be set once (or it could be omitted), fTime is modified per-update anyway. Modifying the code to return a 32-bit integer should be trivial ;).

uniform float fTime;
uniform int iSeed;

uint seed = uint(fTime * 1000.0) + uint(gl_VertexID) + iSeed;

const float InverseMaxInt = 1.0 / 4294967295.0;

//returns a result in the range [0, 1]
float drnd()
{
seed++;

uint i=(seed^12345391u)*2654435769u;
i^=(i<<6u)^(i>>26u);
i*=2654435769u;
i+=(i<<5u)^(i>>12u);
return float(i) * InverseMaxInt;
}



EDIT: you mentioned you need to map one 32-bit int to another, in which case you can simple pass the previous value in as the seed. As for whether the result is always unique, I cannot say.

Edited by irreversible
1

##### Share on other sites

Thanks a lot!

In the end I went with a hybrid with Álvaro's suggestion and irreversible's example :)

With seed a fixed constant that determines the world, and x the input number, my first implementation was:

x ^= (seed ^ 1234567890);
x = (x + 1234567890) & 2147483647;
x = (x * 1000000001) & 2147483647;
x = (x >> 18) | (x << 14);
x = (x * 1000000005) & 2147483647;
return x;

But that had noticable patterns still so not good. But then I combined it with irreversible (the order in which things happen is based on it, the numbers not), giving this:

x ^= (seed ^ 1234567890);
x = (x * 1000000001) & 2147483647;
x = (x ^ ((x << 6) ^ (x >> 26))) & 2147483647;
x = (x * 1000000001) & 2147483647;
x = (x + ((x << 5) ^ (x >> 12))) & 2147483647;
return x;

And that seems to work quite well indeed :)

0

##### Share on other sites
You have to be a little bit more careful. The operation g(x) = (x ^ ((x << 6) ^ (x >> 26))) & 2147483647 is not injective:

g(0) = g(1431655765) = 0

So your function ends up not being a permutation. With seed = 0:

f(0) = f(297859934) = f(719478613) = f(1927211019) = 1905156899

EDIT: I didn't check carefully, but x = (x + ((x << 5) ^ (x >> 12))) & 2147483647;' is probably also problematic. Edited by Álvaro
1

##### Share on other sites
Would this be too slow for your program?
  x = (x ^ seed ^ 1234567890) & 2147483647;
x = ((x << 5) ^ (x >> 26)) & 2147483647;
x = (x + 675788137) & 2147483647;
x ^= 751504984u;
x = (x * 2020831389) & 2147483647;
x = ((x << 15) ^ (x >> 16)) & 2147483647;
x = (x + 1804049603) & 2147483647;
x ^= 1028562816u;
x = (x * 1430376653) & 2147483647;
x = ((x << 15) ^ (x >> 16)) & 2147483647;
x = (x + 1804049603) & 2147483647;
x ^= 1028562816u;
x = (x * 1430376653) & 2147483647;
return x;
`
1

##### Share on other sites

Thanks for pointing that out. That last one works nicely. But if I remove the last 4 lines (before return x), then the patterns look ugly. Seems like that additional repetition of similar things fixes it. So, works great, but I'm going to experiment to try removing some lines :)

Do you have any explanation why some of these give ugly patterns in results, while others look very random? Thanks!

0

##### Share on other sites
I duplicated the last four lines precisely because I also saw some ugly patterns. What are you doing with the output exactly, where you see the patterns?
0

##### Share on other sites

World generation:

On the left: ugly patterns of trees (the dots)

On the right: good pattern of trees with your code :)

0

## Create an account

Register a new account