CODEWITHSUNDEEP
crandomprocedural-generation
robbrit
robbrit

Reputation: 17960

Randomly Generated 2D Noise

I'm trying to generate a random 2D grid that is procedurally generated from the [x, y] coordinates (as opposed to pre-generating a 2D array of numbers). The reason for this is that the map is potentially huge, and there is a good possibility that much of the grid will not actually be needed.

Here's what I have so far:

double value_at(Grid *grid, int seed, int x, int y) {
  srand(seed + x + y * grid->width);
  return (double)rand() / (RAND_MAX + 1.0);
}

UPDATE: A requirement is that value_at has referential transparency (to the extent possible). So the following must hold true:

int i = value_at(grid, seed, 100, 100);
int j = value_at(grid, seed, 100, 100);

assert(i == j);

In other words, if I call value_at with the same arguments it should always give the same result no matter how many times I call it during the execution of the program. The reason for this is because I am trying to generate random terrain, which will involve interpolation between different grid points; it is also possible that the user will re-visit a certain point within the grid.

It's generating grids properly, however I'm seeing a lot of regularities in the output:

Grid 1 Grid 2

You can see that there is a sort of "grain" that sends lines moving diagonally through the output.

I'm doing some research on it but I'm having some trouble finding ways to do this. Does anybody have an idea on how to get the grids to be a bit more "random"?

UPDATE: Thanks to the links provided by ldgabbay, I've added a simple rotating hash function that looks like this:

int simple_hash(int * is, int count) {
  // this contains a bunch of arbitrarily chosen prime numbers
  int i;
  unsigned int hash = 80238287;

  for (i = 0; i < count; i++){
    hash = (hash << 4) ^ (hash >> 28) ^ (is[i] * 5449 % 130651);
  }

  return hash % 75327403;
}

Then the value_at function looks like this:

double value_at(Grid *grid, int seed, int x, int y) {
  int is[] = {x, y, seed};
  srand(simple_hash(is, 3));
  return (double)rand() / (RAND_MAX + 1.0);
}

Here are some sample grids that it generates:

Grid 3 enter image description here

Upvotes: 1

Views: 865

Answers (1)

ldgabbay
ldgabbay

Reputation: 1183

I think there's a subtle flaw in your use of srand to make the value_at deterministic. Normally, a random number generator is seeded once and the numbers that come out of it are pseudo random. However, in this method, you are looking at the very first random number to come out of the random number generator for different seeds. This may not be as random as you'd like. I would expect this is highly dependent on the implementation of the random number generator on your system.

Since you have the requirement that you can't save your random sequence, I have a few ideas.

1)

Try altering the formula you use to alter the random seed. Right now, your seed is changing very predictably as you move across the grid. (e.g. seed, seed+1, seed+2, ..., seed+width, seed+width+1, etc.) What you want is:

srand(seed + hash(x + y * grid->width));

where hash is something simple that maps a number in [0, width*height) to another number in that range, but less predictable.

Some simple hash functions can be found here.

2)

Pop a deterministic number of random numbers off the random number generator before getting your random value. So, before your return statement, add a line like:

for (i=0; i!=skip; ++i) rand();

You can set skip to a fixed number, or you could even make it a deterministic function of x, y, or even seed.

Upvotes: 1

Related Questions