• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Lode

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

-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! smile.png

Edited by Lode
0

Share this post


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


Link to post
Share on other sites
There are a few fast operations you can do on an `unsigned' value that are permutations of Z/(2^32):
- add a constant
- 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 this post


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


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


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


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


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


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

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!

0

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?
0

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

0

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  
Followers 0