- Home /
How to create seemingly random arrangement of tiles in a grid?
I am making a game with a huge environment where terrain tiles appear as the player gets close enough to them. It can be thought of as a grid of tiles with coordinates starting at (0, 0), and extending outwards in all directions. I will have a variety of these terrain tiles, and I need them to be placed on the map in a way that appears to not have a pattern, but it can not be random either. Manually setting the tiles is not an option because the map will be gigantic. I need a function that will take the map coordinates and output which tile to spawn.
Thanks in advance!
Answer by gfoot · Jan 16, 2014 at 11:35 PM
You need to push the tile coordinates through a hash function. You need to be careful how you combine the coordinates - one reasonable way is to hash one of the coordinates first, then add the hash of the sum of the coordinates, then hash again - i.e. Hash(Hash(x) + Hash(Hash(x)+y)).
For your purposes it doesn't matter much what you use for the hash function, so long as it's not too predictable and it avoids periodicity. Most hashes that get studied these days are for cryptographic purposes, which is overkill here. The other main set of hashes are those used for creating things like C#'s HashSet - and all C# objects provide these (the GetHashCode() method). However, these are not meant to be random-looking - their only goal is to avoid collisions. So it can be hard to find something in-between, which is cheap to compute but doesn't show obvious patterns.
I've taken the top function from this page and converted it to C# below:
http://burtleburtle.net/bob/hash/integer.html
public static int Hash(int input)
{
uint a = (uint)input;
a = (a ^ 61) ^ (a >> 16);
a = a + (a << 3);
a = a ^ (a >> 4);
a = a * 0x27d4eb2d;
a = a ^ (a >> 15);
return (int)a;
}
I haven't checked suitability much, but the page I took it from seems to have a bunch of analysis further down, if you're interested enough. You could also read Wikipedia: http://en.wikipedia.org/wiki/List_of_hash_functions
Again, for getting a hash from two coordinates, make sure you don't do something symmetrical or periodic - nesting the hashes is a simple solution that gives good results.
public static int Hash(int x, int y)
{
int hy = Hash(y);
return Hash(Hash(x+hy) + hy);
}
using the random method that you suggested seems to make a pattern. $$anonymous$$eeping the y coordinate at 1, the results as I increment the x coordinate are 2, 5, 8, 11, 14, 17. Should this not be happening?
Hi, sorry about that, you're right - System.Random doesn't respond at all well to this abuse. I've edited the answer with hopefully better advice - and replacements for both methods.
This is much better! Do you know what I could do to make it even more unpredictable? Like what is the key to hash methods exactly?
Is there something in particular about the results you're getting now that you don't like? There are some statistics you could use to check the randomness you're getting, e.g. for each possible tile type, count how many times it appears in a certain large range (e.g. from -1000 to 1000 in each axis) and see if it's abnormal.
If you go too far with this though you might end up with a result that is too locally random, and doesn't have enough global consistency. If you want to sometimes have clusters of tiles together that have something in common, there are other techniques to generate that - Perlin noise is commonly used, for example.
Regarding hash functions, generally the term just means a function that takes in (usually) complicated data and returns a consistent, simple type based on the content of the data. There's not really a key to hash functions in general though, because different purposes have different requirements.
Often people want things like a high likelihood of getting different values from different inputs - without specifying any relationships on the inputs. That applies to your case, though not to the same extent that it applies to GetHashCode. For some uses you want a degree of one-way-ness to the function, so that it's hard to find an input that gives a specific output - that's important for cryptography, but doesn't matter in your case.
For your case you want apparent randomness, which is a bit different, but shares some of these requirements. Just be aware that most hash functions are either designed with larger amounts of input data in $$anonymous$$d, or simply to distribute results evenly without being concerned with apparent randomness.
One area where this kind of randomness is used is in noise functions for pixel shaders, where you want a consistent value per pixel, but no correlation with neighbouring pixels. You might find some good examples there, though the art of pixel shader authoring is mostly to find something as cheap as you can that gives a result that's just about convincing enough.
wow thanks for all the info! and I am not sure yet if this is good enough, all i want is apparent randomness with as little repetition as possible. I plan on using a different hash for tiles, rocks locations, tree locations, shrubs locations, and so on so that almost every tile will be unique.
Your answer
Follow this Question
Related Questions
Algorithm for loading sounds 1 Answer
Sphere made of cubes algorithm 4 Answers
My precedural Algorithm for Tidy TileMapper is not working! 3 Answers
Best Solution For Procedural Match-3 Board? 0 Answers
Procedural Mesh 1 Answer