current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 2 down vote favorite

I've been trying to find an algorithm that will take in an x value, a y value, and a seed value and then spit out a number between 0 and 255 (or an int that I can cut up into bytes). I want to be able to feed in the tile a player is standing on during some ingame event and get the same value for the same tile any time the player is in that level. I don't want to use a linear PRNG because I just want to check a few tiles at any one time, not go though several of them to get a sequence.

I tried modifying an Xor Shift PRNG, but I just end up making patterns like below:

pattern

ubyte Xor( int wx, int wy, ulong seed ){
    int result = wx ^ (wx >> 7) ^ wy ^ (wy >> 9) ^ seed ^ (seed << 6);
    return cast(ubyte)result;
}

My input values are likely to be 0-32000 for x and y, and seed can be any ulong value. I'd like to avoid floating point math as it's not deterministic between machines (so it would screw up some multiplayer stuff). I just need to not get a repeating pattern, and have each seed produce a distinctly different output. Can anyone point me in the right direction?

share|improve this question
    
Basically, you want a hash value, is that it? –  Alexandre Vaillancourt Mar 17 at 18:08
    
Maybe this question belongs more to math.stackexchange.com... –  Alexandre Vaillancourt Mar 17 at 18:09
    
Could you use 2D Perlin or Simplex noise? –  fastinvsqrt Mar 24 at 14:20
    
@AlexandreVaillancourt I don't think math stackexchange is the right platform for this. This is obviously a programming problem. –  Philipp May 4 at 11:20

2 Answers 2

up vote 3 down vote accepted

What you are looking for is a hash algorithm. You'd concatenate your 16 bit x and y position into a 32 bit number and then hash that to get what is effectively a pseudo random number out. The size of the hash output depends on what algorithm you use, but you could easily just use the lowest 8 bits of whatever the output is to get your 0-255 value. It will have the properties that you want: neighboring tiles will usually have very different values, but the same tile will always give you the same result. For use in a game scenario I would recommend murmurhash. Its not quite cryptographic quality, which is fine for your usage case, and is very fast while giving very nice pseudo random distribution (avalanche effect).

Murmurhash3 source code can be found here: https://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp

(:

share|improve this answer
2  
Take a look at gist.github.com/badboy/6267743#64-bit-to-32-bit-hash-functions, which will specifically turn a 64 bit value (i.e. 16bit x + 16bit y + 32bit seed) into a 32bit hash value very fast (tens of machine instructions) and with minimal artifacts. –  user41442 Apr 4 at 21:52
    
Great point about getting a seed in there BTW. With a seed you can make it different each run despite it doing what the op wanted (or however else you want to use the seed). –  Alan Wolfe May 6 at 5:12
up vote 0 down vote

Why not a PRNG, actually? It looks like a simple and good tool to me.

Some pseudocode using srand/rand that you should be able to adapt to any other PRNG:

int shuffle(int seed, int x, int y)
{
    int tmp;
    srand(seed); tmp = rand();
    srand(tmp + x); tmp = rand();
    srand(tmp + y); tmp = rand();
    return tmp;
}

This can actually be very fast. Using one of C++’s standard PRNGs, the following function compiles to just shuffling instructions (no std library calls) and can execute 80 million times a second (5 times faster than Murmurhash).

#include <random>

int shuffle(int seed, int x, int y)
{
    std::minstd_rand r;
    r.seed(seed); r.seed(r() + x); r.seed(r() + y);
    return r();
}
share|improve this answer
    
While this will probably work, it is very slow compared to specialized hashing methods –  user41442 Apr 4 at 21:44
    
How much slower exactly? –  sam hocevar Apr 6 at 13:14
    
The function call overhead of rand/srand alone, not to mention the costs of running the function, are high. An optimized hash by contrast can run in 10-12 machine instructions. For something done for each pixel/tile, this can be significant. Further rand() usually produces terrible artifacts using the spectral test. –  user41442 Apr 6 at 19:59
1  
Dude, this is pseudocode. As I said, just use a different PRNG if you don’t like rand(). –  sam hocevar Apr 7 at 6:16
    
@user41442 - but does it need to be fast? According to the OP: "I just want to check a few tiles at any one time" - so rand() is fine for this use case. –  Darth Melkor May 4 at 11:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.