**1**

# Seeding a pseudo-randomly generated game map

###
#1
Members - Reputation: **131**

Posted 24 October 2011 - 11:03 AM

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?

###
#4
Members - Reputation: **131**

Posted 24 October 2011 - 02:35 PM

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
Crossbones+ - Reputation: **14879**

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
Members - Reputation: **131**

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
Moderators - Reputation: **9308**

Posted 25 October 2011 - 07:24 AM

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
Crossbones+ - Reputation: **14879**

Posted 25 October 2011 - 07:28 AM

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
Members - Reputation: **131**

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.