Algorithm Needed: Predictable Randomized Tiles in Javascript

Question

Here is the function definition:

/**
 * @param {number} x The x-coordinate (can be positive or negative)
 * @param {number} y The y-coordinate (can be positive or negative)
 * @param {number} tileCount The number of available tiles
 * @return {number} The selected tile index
 */
 function getRandomTileIndex(x, y, tileCount) {
    // Fill in code here
 }

I could, for example, return x * y % tileCount but I want to introduce randomness. I could do return Math.round(Math.random() * (tileCount-1)) but then that would return different tile indices every time.

I want this function to be deterministic, so when using the same input (x, y, tileCount) the same output will always occur. But I also want it to appear (as much as possible) to be random with an even distribution - the quality of the randomness does not have to be perfect.

The purpose for this random tile generator is for a game with a (nearly) infinite grid - user starts in the middle (x,y) = (0,0) and will move outwards in whatever direction he wants - I will only have a fixed number of background tiles for the "ground" - and I want it so that every time you load the game the world looks the same.

check out this post: http://stackoverflow.com/questions/424292/how-to-create-my-own-javascript-random-number-generator-that-i-can-also-set-the — Sam, May 17 '13 at 20:32
Thanks Sam for that useful link - I think seedrandom is exactly what i needed. — codefactor, May 17 '13 at 21:08

score 2 · Accepted Answer · edited May 23 '17 at 10:25

2

If you want to introduce "predictable randomness" then sounds like you want a hash. Predictable randomness is an oxymoron as true randomness cannot be predictable, so we'll call it unknown but deterministic.

The algorithm looks like this:

use an algorithm (SHA-256, md5, etc) to hash some unique value for a given location (x*Y) sounds good to me (however this would introduce some symmetry -- (1,1) maps to the same as (-1 -1)
Use some attribute of the return value to return a tileCount number
- maybe sum(bits of hash) % tileCount

To address the symmetry issue, you could add a large number to x and y so that the symmetry happens on an almost impossibly distant location. so:

hashVal = hash((x+53562345)*(y-235734093))
tileType = sum(hashVal bits) % tileCount

or you can use sum(hash(x)+hash(y)) that would eliminate the symmetry, but too many hash algorithms can get slow and clunky.

edited May 23 '17 at 10:25

Community

1
1

answered May 17 '13 at 20:37

ajon

7,868
11
48
86

1

»Predictable randomness« could also refer to a PRNG. – Joey May 17 '13 at 20:42
@ajon I agree about the oxymoron. This is a good idea - I wonder though about the way to generate a unique number given x,y ... having symmetry `getRandomTileIndex(-1,-1,100) == getRandomTileIndex(1,1,100)` would be devastating to the effect I was trying to create. – codefactor May 17 '13 at 20:44
@Joey, yes, I was just referring to the fact that this phrase doesn't work linguistically. Granted in the industry prng are referred to as predictably random. – ajon May 17 '13 at 20:44
@codefactor See my addition to address the symmetry. – ajon May 17 '13 at 20:50
1

@ajon What do you think would happen with `hashVal = hash(x*53562345+y)` ? – codefactor May 17 '13 at 20:53
That sounds like a great alternative. good idea. – ajon May 17 '13 at 20:54
I think maybe instead I will use the answer from http://stackoverflow.com/questions/424292/how-to-create-my-own-javascript-random-number-generator-that-i-can-also-set-the using the x,y,tileCount as the seem to the random generator and then using `Math.random()` instead. – codefactor May 17 '13 at 21:07
Summing two hashes would introduce a huge bias (for the same reason that 7 gets rolled more often than snake-eyes) – BlueRaja - Danny Pflughoeft May 17 '13 at 21:46
@BlueRaja-DannyPflughoeft I had in my mind a small number of unique tiles maybe ~ 20, which would really minimize the bias, but your point is a great one. I also hadn't looked at how few bits a lot of the hash algorithms are. – ajon May 17 '13 at 22:46

score 0 · Answer 2 · answered May 17 '13 at 20:44

0

I would suggest you using a function that creates the tiles dynamicaly and than saves them in an object. So every time the function is called it will return the value from the created object. For saving the object you could also use the HTML5 Local Storage for persistance if you want to create a HTML5 game.

A proposal would be:

/**
 * @param {number} x The x-coordinate (can be positive or negative)
 * @param {number} y The y-coordinate (can be positive or negative)
 * @param {number} tileCount The number of available tiles
 * @return {number} The selected tile index
 */
 var tiles = {};
 function getRandomTileIndex(x, y, tileCount) {
    var tile;
    if(tiles[x][y]) {
        tile = tiles[x][y];
    }
    else {
        tile = Math.round(Math.random() * (tileCount));
        tiles[x][y] = tile;
    }
    return tile;
 }

answered May 17 '13 at 20:44

Thomas Kosiewski

144
3
9

This is a good attempt - but like i said the world is (nearly) infinite - and I want it to be deterministic, so everyone sees the same world (regardless of which system, or if they have cleared cache, opened different browser, etc) – codefactor May 17 '13 at 20:48
One other note: Users will be building stuff in the world, which other people will see, and likely they will build stuff according to what background they see - so it is important that everyone sees the same thing. – codefactor May 17 '13 at 20:49
@codefactor So you want to create one big map, that will dynamically expend ? – Thomas Kosiewski May 17 '13 at 20:50
Well I have a grid centered at (0,0) and when you move outwards I shift the grid to the left/right/up/down depending on direction. Stuff people build will have relative coordinates from the center - and I want to paint the background with these random tiles - but i want it to always be the same. – codefactor May 17 '13 at 20:57

Algorithm Needed: Predictable Randomized Tiles in Javascript

2 Answers2