Jump to content

  • Log In with Google      Sign In   
  • Create Account

We need your help!

We need 1 more developer from Canada and 12 more from Australia to help us complete a research survey.

Support our site by taking a quick sponsored survey and win a chance at a $50 Amazon gift card. Click here to get started!


Seeding a pseudo-randomly generated game map


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
8 replies to this topic

#1 Paulus_newbieus   Members   -  Reputation: 131

Like
0Likes
Like

Posted 24 October 2011 - 11:03 AM

Hi, I am looking to build a pseudo-randomly generated game level/map.
A map is divided into blocks of areas, and using a seed I want to be able to regenerate the same content of any of these areas anywhere in my game map.
So if I teleport to a far-off area, it will look the same as the next time I visit the same area after restarting the game.

I know lots of games already use this mechanic, but my issue is with the fact that to seed a pseudo-random number generator you typically supply a single value such as an unsigned integer.
What I have instead is an x,y grid coordinate, not a single value, because that is the only way I can think of how I would identify a map area, especially if the map is potentially infinite in size.
For example, the first area may be 1,1. To the right is 2,1, and below is 1,2 etc.

So I guess what I am asking is how can I use a coordinate as a seed?

Sponsor:

#2 Waterlimon   Crossbones+   -  Reputation: 3662

Like
1Likes
Like

Posted 24 October 2011 - 11:09 AM

Int=(int)short << 16 & short2

???

o3o


#3 Álvaro   Crossbones+   -  Reputation: 16572

Like
0Likes
Like

Posted 24 October 2011 - 11:25 AM

srand(x * 10366439865051156459ul + y);


#4 Paulus_newbieus   Members   -  Reputation: 131

Like
1Likes
Like

Posted 24 October 2011 - 02:35 PM

Thanks for suggestions guys.

Int=(int)short << 16 & short2

???


So short is the x coord and short2 is the y. You are bit shifting the x by 16 and adding it to the y, to make it a unique single value? This is so the point {1;2} will not result in the same seed as {2;1}, am I right?

And alvaro, you are doing something similar.





#5 Álvaro   Crossbones+   -  Reputation: 16572

Like
1Likes
Like

Posted 24 October 2011 - 10:50 PM

Thanks for suggestions guys.


Int=(int)short << 16 & short2

???


So short is the x coord and short2 is the y. You are bit shifting the x by 16 and adding it to the y, to make it a unique single value? This is so the point {1;2} will not result in the same seed as {2;1}, am I right?

And alvaro, you are doing something similar.


I am doing something similar, but my code works. What Waterlimon posted has several issues. He probably meant to say `(short1 << 16) + short2' or `(short1 << 16) | short2'. With '&' you'll get 0. And you can't use `short' as a variable name.

#6 Paulus_newbieus   Members   -  Reputation: 131

Like
0Likes
Like

Posted 25 October 2011 - 05:50 AM


Thanks for suggestions guys.


Int=(int)short << 16 & short2

???


So short is the x coord and short2 is the y. You are bit shifting the x by 16 and adding it to the y, to make it a unique single value? This is so the point {1;2} will not result in the same seed as {2;1}, am I right?

And alvaro, you are doing something similar.


I am doing something similar, but my code works. What Waterlimon posted has several issues. He probably meant to say `(short1 << 16) + short2' or `(short1 << 16) | short2'. With '&' you'll get 0. And you can't use `short' as a variable name.


Thanks for clarification and taking the time to help me out alvaro!

I actually come from a VB .Net programming background (*hangs head in shame*) so could you please clarify with the symbols what's going on with the bit shift and addition i.e. should it be adding the results?
Also, alvaro what's the 10366439865051156459ul signify, and how would that be better than a bit shift?

Many thanks!

#7 JTippetts   Moderators   -  Reputation: 10338

Like
1Likes
Like

Posted 25 October 2011 - 07:24 AM

The big, ugly constant alvaro uses makes the algorithm a form of LCG. When folding coordinates together (hashing), you can get patterns that develop in the hashes of adjacent coordinates, and these patterns can conceivably make patterns in the generated level depending on how you use the hashes. By multiplying by a large LCG prime, you can mitigate the patterns somewhat and make the output more random-ish.

The bit manipulation that was posted includes a shift-left (tantamount to multiplying by 2^n) then an OR operator.

Another hint for you might be to generate a single random number (from the standard library generator or some other generator) to represent the "World Seed", and fold this number in when hashing the coordinates. This way, you can generate multiple random worlds by changing the world seed. Otherwise, you will always only get just one world.

I use a FNV hash, but mostly because I use it to generate Perlin noise and so I really don't like to have obvious patterns in the outputs.

#8 Álvaro   Crossbones+   -  Reputation: 16572

Like
1Likes
Like

Posted 25 October 2011 - 07:28 AM

You should try to find some material on bit manipulations in C or C++ somewhere else, for a more complete understanding.

Let's analyze the expression ((x << 16) + y).

(x << 16) means "take the value of x and shift it 16 bits to the left", or equivalently "multiply x by 65,536". This means that (1, 65536) and (2, 0) map to the same number. I don't know if this is acceptable to you, but my guess is that it's fine. The magic constant I used is simply a random odd 64-bit number. You should use a random odd 32-bit number if you are using 32-bit arithmetic. The advantage of using a large random number instead of 65,536 here is that you can generalize the procedure to hash more information into the seed like this:
unsigned long seed = x;
 seed = seed * 10366439865051156459ul + y;
 seed = seed * 10366439865051156459ul + z;
 seed = seed * 10366439865051156459ul + w;
 // ...


If you were to do that by shifting alone, the information about x would eventually get lost in overflow.

There are situations where you need to hash information down to a single number and you need the result to look much more random (e.g., cryptographically signing a document), but I don't think you have to go crazy for your particular application.

#9 Paulus_newbieus   Members   -  Reputation: 131

Like
0Likes
Like

Posted 26 October 2011 - 03:51 AM

You should try to find some material on bit manipulations in C or C++ somewhere else, for a more complete understanding.

Let's analyze the expression ((x << 16) + y).

(x << 16) means "take the value of x and shift it 16 bits to the left", or equivalently "multiply x by 65,536". This means that (1, 65536) and (2, 0) map to the same number. I don't know if this is acceptable to you, but my guess is that it's fine. The magic constant I used is simply a random odd 64-bit number. You should use a random odd 32-bit number if you are using 32-bit arithmetic. The advantage of using a large random number instead of 65,536 here is that you can generalize the procedure to hash more information into the seed like this:

unsigned long seed = x;
 seed = seed * 10366439865051156459ul + y;
 seed = seed * 10366439865051156459ul + z;
 seed = seed * 10366439865051156459ul + w;
 // ...


If you were to do that by shifting alone, the information about x would eventually get lost in overflow.

There are situations where you need to hash information down to a single number and you need the result to look much more random (e.g., cryptographically signing a document), but I don't think you have to go crazy for your particular application.


Thanks, much appreciated guys.










Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS