Jump to content
  • Advertisement
Sign in to follow this  
Lode

good random permutation?

This topic is 1595 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
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;

Share this post


Link to post
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!

Share this post


Link to post
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?

Share this post


Link to post
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 :)

 

hnJbTyN.png

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!