Jump to content
  • Advertisement
Sign in to follow this  
Paulus_newbieus

Seeding a pseudo-randomly generated game map

This topic is 2608 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

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?

Share this post


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



Share this post


Link to post
Share on other sites

Thanks for suggestions guys.
[quote name='Waterlimon' timestamp='1319476188' post='4876360']
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.
[/quote]

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.

Share this post


Link to post
Share on other sites

[quote name='Paulus_newbieus' timestamp='1319488546' post='4876462']
Thanks for suggestions guys.
[quote name='Waterlimon' timestamp='1319476188' post='4876360']
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.
[/quote]

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.
[/quote]

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 [color="#006666"][font="CourierNew, monospace"]10366439865051156459ul [/font]signify, and how would that be better than a bit shift?

Many thanks!

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites

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.





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!