2
\$\begingroup\$

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?

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

2 Answers 2

3
\$\begingroup\$

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

(:

\$\endgroup\$
2
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – user41442
    Apr 4, 2015 at 21:52
  • \$\begingroup\$ 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). \$\endgroup\$
    – Alan Wolfe
    May 6, 2015 at 5:12
0
\$\begingroup\$

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();
}
\$\endgroup\$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .