c - 随机生成的二维噪声

Question

我正在尝试生成随机二维网格，该网格是根据 [x, y] 坐标按程序生成的(与预先生成二维数字数组相反)。这样做的原因是 map 可能很大，而且很可能实际不需要大部分网格。

这是我目前所拥有的:

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

更新:要求 value_at 具有引用透明性(在可能的范围内)。所以以下必须成立:

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

assert(i == j);

换句话说，如果我用相同的参数调用 value_at，无论我在程序执行期间调用它多少次，它都应该总是给出相同的结果.这样做的原因是因为我试图生成随机地形，这将涉及不同网格点之间的插值；用户也有可能会重新访问网格内的某个点。

它正确地生成了网格，但是我在输出中看到了很多规律:

您可以看到有一种“颗粒”发送线在输出中沿对角线移动。

我正在对此进行一些研究，但在寻找方法时遇到了一些麻烦。有人知道如何让网格更“随机”一点吗？

更新:感谢 ldgabbay 提供的链接，我添加了一个简单的旋转哈希函数，如下所示:

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;
}

value_at 函数如下所示:

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);
}

这是它生成的一些示例网格:

Answer 1

我认为您使用 srand 使 value_at 具有确定性时存在一个微妙的缺陷。通常，随机数生成器被播种一次，从中产生的数字是伪随机的。但是，在这种方法中，您正在查看从不同种子的随机数生成器中产生的第一个随机数。这可能不像您想要的那样随机。我希望这在很大程度上取决于您系统上随机数生成器的实现。

既然你有不能保存你的随机序列的需求，我有几个想法。

1)

尝试改变您用来改变随机种子的公式。现在，当你穿过网格时，你的种子正在发生非常可预测的变化。 (例如种子，种子+1，种子+2，...，种子+宽度，种子+宽度+1等)你想要的是:

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

其中 hash 是一种简单的东西，它将 [0, width*height) 中的数字映射到该范围内的另一个数字，但不易预测。

可以找到一些简单的散列函数here .

2)

在获取随机值之前，从随机数生成器中弹出确定数量的随机数。所以，在你的 return 声明之前，添加一行:

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

您可以将 skip 设置为一个固定数字，或者您甚至可以将其设为 x、y 甚至种子的确定性函数。